Complexity Boundaries for Generalized Guarded Existential Rules - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Reports Year : 2011

Complexity Boundaries for Generalized Guarded Existential Rules


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.
Fichier principal
Vignette du fichier
rr-main-with-authors.pdf (436.66 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-00568935 , version 1 (23-03-2011)


  • HAL Id : lirmm-00568935 , version 1
  • PRODINRA : 246571


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⟩
398 View
311 Download


Gmail Facebook X LinkedIn More