The Chase Algorithm

The chase procedure is a fundamental algorithm that has been successfully applied in a variety of database applications. Originally proposed to tackle the implication problem for data dependencies and to optimize Conjunctive Queries (CQs) under data dependencies, it has become a central tool in Semantic Query Optimization (SQO). For instance, the chase can be used to enumerate minimal CQs under a set of dependencies, thus supporting the search for more efficient query evaluation plans. Beyond SQO, the chase algorithm has been applied in many other contexts, such as data exchange, peer data exchange, data integration, query answering using views, and probabilistic databases.
The core idea of the chase algorithm is simple: given a set of dependencies (also called constraints) over a database schema and a fixed database instance as input, it fixes constraint violations in the instance.
As shown in by Deutsch, Nash and Remmel in 2008, in general it is undecidable if the chase terminates or not, even for a fixed instance. Still, addressing the issue of non-terminating chase sequences, several sufficient conditions for the input constraints have been proposed that guarantee termination on every database instance. Our work focuses on both the development of such termination conditions and on applications that can be realized if the chase terminates.

Publications

• On Chase Termination Beyond Stratification, Michael Meier, Michael Schmidt, Georg Lausen. In Proc. VLDB 2009, Lyon (France). Technical Report.
• Stop the Chase, Michael Meier, Michael Schmidt, Georg Lausen. In Proc. Alberto Mendelzon Workshop 2009, Arequipa (Peru). Technical Report.
• Foundations of SPARQL Query Optimization, Michael Schmidt, Michael Meier, Georg Lausen. Technical Report.
• Towards Rule-Based Minimization of RDF Graphs under Constraints, Michael Meier. In Proc. RR 2008, Karlsruhe (Germany).