Chasing constrained tuple-generating dependencies.
Michael J. Maher and Divesh Srivastava.
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 for such
constraint domains, and can be used as a weak implication
procedure for other constraint domains. We describe the
conditions under which the chase procedures can be terminated
early without weakening them. We develop a form of magic
sets optimization for making the chase procedures for CTGDs
goal-directed; this is the first such use of magic sets in
chase procedures.