Walking the Complexity Lines for Generalized Guarded Existential Rules

Jean-François Baget 1 Marie-Laure Mugnier 1, * Sebastian Rudolph 2 Michaël Thomazo 1
* Auteur correspondant
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 : We establish complexities of the conjunctive query entailment problem for classes of existential rules (i.e. Tuple-Generating Dependencies or Datalog+/- rules). Our contribution is twofold. First, we introduce the class of greedy bounded treewidth sets (gbts), 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. Second, 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 bounded and unbounded predicate arity) and data complexity.
Type de document :
Communication dans un congrès
Toby Walsh. IJCAI: International Joint Conference on Artificial Intelligence, Jul 2011, Barcelona, Spain. AAAI Press, 22nd International Joint Conference on Artificial Intelligence, pp.712-717, 2011, 〈http://ijcai-11.iiia.csic.es/〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00618081
Contributeur : Jean-François Baget <>
Soumis le : mercredi 31 août 2011 - 15:56:56
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Identifiants

  • HAL Id : lirmm-00618081, version 1

Collections

Citation

Jean-François Baget, Marie-Laure Mugnier, Sebastian Rudolph, Michaël Thomazo. Walking the Complexity Lines for Generalized Guarded Existential Rules. Toby Walsh. IJCAI: International Joint Conference on Artificial Intelligence, Jul 2011, Barcelona, Spain. AAAI Press, 22nd International Joint Conference on Artificial Intelligence, pp.712-717, 2011, 〈http://ijcai-11.iiia.csic.es/〉. 〈lirmm-00618081〉

Partager

Métriques

Consultations de la notice

374