London Met Repository

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

Lists

Tools

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.

[+][-]

Abstract

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.

Documents