Walking the Complexity Lines for Generalized Guarded Existential Rules

Jean-François BagetJean-François Baget, Marie-Laure MugnierMarie-Laure Mugnier, Sebastian RudolphSebastian Rudolph, Michaël ThomazoMichaël Thomazo

Download

Jean-François Baget, Marie-Laure Mugnier, Sebastian Rudolph, Michaël Thomazo
Walking the Complexity Lines for Generalized Guarded Existential Rules
In Toby Walsh, eds., Proceedings of the 22nd International Joint Conference on Artificial Intelligence, 712-717, July 2011. IJCAI/AAAI

Details
Bibtex

KurzfassungAbstract
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 greedy bounded treewidth sets (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 gbts, which is worst-case optimal for combined complexity with bounded predicate arity, as well as for data complexity. Secondly, we classify several 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.
Forschungsgruppe:Research Group: Computational LogicComputational Logic

@inproceedings{BMRT2011,
  author    = {Jean-Fran{\c{c}}ois Baget and Marie-Laure Mugnier and Sebastian
               Rudolph and Micha{\"{e}}l Thomazo},
  title     = {Walking the Complexity Lines for Generalized Guarded Existential
               Rules},
  editor    = {Toby Walsh},
  booktitle = {Proceedings of the 22nd International Joint Conference on
               Artificial Intelligence},
  publisher = {IJCAI/AAAI},
  year      = {2011},
  month     = {July},
  pages     = {712-717}
}