Restricted Chase Termination: You Want More than Fairness

The chase is a fundamental algorithm with ubiquitous uses in database theory. Given a database and a set of existential rules (aka tuple-generating dependencies), it iteratively extends the database to ensure that the rules are satisfied in a most general way. This process may not terminate, and a major problem is to decide whether it does. This problem has been studied for a large number of chase variants, which differ by the conditions under which a rule is applied to extend the database. Surprisingly, the complexity of the universal termination of the restricted (aka standard) chase is not fully understood. We close this gap by placing universal restricted chase termination in the analytical hierarchy. This higher hardness is due to the fairness condition, and we propose an alternative condition to reduce the hardness of universal termination.

Authors

Institutions

Publication Details

Journal
Proceedings of the ACM on Management of Data
Published
2025-06-09
DOI
https://doi.org/10.1145/3725246
Primary Topic
Advanced Database Systems and Queries
Type
article
Field-Weighted Citation Impact
0.00

Funders

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Restricted Chase Termination: You Want More than Fairness

Michaël Thomazo, Lucas Larroque, David Carral, Lukas Gerlach
Proceedings of the ACM on Management of Data
Advanced Database Systems and Queries
article

Restricted Chase Termination: You Want More than Fairness

Michaël Thomazo, Lucas Larroque, David Carral, Lukas Gerlach
article en

Abstract

The chase is a fundamental algorithm with ubiquitous uses in database theory. Given a database and a set of existential rules (aka tuple-generating dependencies), it iteratively extends the database to ensure that the rules are satisfied in a most general way. This process may not terminate, and a major problem is to decide whether it does. This problem has been studied for a large number of chase variants, which differ by the conditions under which a rule is applied to extend the database. Surprisingly, the complexity of the universal termination of the restricted (aka standard) chase is not fully understood. We close this gap by placing universal restricted chase termination in the analytical hierarchy. This higher hardness is due to the fairness condition, and we propose an alternative condition to reduce the hardness of universal termination.

Proceedings of the ACM on Management of DataVol. 3(2)
Centre National de la Recherche Scientifique (FR), Institut national de recherche en sciences et technologies du numérique (FR), Université de Montpellier (FR), Université Paris Sciences et Lettres (FR), École Normale Supérieure - PSL (FR), Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier (FR), Technische Universität Dresden (DE)
Deutscher Akademischer Austauschdienst, Deutsche Forschungsgemeinschaft, Bundesministerium für Bildung und Forschung, Technische Universität Dresden
Peace, Justice and strong institutions
Openalex Percentile: Top 87%
Advanced Database Systems and Queries
DOIOpen Access PDFOpenAlex
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Restricted Chase Termination: You Want More than Fairness — Michaël Thomazo, Lucas Larroque, et al. · Proceedings of the ACM on Management of Data (2025) | TGRS Research Map | TGRS