Answering Conjunctive Regular Path Queries over Guarded Existential Rules - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2017

Answering Conjunctive Regular Path Queries over Guarded Existential Rules

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.
Fichier principal
Vignette du fichier
bbmt-ijcai2017.pdf (263.38 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-01632224 , version 1 (09-11-2017)

Identifiers

  • HAL Id : lirmm-01632224 , version 1

Cite

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⟩
368 View
229 Download

Share

More