Query rewriting over shallow ontologies

Abstract. We investigate the size of conjunctive query rewritings over OWL2QL ontologies of depth 1 and 2 by means of a new formalism, called hypergraph programs, for computing Boolean functions. Both pos-itive and negative results are obtained. All conjunctive queries over on-tologies of depth 1 have polynomial-size nonrecursive datalog rewritings; tree-shaped queries have polynomial-size positive existential rewritings; however, for some queries and ontologies of depth 1, positive existential rewritings can only be of superpolynomial size. Both positive existential and nonrecursive datalog rewritings of conjunctive queries and ontolo-gies of depth 2 suffer an exponential blowup in the worst case, while first-order rewritings can grow superpolynomially unless NP ⊆ P/poly.