Loop restricted existential rules and first-order rewritability for query answering.

This article introduces and studies new classes of tuple-generating dependencies (TGDs), also known as existential rules, within ontology-based data access (OBDA). The main focus is on defining the class of loop restricted (LR) TGDs, characterized by restrictions on loops in derivation paths of TGDs, and its generalization to generalized loop restricted (GLR) TGDs. The authors prove that both LR and GLR classes satisfy the bounded derivation tree depth property (BDTDP), which implies the bounded derivation-depth property (BDDP), ensuring that conjunctive query answering (CQA) under these classes is decidable and first-order rewritable. Complexity results show that CQA data complexity for LR and GLR TGDs is in AC⁰, while combined complexity is 2-ExpTime complete; deciding membership in these classes is Pspace complete. Furthermore, GLR TGDs properly contain most previously known first-order rewritable TGD classes but are incomparable with the labeled oblivious acyclic (LOA) class, highlighting their broad applicability in efficient OBDA systems.