On the Complexity of Evaluating Regular Path Queries over Linear Existential Rules

Meghyn Bienvenu 1, 2, 3 Michaël Thomazo 4
3 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
4 CEDAR - Rich Data Analytics at Cloud Scale
Inria Saclay - Ile de France
Abstract : In the setting of ontology-mediated query answering, a query is evaluated over a knowledge base 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 evaluating the standard form of navigational queries, namely two-way regular path queries, over knowledge bases whose ontology is expressed by means of linear existential rules. More specifically, we show how to extend an approach developed for DL-LiteR to obtain an exponential-time decision procedure for linear rules. We prove that this algorithm achieves optimal worst-case complexity by establishing a matching EXPTIME lower bound.
Type de document :
Communication dans un congrès
10th International Conference on Web Reasoning and Rule Systems, Sep 2016, Aberdeen, United Kingdom. 10th International Conference on Web Reasoning and Rule Systems
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01341787
Contributeur : Michaël Thomazo <>
Soumis le : lundi 4 juillet 2016 - 17:50:09
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01341787, version 1

Citation

Meghyn Bienvenu, Michaël Thomazo. On the Complexity of Evaluating Regular Path Queries over Linear Existential Rules. 10th International Conference on Web Reasoning and Rule Systems, Sep 2016, Aberdeen, United Kingdom. 10th International Conference on Web Reasoning and Rule Systems. 〈hal-01341787〉

Partager

Métriques

Consultations de la notice

233

Téléchargements de fichiers

93