Let's Play Tag: Linear Time Evaluation of Conjunctive Queries under TGD Constraints
This work addresses efficiency in database query evaluation under constraints, which is incremental as it extends existing dichotomies to constrained settings for specific cases.
The paper tackles the problem of evaluating conjunctive queries under tuple-generating dependency (TGD) constraints in linear time, focusing on modes like single-testing and counting. It proposes an approach that lifts known dichotomies from unconstrained settings for specific TGD classes, such as non-recursive sets with binary heads or frontier-guarded full TGDs, but notes challenges for enumeration and less restrictive classes.
We study the limits of linear time evaluation of conjunctive queries under constraints expressed as tuple-generating dependencies (TGDs), across several modes of query evaluation: single-testing, all-testing, counting, lexicographic direct access, and enumeration. While full classifications seem far beyond reach, we propose an approach that, for some evaluation modes and classes of TGDs, makes it possible to lift known dichotomies from the unconstrained setting. In particular, our approach applies to all mentioned evaluation modes except enumeration, when the constraints fall into one of two classes: non-recursive sets of TGDs in which every TGD uses at most binary relation symbols in the head or has at most two frontier variables; and frontier-guarded full TGDs. We further provide a collection of examples showcasing the challenges that arise for enumeration and for less restrictive classes of TGDs.