Loop Restricted Existential Rules and First-order Rewritability for Query Answering
This work addresses the problem of efficient query answering in ontology-based data access for database and AI researchers, offering a new language that generalizes and contains most known first-order rewritable classes, though it is incremental in extending existing theoretical frameworks.
The paper introduces loop restricted (LR) TGDs, a new class of existential rules with restrictions on rule set loops, and shows that conjunctive query answering under LR TGDs is decidable, first-order rewritable, with data complexity in AC0 and combined complexity EXPTIME-complete.
In ontology-based data access (OBDA), the classical database is enhanced with an ontology in the form of logical assertions generating new intensional knowledge. A powerful form of such logical assertions is the tuple-generating dependencies (TGDs), also called existential rules, where Horn rules are extended by allowing existential quantifiers to appear in the rule heads. In this paper we introduce a new language called loop restricted (LR) TGDs (existential rules), which are TGDs with certain restrictions on the loops embedded in the underlying rule set. We study the complexity of this new language. We show that the conjunctive query answering (CQA) under the LR TGDs is decid- able. In particular, we prove that this language satisfies the so-called bounded derivation-depth prop- erty (BDDP), which implies that the CQA is first-order rewritable, and its data complexity is in AC0 . We also prove that the combined complexity of the CQA is EXPTIME complete, while the language membership is PSPACE complete. Then we extend the LR TGDs language to the generalised loop restricted (GLR) TGDs language, and prove that this class of TGDs still remains to be first-order rewritable and properly contains most of other first-order rewritable TGDs classes discovered in the literature so far.