• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Book chapter

Theoretically optimal datalog rewritings for OWL 2 QL ontology-mediated queries

P. 1-13.
Bienvenu M., Kikot S., Kontchakov R., Podolskii V. V., Zakharyaschev M.

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. © 2016, CEUR-WS. All rights reserved.

In book

Edited by: M. Lenzerin. Iss. 1577. 2016.