Tree-like queries in OWL 2 QL: succinctness and complexity results

Bienvenu, Meghyn, Kikot, Stanislav and Podolskii, Vladimir (2015) Tree-like queries in OWL 2 QL: succinctness and complexity results. Proceedings of LICS 2015: 30th Annual ACM/IEEE Symposium on Logic in Computer Science,. pp. 317-328.

[img]
Preview
Text
lics15_main.pdf - Accepted Version

Download (649kB) | Preview
Official URL: http://dx.doi.org/10.1109/LICS.2015.38

Abstract / Description

This paper investigates the impact of query topology on the difficulty of answering conjunctive queries in the presence of OWL 2 QL ontologies. Our first contribution is to clarify the worst-case size of positive existential (PE), non-recursive Datalog (NDL), and first-order (FO) rewritings for various classes of tree-like conjunctive queries, ranging from linear queries to bounded treewidth queries. Perhaps our most surprising result is a superpolynomial lower bound on the size of PE-rewritings that holds already for linear queries and ontologies of depth 2. More positively, we show that polynomial-size NDL-rewritings always exist for tree-shaped queries with a bounded number of leaves (and arbitrary ontologies), and for bounded tree-width queries paired with bounded depth ontologies. For FO-rewritings, we equate the existence of polysize rewritings with well-known problems in Boolean circuit complexity. As our second contribution, we analyze the computational complexity of query answering and establish tractability results (either NLor LOGCFL-completeness) for a range of query-ontology pairs. Combining our new results with those from the literature yields a complete picture of the succinctness and complexity landscapes for the considered classes of queries and ontologies.

Item Type: Article
Uncontrolled Keywords: ontology-based data access, description logic, ontology-mediated query, query rewriting, succinctness, computational complexity, circuit complexity
Subjects: 000 Computer science, information & general works
Department: School of Computing and Digital Media
Depositing User: Stanislav Kikot
Date Deposited: 15 May 2020 10:58
Last Modified: 15 May 2020 11:11
URI: http://repository.londonmet.ac.uk/id/eprint/5787

Downloads

Downloads per month over past year



Downloads each year

Actions (login required)

View Item View Item