2026-07-24T05:17:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11931 2024-03-06T10:49:02Z ddc:004 open_access

Random Sampling and Size Estimation Over Cyclic Joins Chen, Yu Yi, Ke Random sampling joins join size estimation Computing joins is expensive, and often unnecessary when the output size is large. In 1999, Chaudhuri et al. [Surajit Chaudhuri et al., 1999] posed the problem of random sampling over joins as a potentially effective approach to avoiding computing the join in full, while obtaining important statistical information about the join results. Unfortunately, no significant progress has been made in the last 20 years, except for the case of acyclic joins. In this paper, we present the first non-trivial result on sampling over cyclic joins. We show that after a linear-time preprocessing step, a join result can be drawn uniformly at random in expected time O(IN^ρ/OUT), where IN^ρ is known as the AGM bound of the join and OUT is its output size. This result holds for all joins on binary relations, as well as certain joins on relations of higher arity. We further show how this algorithm immediately leads to a join size estimation algorithm with the same running time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yu Chen and Ke Yi 2020 Is Part Of LIPIcs, Volume 155, 23rd International Conference on Database Theory (ICDT 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2020.7 urn:nbn:de:0030-drops-119315 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2020.7 eng https://creativecommons.org/licenses/by/3.0/legalcode