Stage-oe-small.jpg

Inproceedings3149: Unterschied zwischen den Versionen

Aus Aifbportal
Wechseln zu:Navigation, Suche
Zeile 13: Zeile 13:
 
|Month=Juli
 
|Month=Juli
 
|Booktitle=Proceedings of the 22nd International Joint Conference on Artificial Intelligence
 
|Booktitle=Proceedings of the 22nd International Joint Conference on Artificial Intelligence
 +
|Pages=963-968
 
|Publisher=IJCAI 2011
 
|Publisher=IJCAI 2011
|Note=to appear
+
|Editor=Toby Walsh
 
}}
 
}}
 
{{Publikation Details
 
{{Publikation Details
 
|Abstract=Existential rules, i.e. Datalog extended with existential quantifiers in rule heads, are currently studied under a variety of names such as Datalog+/–, \exists\forall-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.
 
|Abstract=Existential rules, i.e. Datalog extended with existential quantifiers in rule heads, are currently studied under a variety of names such as Datalog+/–, \exists\forall-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.
|Download=KR-IJCAI2011-joining-acyclicity.pdf,  
+
|Download=KR-IJCAI2011-joining-acyclicity.pdf,
 
|Projekt=ExpresST
 
|Projekt=ExpresST
 
|Forschungsgruppe=Wissensmanagement
 
|Forschungsgruppe=Wissensmanagement

Version vom 12. August 2011, 16:33 Uhr


Extending Decidable Existential Rules by Joining Acyclicity and Guardedness


Extending Decidable Existential Rules by Joining Acyclicity and Guardedness



Published: 2011 Juli
Herausgeber: Toby Walsh
Buchtitel: Proceedings of the 22nd International Joint Conference on Artificial Intelligence
Seiten: 963-968
Verlag: IJCAI 2011

Referierte Veröffentlichung

BibTeX

Kurzfassung
Existential rules, i.e. Datalog extended with existential quantifiers in rule heads, are currently studied under a variety of names such as Datalog+/–, \exists\forall-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.

Download: Media:KR-IJCAI2011-joining-acyclicity.pdf

Projekt

ExpresST



Forschungsgruppe

Wissensmanagement


Forschungsgebiet

Komplexitätstheorie, Logik, Logikprogrammierung