Answering Conjunctive Regular Path Queries over Guarded Existential Rules

Answering Conjunctive Regular Path Queries over Guarded Existential Rules

Jean-Fran├žois Baget, Meghyn Bienvenu, Marie-Laure Mugnier, Michael Thomazo

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 793-799. https://doi.org/10.24963/ijcai.2017/110

Ontology-mediated query answering is concerned with the problem of answering queries over knowledge bases consisting of a database instance and an ontology. While most work in the area focuses on conjunctive queries, navigational queries are gaining increasing attention. In this paper, we investigate the complexity of answering two-way conjunctive regular path queries (CRPQs) over knowledge bases whose ontology is given by a set of guarded existential rules. We first consider the subclass of linear existential rules and show that CRPQ answering is EXPTIME-complete in combined complexity and NL-complete in data complexity, matching the recently established bounds for answering non-conjunctive RPQs. For guarded rules, we provide a non-trivial reduction to the linear case, which allows us to show that the complexity of CRPQ answering is the same as for plain conjunctive queries, namely, 2EXPTIME-complete in combined complexity and PTIME-complete in data complexity.
Keywords:
Knowledge Representation, Reasoning, and Logic: Computational Complexity of Reasoning
Knowledge Representation, Reasoning, and Logic: Knowledge Representation Languages
Knowledge Representation, Reasoning, and Logic: Logics for Knowledge Representation