Theoretically Optimal Datalog Rewritings for OWL 2 QL Ontology-Mediated Queries

Abstract

We show that, for OWL 2 QL ontology-mediated queries with (i) ontologies of bounded depth and conjunctive queries of bounded treewidth, (ii) ontologies of bounded depth and bounded-leaf tree-shaped conjunctive queries, and (iii) arbitrary ontologies and bounded-leaf tree-shaped conjunctive queries, one can construct and evaluate nonrecursive datalog rewritings by, respectively, LOGCFL, NL and LOGCFL algorithms, which matches the optimal combined complexity.

full version of the paper in the Proc. of the 29th Int. Workshop on Description Logics (DL 2016)