Paper
Let's Play Tag: Linear Time Evaluation of Conjunctive Queries under TGD Constraints
Authors
Nofar Carmeli, Carsten Lutz, Marcin Przybyłko
Abstract
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.
Metadata
Related papers
Fractal universe and quantum gravity made simple
Fabio Briscese, Gianluca Calcagni • 2026-03-25
POLY-SIM: Polyglot Speaker Identification with Missing Modality Grand Challenge 2026 Evaluation Plan
Marta Moscati, Muhammad Saad Saeed, Marina Zanoni, Mubashir Noman, Rohan Kuma... • 2026-03-25
LensWalk: Agentic Video Understanding by Planning How You See in Videos
Keliang Li, Yansong Li, Hongze Shen, Mengdi Liu, Hong Chang, Shiguang Shan • 2026-03-25
Orientation Reconstruction of Proteins using Coulomb Explosions
Tomas André, Alfredo Bellisario, Nicusor Timneanu, Carl Caleman • 2026-03-25
The role of spatial context and multitask learning in the detection of organic and conventional farming systems based on Sentinel-2 time series
Jan Hemmerling, Marcel Schwieder, Philippe Rufin, Leon-Friedrich Thomas, Mire... • 2026-03-25
Raw Data (Debug)
{
"raw_xml": "<entry>\n <id>http://arxiv.org/abs/2603.18709v1</id>\n <title>Let's Play Tag: Linear Time Evaluation of Conjunctive Queries under TGD Constraints</title>\n <updated>2026-03-19T10:09:17Z</updated>\n <link href='https://arxiv.org/abs/2603.18709v1' rel='alternate' type='text/html'/>\n <link href='https://arxiv.org/pdf/2603.18709v1' rel='related' title='pdf' type='application/pdf'/>\n <summary>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.</summary>\n <category scheme='http://arxiv.org/schemas/atom' term='cs.DB'/>\n <published>2026-03-19T10:09:17Z</published>\n <arxiv:primary_category term='cs.DB'/>\n <author>\n <name>Nofar Carmeli</name>\n </author>\n <author>\n <name>Carsten Lutz</name>\n </author>\n <author>\n <name>Marcin Przybyłko</name>\n </author>\n </entry>"
}