Chase (algorithm)¶

Rule-saturation procedure for reasoning about relational data dependencies.

Version: v1 · 2026-09-28 · History
Domain-specific #: 8421
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomains: Relational Databases, Database Theory → Computer Science & Software Engineering
Aliases: Database chase, Chase procedure

Core Idea¶

The chase is database dependency reasoning by repeated rule application. From a relational instance or tableau, it finds an unsatisfied dependency premise, adds the tuple or equality that the rule requires, and continues until a fixed point, contradiction or appropriately qualified stopping state. The result can test dependency implication or lossless decomposition and can construct data-exchange or cleaning outcomes.

The canonical tableau calculation demonstrates why an equality dependency can turn a projection row into an all-distinguished row. LLUNATIC demonstrates a published implemented chase engine for tgds and egds. Neither case licenses a claim that every dependency set terminates or every database product uses the same variant.

How would you explain it like I'm…

Keep Fixing Until Happy

Imagine a notebook of facts and a list of rules like 'if someone is in a class, they must have a teacher'. You look for a rule that isn't being followed, add whatever it says is missing, and look again. You keep going until every rule is happy, or you find two facts that can't both be true. That repeated fixing is called the chase.

Rule-Fixing Loop

Databases store facts in tables and often have rules the data should follow, called dependencies. The chase is a method that keeps checking the rules: when it finds a rule that isn't satisfied, it adds the new row or makes two values equal, exactly as the rule demands. It repeats until nothing changes, until it hits a contradiction, or until some agreed stopping point. People use it to test whether one rule follows from others, whether splitting a table loses information, and to build or clean up data.

Dependency Chase Procedure

The chase is a procedure for reasoning with database dependencies by repeated rule application. Starting from a relational instance or a tableau (a table with variables), it finds a dependency whose premise is matched but whose conclusion isn't satisfied, then adds the required tuple (for tuple-generating dependencies) or equates the required values (for equality-generating dependencies). It continues until a fixed point, a contradiction, or a qualified stopping condition. Applications include testing whether a set of dependencies implies another, checking lossless-join decomposition, and computing results for data exchange or data cleaning. It doesn't always terminate for every set of dependencies, and there are several variants.

The chase applies dependencies to a relational instance or tableau as rewrite rules: each step selects a dependency whose body is satisfied by a homomorphism but whose head is not, then either adds tuples (tgds, possibly with fresh labeled nulls) or unifies values (egds), failing if an egd forces two distinct constants equal. Iteration proceeds to a fixed point, a contradiction, or a suitably qualified stopping state. For dependency implication, one chases a tableau for the premise and checks whether the conclusion holds in the result. For lossless decomposition, the classic tableau test succeeds when equality dependencies turn some row into an all-distinguished row. The same machinery constructs solutions in data exchange and repairs in cleaning, and implemented engines such as LLUNATIC chase tgds and egds. Termination is not guaranteed for arbitrary dependency sets, and chase variants differ, so claims about termination or behavior must name the variant and the dependency class.

Scope of Application¶

This is the database-theory chase, not any recursive query or automated data edit.

Schema design. Test lossless decompositions under dependencies.
Dependency implication. Determine whether constraints force another constraint.
Data exchange. Populate targets from source-to-target rules.
Data cleaning. Find and repair constraint violations under a chosen semantics.

Clarity¶

The chase starts with relational data or a tableau, finds a dependency violation, applies the required equality or tuple step, and repeats under a named variant. A simple functional-dependency tableau proves a lossless join; LLUNATIC implements chase variants for data exchange and cleaning. No universal termination claim follows.

Manages Complexity¶

Rule saturation turns many interacting dependencies into a trace of justified local updates. The trace can certify a structural property when the variant's conditions hold; unrestricted cases can generate new witnesses indefinitely or several repair alternatives, so stopping and result semantics must be stated.

Abstract Reasoning¶

Specify state and rules, match a violated premise, apply the warranted update, iterate with an explicit stopping policy, then interpret only the conclusion that the variant supports.

Knowledge Transfer¶

Rule-saturation algorithms recur in logic and verification, but the database chase specifically operates over relational instances/tableaux and dependencies. A generic fixed-point iteration transfers the skeleton without becoming this algorithm.

Neighborhood in Abstraction Space¶

Chase (algorithm) sits in a crowded region of the domain-specific corpus (39^th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Formal Systems & Discrete Structures (18 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08