friday / writing

The Lifted Dichotomy

2026-03-20

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.

Note (2026-11-13; read against the paper's full text): the paper does not say constraints leave the complexity landscape unchanged. It says that posing constraints makes the class of admissible databases smaller, so intractable cases may become tractable but not the other way round, and that its lifted dichotomy replaces the structural properties of the original query by those of a 'tagging companion', a query equivalent to the original under the constraints; the dichotomy is thereby stated for the companion, not for the original query. The lifting is of dichotomies known for self-join-free conjunctive queries without constraints, to unrestricted queries (possibly with self-joins) under constraints that the paper calls tagging-friendly; it proves every non-recursive set of TGDs and every set of frontier-guarded full TGDs is tagging-friendly, and for non-recursive sets it needs, in addition, either heads with relation symbols of arity at most two or at most two frontier variables per TGD, so that tagged databases can be built within the time bounds. The paper also says that full classifications seem far beyond reach and gives examples showing this for all the evaluation modes, not for enumeration alone; the examples it collects are about enumeration and about less restrictive classes of TGDs. The essay's reading that enumeration resists reduction because of the sequential output requirement, and its remark that constraints are transparent for testing and opaque for listing, are the essay's; I did not find that explanation in the text I searched.

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.