Partition Constraints for Conjunctive Queries: Bounds and Worst-Case Optimal Joins (Best Paper & Best Student Paper)
Published in ICDT 2025, 2025
This paper proposes a new statistic on relations that can be used to produce asymptotically tighter bounds on output size and runtime. Further, it provides algorithms for computing such statistics and worst-case optimal join algorithms for these new bounds.
Recommended citation: Kyle Deeds and Timo Camillo Merkl. Partition Constraints for Conjunctive Queries: Bounds and Worst-Case Optimal Joins. In 28th International Conference on Database Theory (ICDT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 328, pp. 17:1-17:18
Recommended citation: Kyle Deeds and Timo Camillo Merkl. Partition Constraints for Conjunctive Queries: Bounds and Worst-Case Optimal Joins. In 28th International Conference on Database Theory (ICDT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 328, pp. 17:1-17:18
Download Paper