Ontology-mediated queries: combined complexity and succinctness of rewritings via circuit complexity

Bienvenu, Meghyn, Kikot, Stanislav, Kontchakov, Roman, Podolskii, Vladimir and Zakharyaschev, Michael (2018) Ontology-mediated queries: combined complexity and succinctness of rewritings via circuit complexity. Journal of the ACM, 65 (5). pp. 1-51. ISSN 0004-5411

Preview

Text HyperACM.pdf - Accepted Version Download (887kB) | Preview

Abstract / Description

We give solutions to two fundamental computational problems in ontology-based data access with the W3C standard ontology language OWL2QL: the succinctness problem for first-order rewritings of ontology-mediated queries (OMQs), and the complexity problem for OMQ answering. We classify OMQs according to the shape of their conjunctive queries (treewidth, the number of leaves) and the existential depth of their ontologies. For each of these classes, we determine the combined complexity of OMQ answering, and whether all OMQs in the class have polynomial-size first-order, positive existential, and nonrecursive datalog rewritings. We obtain the succinctness results using hypergraph programs, a new computational model for Boolean functions, which makes it possible to connect the size of OMQ rewritings and circuit complexity.

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:45
Last Modified:	15 May 2020 10:45
URI:	https://repository.londonmet.ac.uk/id/eprint/5786

Downloads

Actions (login required)

View Item