Ontology-Mediated Queries: Combined Complexity and Succinctness of Rewritings via Circuit Complexity

We give solutions to two fundamental computational problems in ontology-based data access with the W3C standard ontology language OWL 2 QL: the succinctness problem for first-order rewritings of ontology-mediated queries (OMQs) and the complexity problem for OMQ answering. We classify OMQs according...

Full description

Saved in:
Bibliographic Details
Published in:Journal of the ACM 2018-09, Vol.65 (5), p.1-51, Article 28
Main Authors: Bienvenu, Meghyn, Kikot, Stanislav, Kontchakov, Roman, Podolskii, Vladimir V., Zakharyaschev, Michael
Format: Article
Language:English
Subjects:
Artificial Intelligence
Boolean algebra
Boolean functions
Circuit complexity
Complexity
Complexity theory
Computation
Computational complexity and cryptography
Computer Science
Computing methodologies
Data management systems
Description logics
Information systems
Knowledge representation
Knowledge representation and reasoning
Logic
Mathematical functions
Mathematical problems
Ontology
Polynomials
Programming languages
Queries
Query languages
Theory of computation
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We give solutions to two fundamental computational problems in ontology-based data access with the W3C standard ontology language OWL 2 QL: 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.
ISSN:0004-5411
1557-735X
DOI:10.1145/3191832