Database schemas are rarely just passive blueprints for tables; they are rich systems of rules, constraints, and dependencies. When we state that "every department must have a manager" or "two records with the same tax ID must belong to the same person," we are defining logical dependencies.
But how do we actually reason about these rules computationally? If we have a complex set of dependencies, how can we prove that one rule logically implies another, or that a query will never return any results because its requirements contradict the schema?
The answer across much of database theory is the chase procedure. The chase is an elegant, iterative algorithmic mechanism that acts as a logical simulator. It takes an initial data structure—such as a database instance, a query graph, or a symbolic tableau—and systematically applies schema rules to "fix" violations. By repeatedly firing these rules until no more changes can be made, the chase constructs a stable, fully expanded state (a fixpoint) that makes all implicit logical consequences explicit.
The Core Mechanism: Iterative Fixpoint Generation
To understand why the chase works, imagine a game of logical dominoes. We begin with an initial state that represents our starting knowledge. We then scan our set of dependencies to find any rule that is violated.
There are two primary ways to resolve a violation depending on the type of rule:
- Generation: If a rule dictates that the presence of certain data implies the existence of other data (a tuple-generating dependency, or TGD), the chase generates new symbolic facts to satisfy the rule.
- Equivalence: If a rule dictates that two values must be identical (an equality-generating dependency, or EGD), the chase equates or merges those values.
Each modification can trigger new violations downstream. The chase process repeats this cycle iteratively. If the process successfully runs out of violations, it terminates in a unique final state known as a universal model. If it hits an unresolvable contradiction (such as trying to equate two distinct constant values), the chase fails, signaling a logical impossibility.
The foundational power of this technique spans multiple paradigms. For instance, S. K. Michael Wong in Testing Implication of Probabilistic Dependencies adapted the chase to test the logical implications of probabilistic dependencies, demonstrating that iteratively applying inference rules yields a unique final state due to its finite Church-Rosser property. To handle more complex relational architectures, Attila Kiss et al. developed a generalized chase procedure in On a general class of data dependencies in the relational model and its implication problems that extends dependency reasoning to multi-relation database schemes.
Unfolding Queries and Proving Containment
One of the most powerful applications of the chase is in query optimization and verification. Instead of running the chase on a massive physical database, we can run it symbolically on a query itself.
By treating the conditions of a query as a symbolic database instance (often represented as a constraint graph or a tableau), we can use the chase to unfold the implicit requirements imposed by the schema.
[Initial Query Graph]
│
▼ (Apply Schema Constraints Iteratively)
[Chased Query Graph] ──► Detect Contradictions? ──► Unsatisfiable
│
▼ (No Contradictions)
[Universal Plan / Expanded Query]
This approach is highly effective for detecting whether a query is fundamentally broken or redundant:
- Satisfiability: In On Testing Satisfiability of Tree Pattern Queries, Ganesh Ramesh et al. showed that representing tree pattern queries as constraint graphs and applying a chase procedure allows systems to systematically uncover hidden contradictions. If the chase encounters an inconsistency, the query is proven to be unsatisfiable, saving significant execution costs.
- Containment: To determine if the results of Query A will always be a subset of Query B under a given schema, we can chase Query A and see if Query B can map into the resulting structure. For example, G. Serfiotis et al. in Containment and Minimization of RDF/S Query Patterns utilized the chase to expand queries into a "universal plan" by iteratively applying schema constraints, providing a rigorous method to prune redundant query paths and verify containment.
- View Design: This capability is crucial when balancing data utility and privacy. Efthymia Tsamoura et al. in Balancing Expressiveness and Inexpressiveness in View Design employed the chase to formally verify whether a specific database view configuration exposes enough information to answer authorized queries while safely concealing sensitive data.
Resolving Conflicts and Repairing Dirty Data
The chase is not limited to abstract logical verification; it serves as a foundational framework for data cleaning and entity resolution. When real-world data is integrated, it frequently violates integrity constraints. The chase offers a principled way to transform "dirty" data into a compliant state.
In Uniform Dependency Language for Improving Data Quality, Wenfei Fan et al. demonstrated that many specialized data-repairing algorithms are actually concrete implementations of a generalized chase mechanism. Instead of merely generating missing records, the process utilizes "fixing functions" to systematically modify inconsistent records until they satisfy defined quality dependencies.
A clear example of this mechanism occurs when handling matching dependencies (MDs), which dictate when distinct records refer to the same real-world entity. As articulated by Leopoldo E. Bertossi et al. in Data Cleaning and Query Answering with Matching Dependencies and Matching Functions, pairing MDs with explicit matching functions allows the system to resolve data conflicts iteratively.
The chase-like procedure repeatedly applies these merging functions to conflicting records until the database reaches a stable, clean state. In Data Cleaning and Query Answering with Matching Dependencies and Matching Functions, the authors further extended this framework to compute certain and possible answers over dirty data, ensuring semantic consistency even when multiple clean database states are reachable.
Managing Existential Rules and Non-Termination
As schemas become more expressive, the chase faces a critical theoretical hurdle: termination. When a schema includes existential rules—rules stating that a condition implies the existence of an un-named entity—the chase can potentially generate a new symbolic value, which then triggers another rule, creating an infinite loop.
Rule: Every Person has a Parent (who is also a Person).
Initial Data: Person(Alice)
Chase Step 1: Person(Alice) ──► Generates Person(Parent_1)
Chase Step 2: Person(Parent_1) ──► Generates Person(Parent_2)
Chase Step 3: Person(Parent_2) ──► Generates Person(Parent_3) ... (Infinite Loop)
Managing this infinite expansion while preserving logical correctness is a central focus of modern database research. In Monotone Rewritability and the Analysis of Queries, Views, and Rules, Stanislav Kikot et al. observed that even simple existential rules can transform a decidable query-answering problem into an undecidable one, using the chase as a tool to map out these complex data dependencies.
To keep query answering computationally tractable under these conditions, the chase is often adapted to rewrite queries into well-behaved logical fragments rather than generating infinite models. For instance, Vince Bárány et al. in Some Model Theory of Guarded Negation adapted the standard chase construction to inductively generate facts under tuple-generating dependencies, allowing queries to be safely rewritten into the Guarded Negation Fragment of first-order logic.
The chase also proves essential when dealing with incomplete or hidden data. In Querying Visible and Invisible Information, Gabriele Puppis et al. introduced a modified chase procedure that systematically derives logical consequences from a combination of explicit visible data and integrity constraints, generating a tree structure of possible database instances to track how information propagates through a schema.
This tracking mirrors the challenges found in data integration systems. As shown by Andrea Calì et al. in Query rewriting and answering under constraints in data integration systems, systems can use iterative inclusion dependency expansion to modify incoming queries. This ensures that the query planner automatically accounts for all distributed source relations that could logically contribute to the final answer, guaranteeing completeness under global schema constraints.
Key Foundational Work
On a general class of data dependencies in the relational model and its implication problems (1991) — contributed 4 concept elements to this direction.
Testing Implication of Probabilistic Dependencies (1996) — contributed 1 concept elements to this direction.