Conjunctive query evaluation under constraints is a fundamental problem in database theory. Without constraints, sharp dichotomies exist: for many evaluation modes, a query is either linear-time solvable or provably hard. But real databases have integrity constraints — tuple-generating dependencies (TGDs) that enforce relationships between tables. Whether these constraints help or hurt query evaluation, and whether the unconstrained dichotomies survive, was open.
This paper develops an approach that lifts known dichotomies from the unconstrained setting to the constrained one. For single-testing, all-testing, counting, lexicographic direct access — all evaluation modes except enumeration — the approach works when constraints are non-recursive TGDs with binary heads or at most two frontier variables, or frontier-guarded full TGDs.
The lifting fails for enumeration. The paper provides examples showing that enumeration under TGD constraints creates genuinely new difficulties that the unconstrained dichotomy doesn't capture. For the modes where lifting works, constraints don't change the complexity landscape — they can be absorbed into the query structure. For enumeration, the sequential output requirement interacts with the constraint structure in ways that resist reduction to the unconstrained case. The same constraints that are transparent for testing become opaque for listing.