Loop Restricted Existential Rules and First-order Rewritability for Query Answering

  • 2018-08-02 01:48:26
  • Vernon Asuncion, Yan Zhang, Heng Zhang, Yun Bai, Weisheng Si
  • 0

Abstract

In ontology-based data access (OBDA), the classical database is enhanced withan ontology in the form of logical assertions generating new intensionalknowledge. A powerful form of such logical assertions is the tuple-generatingdependencies (TGDs), also called existential rules, where Horn rules areextended by allowing existential quantifiers to appear in the rule heads. Inthis paper we introduce a new language called loop restricted (LR) TGDs(existential rules), which are TGDs with certain restrictions on the loopsembedded in the underlying rule set. We study the complexity of this newlanguage. We show that the conjunctive query answering (CQA) under the LR TGDsis decid- able. In particular, we prove that this language satisfies theso-called bounded derivation-depth prop- erty (BDDP), which implies that theCQA is first-order rewritable, and its data complexity is in AC0 . We alsoprove that the combined complexity of the CQA is EXPTIME complete, while thelanguage membership is PSPACE complete. Then we extend the LR TGDs language tothe generalised loop restricted (GLR) TGDs language, and prove that this classof TGDs still remains to be first-order rewritable and properly contains mostof other first-order rewritable TGDs classes discovered in the literature sofar.

 

Quick Read (beta)

loading the full paper ...