# Characterizing the Program Expressive Power of Existential Rule Languages

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 34 references that are in the map.
- First posted on arXiv 15 Dec 2021.

## Builds on (most cited first, 5 of 5)

- [Ontology-based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP](https://mlsanity.com/paper/1301.6479/) (2013)
- [Expressive Completeness of Existential Rule Languages for Ontology-based Query Answering](https://mlsanity.com/paper/1604.05006/) (2016)
- [Towards Universal Languages for Tractable Ontology Mediated Query Answering](https://mlsanity.com/paper/1911.11359/) (2019)
- [Existential Rule Languages with Finite Chase: Complexity and Expressiveness](https://mlsanity.com/paper/1411.5220/) (2014)
- [Model-theoretic Characterizations of Existential Rule Languages](https://mlsanity.com/paper/2001.08688/) (2020)

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

- [A Theory of Formalisms for Representing Knowledge](https://mlsanity.com/paper/2412.11855/) (2024)

## Abstract (arXiv)

Existential rule languages are a family of ontology languages that have been widely used in ontology-mediated query answering (OMQA). However, for most of them, the expressive power of representing domain knowledge for OMQA, known as the program expressive power, is not well-understood yet. In this paper, we establish a number of novel characterizations for the program expressive power of several important existential rule languages, including tuple-generating dependencies (TGDs), linear TGDs, as well as disjunctive TGDs. The characterizations employ natural model-theoretic properties, and automata-theoretic properties sometimes, which thus provide powerful tools for identifying the definability of domain knowledge for OMQA in these languages.