Skip to Main content Skip to Navigation
New interface
Conference papers

Optimal Nonrecursive Datalog Rewritings of Linear TGDs and Bounded (Hyper)Tree-Width Queries

Meghyn Bienvenu 1 Stanislav Kikot 2 Roman Kontchakov 2 Vladislav Ryzhikov 3 Michael Zakharyaschev 2 
1 GRAPHIK - Graphs for Inferences on Knowledge
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : Our concern is answering ontology-mediated queries (O, q), where O 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download
Contributor : Meghyn Bienvenu Connect in order to contact the contributor
Submitted on : Friday, November 10, 2017 - 5:33:47 PM
Last modification on : Friday, August 5, 2022 - 3:03:00 PM
Long-term archiving on: : Sunday, February 11, 2018 - 2:12:00 PM


Files produced by the author(s)


  • HAL Id : hal-01632929, version 1



Meghyn Bienvenu, Stanislav Kikot, Roman Kontchakov, Vladislav Ryzhikov, Michael Zakharyaschev. Optimal Nonrecursive Datalog Rewritings of Linear TGDs and Bounded (Hyper)Tree-Width Queries. DL: Description Logics, Jul 2017, Montpellier, France. ⟨hal-01632929⟩



Record views


Files downloads