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.
Type de document :
Communication dans un congrès
International Workshop on Description Logics, Jul 2017, Montpellier, France. 30th International Workshop on Description Logics, 2017
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01632929
Contributeur : Meghyn Bienvenu <>
Soumis le : vendredi 10 novembre 2017 - 17:33:47
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : dimanche 11 février 2018 - 14:12:00

Fichier

BieKikKonRyzZak-DL17-Opt.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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. International Workshop on Description Logics, Jul 2017, Montpellier, France. 30th International Workshop on Description Logics, 2017. 〈hal-01632929〉

Partager

Métriques

Consultations de la notice

329

Téléchargements de fichiers

32