Model-theoretic Characterizations of Existential Rule Languages
Heng Zhang, Yan Zhang, Guifei Jiang
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.
BibTeX
@inproceedings{ijcai2020p269,
title = {Model-theoretic Characterizations of Existential Rule Languages},
author = {Zhang, Heng and Zhang, Yan and Jiang, Guifei},
booktitle = {Proceedings of the Twenty-Ninth International Joint Conference on
Artificial Intelligence, {IJCAI-20}},
publisher = {International Joint Conferences on Artificial Intelligence Organization},
editor = {Christian Bessiere},
pages = {1940--1946},
year = {2020},
month = {7},
note = {Main track},
doi = {10.24963/ijcai.2020/269},
url = {https://doi.org/10.24963/ijcai.2020/269},
}