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

We give solutions to two fundamental computational problems in ontology-based\ndata access with the W3C standard ontology language OWL 2 QL: the succinctness\nproblem for first-order rewritings of ontology-mediated queries (OMQs), and the\ncomplexity problem for OMQ answering. We classify OMQs according to the shape\nof their conjunctive queries (treewidth, the number of leaves) and the\nexistential depth of their ontologies. For each of these classes, we determine\nthe combined complexity of OMQ answering, and whether all OMQs in the class\nhave polynomial-size first-order, positive existential, and nonrecursive\ndatalog rewritings. We obtain the succinctness results using hypergraph\nprograms, a new computational model for Boolean functions, which makes it\npossible to connect the size of OMQ rewritings and circuit complexity.\n