Abstract
Existential rules, a.k.a. dependencies in databases, and Datalog+/- in knowledge representation and reasoning recently, are a family of important logical languages widely used in computer science and artificial intelligence. Towards a deep understanding of these languages in model theory, we establish model-theoretic characterizations for a number of existential rule languages such as (disjunctive) embedded dependencies, tuple-generating dependencies (TGDs), (frontier-)guarded TGDs and linear TGDs. All these characterizations hold for the class of arbitrary structures, and most of them also work on the class of finite structures. As a natural application of these results, complexity bounds for the rewritability of above languages are also identified.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI), January 7-15, 2021, online |
| Publisher | International Joint Conferences on Artificial Intelligence |
| Pages | 1940-1946 |
| Number of pages | 7 |
| ISBN (Print) | 9780999241165 |
| Publication status | Published - 2020 |
| Event | International Joint Conference on Artificial Intelligence - Duration: 7 Jan 2021 → … |
Publication series
| Name | |
|---|---|
| ISSN (Print) | 1045-0823 |
Conference
| Conference | International Joint Conference on Artificial Intelligence |
|---|---|
| Period | 7/01/21 → … |
Bibliographical note
Publisher Copyright:© 2020 Inst. Sci. inf., Univ. Defence in Belgrade. All rights reserved.