Recent years have seen an increasing interest in ontology-mediated query answering (OMQA), in which the semantic knowledge provided by an ontology is exploited when querying data. One popular ontology language for OMQA is OWL 2 QL, a W3C-standardized language based upon the DL-Lite description logic. This language has the desirable property that OMQA can be reduced to database query evaluation by means of query rewriting. In this talk, I will consider two fundamental questions about OMQA with OWL 2 QL ontologies: 1) Is it possible to devise query rewriting algorithms that produce polynomial-size rewritings? 2) How does the worst-case complexity of OMQA vary depending on the structure of the ontology-mediated query (OMQ)? After classifying OMQs according to the shape of their conjunctive queries (treewidth, the number of leaves) and the existential depth of their ontologies, I will present the obtained complexity and succinctness landscapes and sketch some of the main ingredients in the proofs (in particular, a novel connection between OMQ rewritings and circuit complexity). 

 

This talk is based upon a JACM'18 paper co-authored with Stanislav Kikot, Roman Kontchakov, Vladimir Podolskii, and Michael Zakharyaschev.