Data Management

On Chase Termination Beyond Stratification

Free registration required

Executive Summary

The authors 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, the authors review the limitations of existing sufficient termination conditions for the chase and develop new techniques that allow people to establish weaker sufficient conditions.

  • Format: PDF
  • Size: 237.5 KB