Answering Conjunctive Regular Path Queries over Guarded Existential Rules

Jean-François Baget 1 Meghyn Bienvenu 1 Marie-Laure Mugnier 1 Michaël Thomazo 2
1 GRAPHIK - Graphs for Inferences on Knowledge
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, CRISAM - Inria Sophia Antipolis - Méditerranée
2 CEDAR - Rich Data Analytics at Cloud Scale
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
Abstract : 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 fo-cuses on conjunctive queries (CQs), 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 CQs, namely 2EXPTIME-complete in combined complexity and PTIME-complete in data complexity.
Document type :
Conference papers
Complete list of metadatas

Cited literature [11 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01632224
Contributor : Marie-Laure Mugnier <>
Submitted on : Thursday, November 9, 2017 - 6:58:54 PM
Last modification on : Friday, June 14, 2019 - 1:58:56 AM
Long-term archiving on : Saturday, February 10, 2018 - 1:54:01 PM

File

bbmt-ijcai2017.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-01632224, version 1

Citation

Jean-François Baget, Meghyn Bienvenu, Marie-Laure Mugnier, Michaël Thomazo. Answering Conjunctive Regular Path Queries over Guarded Existential Rules. IJCAI: International Joint Conference on Artificial Intelligence, Aug 2017, Melbourne, Australia. ⟨lirmm-01632224⟩

Share

Metrics

Record views

431

Files downloads

285