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 metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/hal-01632929
Contributor : Meghyn Bienvenu <>
Submitted on : Friday, November 10, 2017 - 5:33:47 PM
Last modification on : Wednesday, March 13, 2019 - 5:22:02 PM
Long-term archiving on : Sunday, February 11, 2018 - 2:12:00 PM

File

BieKikKonRyzZak-DL17-Opt.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01632929, version 1

Citation

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⟩

Share

Metrics

Record views

429

Files downloads

52