Extending Decidable Existential Rules by Joining Acyclicity and Guardedness.
Existential rules, i.e. Datalog extended with existential quantifiers in rule heads, are currently studied under a variety of names such as Datalog+/-, ∀∃-rules, and tuple-generating dependencies. The renewed interest in this formalism is fuelled by a wealth of recently discovered language fragments...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Conference item |
| Published: |
IJCAI/AAAI
2011
|
| _version_ | 1797103879002783744 |
|---|---|
| author | Krötzsch, M Rudolph, S |
| author2 | Walsh, T |
| author_facet | Walsh, T Krötzsch, M Rudolph, S |
| author_sort | Krötzsch, M |
| collection | OXFORD |
| description | Existential rules, i.e. Datalog extended with existential quantifiers in rule heads, are currently studied under a variety of names such as Datalog+/-, ∀∃-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. |
| first_indexed | 2024-03-07T06:26:16Z |
| format | Conference item |
| id | oxford-uuid:f466b81f-eaa1-47af-8863-e97df8469968 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T06:26:16Z |
| publishDate | 2011 |
| publisher | IJCAI/AAAI |
| record_format | dspace |
| spelling | oxford-uuid:f466b81f-eaa1-47af-8863-e97df84699682022-03-27T12:19:30ZExtending Decidable Existential Rules by Joining Acyclicity and Guardedness.Conference itemhttp://purl.org/coar/resource_type/c_5794uuid:f466b81f-eaa1-47af-8863-e97df8469968Symplectic Elements at OxfordIJCAI/AAAI2011Krötzsch, MRudolph, SWalsh, TExistential rules, i.e. Datalog extended with existential quantifiers in rule heads, are currently studied under a variety of names such as Datalog+/-, ∀∃-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. |
| spellingShingle | Krötzsch, M Rudolph, S Extending Decidable Existential Rules by Joining Acyclicity and Guardedness. |
| title | Extending Decidable Existential Rules by Joining Acyclicity and Guardedness. |
| title_full | Extending Decidable Existential Rules by Joining Acyclicity and Guardedness. |
| title_fullStr | Extending Decidable Existential Rules by Joining Acyclicity and Guardedness. |
| title_full_unstemmed | Extending Decidable Existential Rules by Joining Acyclicity and Guardedness. |
| title_short | Extending Decidable Existential Rules by Joining Acyclicity and Guardedness. |
| title_sort | extending decidable existential rules by joining acyclicity and guardedness |
| work_keys_str_mv | AT krotzschm extendingdecidableexistentialrulesbyjoiningacyclicityandguardedness AT rudolphs extendingdecidableexistentialrulesbyjoiningacyclicityandguardedness |