Split Theorems for Join Reporting and Sampling
Abstract
The box-tree technique is an elegant and powerful tool for natural join processing. Recently developed by the database theory community, it yields simple algorithms and data structures for solving three fundamental problems - join reporting, small-delay enumeration, and join sampling - with performance matching the best known bounds, up to polylogarithmic factors. This article presents the technique's theoretical foundation in a form accessible to the broader database community. At the core of this foundation are the so-called split theorems, which uncover a combinatorial and intrinsically geometric structure underlying natural joins. Two versions of these theorems are proved using elementary, self-contained arguments.
Fields of Study & Subjects
Advanced Database Systems and Queries
Data Quality and Management
Data Management and Algorithms
Publication details
- Journal / source
- ACM SIGMOD Record
- Publisher
- Association for Computing Machinery (ACM)
- Volume
- 54
- Issue
- 4
- Pages
- 7–18
- Publication date
- 19 January 2026
- Language
- EN