The complexity of ontology-based data access with OWL 2 QL and bounded treewidth queries

Bienvenu, Meghyn, Kikot, Stanislav, Kontchakov, Roman, Podolskii, Vladimir, Ryzhikov, Vladislav and Zakharyaschev, Michael (2017) The complexity of ontology-based data access with OWL 2 QL and bounded treewidth queries. In: PODS 2017, 14-19 May 2017, Chicago, Illinois, United States.

1702.03358.pdf - Accepted Version

Download (908kB) | Preview
Official URL:

Abstract / Description

Our concern is the overhead of answeringOWL 2 QLontology-mediated queries (OMQs) inontology-based data access compared to evaluating their underlying tree-shaped and boundedtreewidth conjunctive queries (CQs). We show that OMQs withbounded-depth ontologieshave nonrecursive datalog (NDL) rewritings that can be constructed and evaluated inLOGCFLfor combined complexity, even inNLif their CQs are tree-shaped with a bounded numberof leaves, and so incur no overhead in complexity-theoreticterms. For OMQs with arbitraryontologies and bounded-leaf CQs, NDL-rewritings are constructed and evaluated inLOGCFL.We show experimentally feasibility and scalability of our rewritings compared to previouslyproposed 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 inthe CQs is regarded as the parameter, and that answering OMQswith a fixed ontology (ofinfinite depth) isNP-complete for tree-shaped andLOGCFLfor bounded-leaf CQs.

Item Type: Conference or Workshop Item (Paper)
Uncontrolled Keywords: ontology-based data access; ontology-mediated query; query rewriting; combined & parameterised complexity
Subjects: 000 Computer science, information & general works
Department: School of Computing and Digital Media
Depositing User: Stanislav Kikot
Date Deposited: 15 May 2020 11:26
Last Modified: 15 May 2020 11:26


Downloads per month over past year

Downloads each year

Actions (login required)

View Item View Item