Chasing constrained tuple-generating dependencies
Michael J. Maher, Divesh Srivastava · 1996
We investigate the implication problem for constrained tuple-generating dependencies (CTGDs), the extension of tuple- and equality-generating dependencies that permits expression of semantic relations (constraints) on variables. The implication problem is central to identifying redundant integrity constraints, checking integrity constraints on constraint databases, detecting independence of queries and updates, and optimizing queries. We provide two chase procedures for the implication problem. The first is cautious, generating tuples and constraints only when justified, whereas the second is speculative, generating tuples and constraints that have attached conditions about when they exist/hold. The cautious chase is more efficient, in some sense, but less powerful in demonstrating that a CTGD is implied. We demonstrate that, for constraint domains with Independence of Negative Constraints, the two chase procedures are equally powerful. The cautious chase is thus the chase of choice fo...