2026-08-10T22:32:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25623 2026-06-23T12:03:59Z ddc:004 open_access

Acyclic Join Sampling Under Selections: Dichotomy, Union Sampling, and Enumeration Huang, Jinchao Tao, Yufei Wang, Sibo Conjunctive Queries Acyclic Joins Sampling Lower Bounds Previous research on join sampling has focused on joins without selection conditions, even though such conditions are prevalent in everyday queries in database systems. Motivated by this, we undertake a systematic investigation on the complexity of sampling from the result of an acyclic join under equality conditions given only at runtime. When conditions are conjunctive, the goal is to understand when it is possible to precompute a feasible structure that uses Õ(IN) space and supports sampling in Õ(1) time, where IN is the input size. We present a dichotomy to characterize (subject to a widely-accepted conjecture) the existence of such structures based on the conditions supplied and, in every feasible scenario, give an optimal structure of O(IN) space and O(1) sample time. We then extend our investigation to conditions expressed in disjunctive normal form, where the core challenge reduces to the fundamental set union sampling problem. We overcome the challenge with an optimal algorithm and utilize it to develop optimal sampling structures. Our findings also lead to new results on the closely-related random enumeration problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jinchao Huang and Yufei Tao and Sibo Wang 2026 Is Part Of LIPIcs, Volume 365, 29th International Conference on Database Theory (ICDT 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2026.9 urn:nbn:de:0030-drops-256231 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2026.9 eng https://creativecommons.org/licenses/by/4.0/legalcode