Theoretically Optimal Datalog Rewritings for OWL 2 QL Ontology-Mediated Queries
Meghyn Bienvenu, Stanislav Kikot, Roman Kontchakov, Vladimir Vladimirovich Podolskii, Michael Zakharyaschev · BIROn (Birkbeck, University of London) · 2016
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.