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.
|Dipl.-Inf. bacc. math. Michael Meier|
|Dipl.-Inf. Michael Schmidt|
- 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).