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
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.
Type de document :
Communication dans un congrès
IJCAI: International Joint Conference on Artificial Intelligence, Aug 2017, Melbourne, Australia. 26th International Joint Conference on Artificial Intelligence, 2017, 〈https://ijcai-17.org〉
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01632224
Contributeur : Marie-Laure Mugnier <>
Soumis le : jeudi 9 novembre 2017 - 18:58:54
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : samedi 10 février 2018 - 13:54:01

Fichier

bbmt-ijcai2017.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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. 26th International Joint Conference on Artificial Intelligence, 2017, 〈https://ijcai-17.org〉. 〈lirmm-01632224〉

Partager

Métriques

Consultations de la notice

223

Téléchargements de fichiers

99