# Model-theoretic Characterizations of Existential Rule Languages

arXiv: https://arxiv.org/abs/2001.08688 · HTML: https://mlsanity.com/paper/2001.08688/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jan 2020.

## Built on by (most cited first, 1 of 1)

- [Characterizing the Program Expressive Power of Existential Rule Languages](https://mlsanity.com/paper/2112.08136/) (2021)

## Abstract (arXiv)

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 arbitrary structures, and most of them also work on the class of finite structures. As a natural application of these characterizations, complexity bounds for the rewritability of above languages are also identified.