A simple algorithm for worst case optimal join and sampling

DOI10.4230/LIPICS.ICDT.2025.23MaRDI QIDQ7292791zbMATH OpenFDO

Authors Florent Capelli, Oliver Irwin, S. Salvati

Publication date 8 July 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICDT.2025.23

Mathematics Subject Classification ID

Database theory (68P15)

Cites work

• Applications of information inequalities to database theory problems
• Constraint solving via fractional edge covers
• Hypergraphs, entropy, and inequalities
• Join sampling under acyclic degree constraints and (cyclic) subgraph sampling
• Perfect hashing
• Random Sampling and Size Estimation Over Cyclic Joins.
• Sampling the Leaves of a Tree with Equal Probabilities
• Size bounds and query plans for relational joins
• Worst-case optimal join algorithms

This page was built for publication: A simple algorithm for worst case optimal join and sampling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7292791)