• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Глава

Optimal nonrecursive datalog rewritings of linear TGDs and bounded (Hyper)Tree-width queries

P. 1-12.
Bienvenu M., Kikot S., Kontchakov R., Ryzhikov V., Zakharyaschev M.

Our concern is answering ontology-mediated queries (Ο q), whereΟ is a set of linear tgds and q a conjunctive query (CQ) of bounded hypertree width. Assuming that the arity of predicates is bounded, we show that polynomial-size nonrecursive Datalog rewritings can be constructed and executed in (i) LOGCFL for OMQs with ontologies of bounded existential depth; (ii) NL for OMQs with ontologies of bounded depth and CQs whose hypertree decompositions have a bounded number of leaves; (iii) LOGCFL for OMQs with acyclic CQs whose join trees have a bounded number of leaves.

В книге

Под науч. редакцией: A. Artale, B. Glimm, R. Kontchakov. Aachen: CEUR Workshop Proceedings, 2017.