  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.
