# Non-Uniformly Terminating Chase: Size and Complexity

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning benchmarks and evaluation, one of 17 directions in LLM reasoning.
- Builds on 6 of its 40 references that are in the map.
- First posted on arXiv 22 Apr 2022.

## Placed in

- LLM reasoning / [Reasoning benchmarks and evaluation](https://mlsanity.com/lr/reasoning-benchmarks-and-evaluation/)

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

- [Anatomy of the chase](https://mlsanity.com/paper/1303.6682/) (2013)
- [A Single Approach to Decide Chase Termination on Linear Existential Rules](https://mlsanity.com/paper/1810.02132/) (2018)
- [All-Instances Restricted Chase Termination](https://mlsanity.com/paper/1901.03897/) (2019)
- [The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs](https://mlsanity.com/paper/1912.12442/) (2019)
- [Oblivious and Semi-Oblivious Boundedness for Existential Rules](https://mlsanity.com/paper/2006.08467/) (2020)
- [When Can We Answer Queries Using Result-Bounded Data Interfaces?](https://mlsanity.com/paper/1706.07936/) (2017)

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

- [Semi-Oblivious Chase Termination for Linear Existential Rules: An Experimental Study](https://mlsanity.com/paper/2303.12851/) (2023)

## Abstract (arXiv)

The chase procedure, originally introduced for checking implication of database constraints, and later on used for computing data exchange solutions, has recently become a central algorithmic tool in rule-based ontological reasoning. In this context, a key problem is non-uniform chase termination: does the chase of a database w.r.t. a rule-based ontology terminate? And if this is the case, what is the size of the result of the chase? We focus on guarded tuple-generating dependencies (TGDs), which form a robust rule-based ontology language, and study the above central questions for the semi-oblivious version of the chase. One of our main findings is that non-uniform semi-oblivious chase termination for guarded TGDs is feasible in polynomial time w.r.t. the database, and the size of the result of the chase (whenever is finite) is linear w.r.t. the database. Towards our results concerning non-uniform chase termination, we show that basic techniques such as simplification and linearization, originally introduced in the context of ontological query answering, can be safely applied to the chase termination problem.