Model-Theoretic Characterizations of Existential Rule Languages
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.
Cite
Text
Zhang et al. "Model-Theoretic Characterizations of Existential Rule Languages." International Joint Conference on Artificial Intelligence, 2020. doi:10.24963/IJCAI.2020/269Markdown
[Zhang et al. "Model-Theoretic Characterizations of Existential Rule Languages." International Joint Conference on Artificial Intelligence, 2020.](https://mlanthology.org/ijcai/2020/zhang2020ijcai-model/) doi:10.24963/IJCAI.2020/269BibTeX
@inproceedings{zhang2020ijcai-model,
title = {{Model-Theoretic Characterizations of Existential Rule Languages}},
author = {Zhang, Heng and Zhang, Yan and Jiang, Guifei},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2020},
pages = {1940-1946},
doi = {10.24963/IJCAI.2020/269},
url = {https://mlanthology.org/ijcai/2020/zhang2020ijcai-model/}
}