Complexity Boundaries for Generalized Guarded Existential Rules
Lists
Only you see this
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.
BibTeX
@inproceedings{baget2011complexity,
author = {Jean-François Baget and Marie-Laure Mugnier and Sebastian Rudolph and Michaël Thomazo},
title = {{Complexity Boundaries for Generalized Guarded Existential Rules}},
booktitle = {HAL},
year = {2011},
}Loading related content...