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.