The Complexity of Ontology-Based Data Access with OWL 2 QL and Bounded Treewidth Queries

Abstract : Our concern is the overhead of answering OWL 2 QL ontology-mediated queries (OMQs) in ontology-based data access compared to evaluating their underlying tree-shaped and bounded treewidth conjunctive queries (CQs). We show that OMQs with bounded-depth ontologies have nonrecursive datalog (NDL) rewritings that can be constructed and evaluated in LOGCFL for combined complexity, even in NL if their CQs are tree-shaped with a bounded number of leaves, and so incur no overhead in complexity-theoretic terms. For OMQs with arbitrary ontologies and bounded-leaf CQs, NDL-rewritings are constructed and evaluated in LOGCFL. We show experimentally feasibility and scalability of our rewritings compared to previously proposed NDL-rewritings. On the negative side, we prove that answering OMQs with tree-shaped CQs is not fixed-parameter tractable if the ontology depth or the number of leaves in the CQs is regarded as the parameter, and that answering OMQs with a fixed ontology (of infinite depth) is NP-complete for tree-shaped and LOGCFL for bounded-leaf CQs.
Type de document :
Communication dans un congrès
36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS 2017), May 2017, Chicago, United States. 2017
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01632638
Contributeur : Meghyn Bienvenu <>
Soumis le : vendredi 10 novembre 2017 - 14:40:38
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : dimanche 11 février 2018 - 14:00:40

Fichier

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

Identifiants

  • HAL Id : hal-01632638, version 1

Citation

Meghyn Bienvenu, Stanislav Kikot, Roman Kontchakov, Vladimir Podolskii, Vladislav Ryzhikov, et al.. The Complexity of Ontology-Based Data Access with OWL 2 QL and Bounded Treewidth Queries. 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS 2017), May 2017, Chicago, United States. 2017. 〈hal-01632638〉

Partager

Métriques

Consultations de la notice

269

Téléchargements de fichiers

27