Computer Science – Databases
Scientific paper
2009-06-23
Computer Science
Databases
Technical Report of VLDB 2009 conference version
Scientific paper
We study the termination problem of the chase algorithm, a central tool in various database problems such as the constraint implication problem, Conjunctive Query optimization, rewriting queries using views, data exchange, and data integration. The basic idea of the chase is, given a database instance and a set of constraints as input, to fix constraint violations in the database instance. It is well-known that, for an arbitrary set of constraints, the chase does not necessarily terminate (in general, it is even undecidable if it does or not). Addressing this issue, we review the limitations of existing sufficient termination conditions for the chase and develop new techniques that allow us to establish weaker sufficient conditions. In particular, we introduce two novel termination conditions called safety and inductive restriction, and use them to define the so-called T-hierarchy of termination conditions. We then study the interrelations of our termination conditions with previous conditions and the complexity of checking our conditions. This analysis leads to an algorithm that checks membership in a level of the T-hierarchy and accounts for the complexity of termination conditions. As another contribution, we study the problem of data-dependent chase termination and present sufficient termination conditions w.r.t. fixed instances. They might guarantee termination although the chase does not terminate in the general case. As an application of our techniques beyond those already mentioned, we transfer our results into the field of query answering over knowledge bases where the chase on the underlying database may not terminate, making existing algorithms applicable to broader classes of constraints.
Lausen Georg
Meier Michael
Schmidt Michael
No associations
LandOfFree
On Chase Termination Beyond Stratification does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Chase Termination Beyond Stratification, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Chase Termination Beyond Stratification will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-708342