Revisiting Acyclicity and Guardedness Criteria for Decidability of Existential Rules

PublikationenPublications

• Nach AutorBy Author
  • Markus KrötzschMarkus Krötzsch
  • Sebastian RudolphSebastian Rudolph
• Nach ForschungsgruppeBy Research Group
  • Information SystemsKnowledge-Based Systems

Toggle side column

Revisiting Acyclicity and Guardedness Criteria for Decidability of Existential Rules

Markus KrötzschMarkus Krötzsch,  Sebastian RudolphSebastian Rudolph

Revisiting Acyclicity and Guardedness Criteria for Decidability of Existential Rules

• Download

Markus Krötzsch, Sebastian Rudolph
Revisiting Acyclicity and Guardedness Criteria for Decidability of Existential Rules
Technical Report, Institut AIFB, KIT, January 2011

• Details
• Bibtex

• KurzfassungAbstract
  Existential rules, i.e. Datalog extended with existential quantifiers in rule heads, are currently studied under a variety of names such as Datalog+/-, forall-exists-rules, and tuple-generating dependencies. The renewed interest in this formalism is fuelled by a wealth of recently discovered language fragments for which query answering is decidable. This paper extends and consolidates two of the main approaches in this field -- acyclicity and guardedness -- by providing (1) complexity-preserving generalisations of weakly acyclic and weakly (frontier-)guarded rules, and (2) a novel formalism of glut-(frontier-)guarded rules that subsumes both. This builds on an insight that acyclicity can be used to extend any existential rule language while retaining decidability. Besides decidability, combined query complexities are established in all cases.
• Projekt:Project: ExpresST, WeDeL-R
• Forschungsgruppe:Research Group: Information Systems„Information Systems“ befindet sich nicht in der Liste (Computational Logic, Automatentheorie, Wissensverarbeitung, Knowledge-Based Systems, Knowledge Systems, Wissensbasierte Systeme, Logische Programmierung und Argumentation, Algebra und Diskrete Strukturen, Knowledge-aware Artificial Intelligence, Algebraische und logische Grundlagen der Informatik) zulässiger Werte für das Attribut „Forschungsgruppe“.Knowledge-Based Systems

@techreport{KR2011,
  author      = {Markus Kr{\"{o}}tzsch and Sebastian Rudolph},
  title       = {Revisiting Acyclicity and Guardedness Criteria for Decidability
                 of Existential Rules},
  institution = {Institut {AIFB,} {KIT}},
  year        = {2011},
  month       = {January}
}