← All papers
First page of The Chase in Lean -- Crafting a Formal Library for Existential Rule Research

The Chase in Lean -- Crafting a Formal Library for Existential Rule Research

Lukas Gerlach

cs.LO Apr 24, 2026 · v1
Crafts a Lean formal library for the chase algorithm over existential rules.
The chase is a sound, complete, but possibly non-terminating algorithm for reasoning with existential rules (aka. tuple-generating dependencies), a highly expressive knowledge representation language. Although the procedure appears simple, research on theoretical properties and optimization for practical implementations has grown to a point where verifying correctness and reproducing proofs becomes challenging and intuition can sometimes be misleading. Lean is a purely functional programming language and interactive theorem prover whose community actively develops formal libraries for mathematics (Mathlib) and computer science (CSLib). In this work, we present our own endeavor of crafting a Lean framework around existential rules and the chase. We discuss design decisions concerning the nuances of chase definitions commonly found in the literature and show how these translate into Lean. To illustrate the framework's capabilities using known results, we show that the result of a chase is a universal model and outline the formalization for proving that without so-called "alternative matches" it is even a core. Beyond existing literature, we unify sufficient chase termination conditions in the likeness of Model-Faithful Acyclicity (MFA) into a common framework while also adding support for constants in rules.

The chase algorithm for reasoning with existential rules is simple in description but has grown complex enough that verifying correctness and reproducing proofs of its properties has become challenging, and intuition can be misleading.

The authors build a formal library in Lean for existential rule research, modeling the chase as a coinductive structure. They formalize terms, atoms, rules, triggers, obsolescence conditions, and chase trees. The formalization uses Skolem terms instead of labelled nulls and models the chase generically over any obsolescence condition.

The formalization proves that chase trees yield universal model sets and that avoiding alternative matches on deterministic rules produces cores. The library is generic enough to support both the Skolem and restricted chase variants, and all results are verified in Lean.