Let's Play Tag: Linear Time Evaluation of Conjunctive Queries under TGD Constraints

Nofar Carmeli, Carsten Lutz, Marcin Przybyłko

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:…