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.

Preview

Text 1702.03358.pdf - Accepted Version Download (908kB) | Preview

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
URI:	https://repository.londonmet.ac.uk/id/eprint/5788

Downloads

Actions (login required)

View Item