Complexity Boundaries for Generalized Guarded Existential Rules

Jean-François Baget 1 Marie-Laure Mugnier 1 Sebastian Rudolph 2 Michaël Thomazo 1
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 : In this report, we establish complexities of the conjunctive query entailment problem for classes of existential rules (also called Tuple-Generating Dependencies or Datalog+/- rules). Our contribution is twofold. First, we introduce the class of \emph{greedy bounded treewidth sets} \emph{(gbts)} of rules, which covers guarded rules, and their known generalizations, namely (weakly) frontier-guarded rules. We provide a generic algorithm for query entailment with \emph{gbts}, which is worst-case optimal for combined complexity with bounded predicate arity, as well as for data complexity. Secondly, we classify several \emph{gbts} classes, whose complexity was unknown, namely frontier-one, frontier-guarded and weakly frontier-guarded rules, with respect to combined complexity (with both unbounded and bounded predicate arity) and data complexity.
Type de document :
Rapport
RR-11006, 2011, 39 p
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00568935
Contributeur : Marie-Laure Mugnier <>
Soumis le : mercredi 23 mars 2011 - 07:00:22
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : vendredi 24 juin 2011 - 02:25:50

Fichier

rr-main-with-authors.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00568935, version 1

Collections

Citation

Jean-François Baget, Marie-Laure Mugnier, Sebastian Rudolph, Michaël Thomazo. Complexity Boundaries for Generalized Guarded Existential Rules. RR-11006, 2011, 39 p. 〈lirmm-00568935〉

Partager

Métriques

Consultations de la notice

602

Téléchargements de fichiers

330