Partition Constraints for Conjunctive Queries: Bounds and Worst-Case Optimal Joins
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916559572697088 |
|---|---|
| author | Deeds, Kyle Merkl, Timo Camillo |
| author_facet | Deeds, Kyle Merkl, Timo Camillo |
| contents | In the last decade, various works have used statistics on relations to improve both the theory and practice of conjunctive query execution. Starting with the AGM bound which took advantage of relation sizes, later works incorporated statistics like functional dependencies and degree constraints. Each new statistic prompted work along two lines; bounding the size of conjunctive query outputs and worst-case optimal join algorithms. In this work, we continue in this vein by introducing a new statistic called a \emph{partition constraint}. This statistic captures latent structure within relations by partitioning them into sub-relations which each have much tighter degree constraints. We show that this approach can both refine existing cardinality bounds and improve existing worst-case optimal join algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_04190 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Partition Constraints for Conjunctive Queries: Bounds and Worst-Case Optimal Joins Deeds, Kyle Merkl, Timo Camillo Databases In the last decade, various works have used statistics on relations to improve both the theory and practice of conjunctive query execution. Starting with the AGM bound which took advantage of relation sizes, later works incorporated statistics like functional dependencies and degree constraints. Each new statistic prompted work along two lines; bounding the size of conjunctive query outputs and worst-case optimal join algorithms. In this work, we continue in this vein by introducing a new statistic called a \emph{partition constraint}. This statistic captures latent structure within relations by partitioning them into sub-relations which each have much tighter degree constraints. We show that this approach can both refine existing cardinality bounds and improve existing worst-case optimal join algorithms. |
| title | Partition Constraints for Conjunctive Queries: Bounds and Worst-Case Optimal Joins |
| topic | Databases |
| url | https://arxiv.org/abs/2501.04190 |