A Simple Algorithm for Worst-Case Optimal Join and Sampling
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929509648826368 |
|---|---|
| author | Capelli, Florent Irwin, Oliver Salvati, Sylvain |
| author_facet | Capelli, Florent Irwin, Oliver Salvati, Sylvain |
| contents | We present an elementary branch and bound algorithm with a simple analysis of why it achieves worstcase optimality for join queries on classes of databases defined respectively by cardinality or acyclic degree constraints. We then show that if one is given a reasonable way for recursively estimating upper bounds on the number of answers of the join queries, our algorithm can be turned into algorithm for uniformly sampling answers with expected running time $O(UP/OUT)$ where $UP$ is the upper bound, $OUT$ is the actual number of answers and $O(\cdot)$ ignores polylogarithmic factors. Our approach recovers recent results on worstcase optimal join algorithm and sampling in a modular, clean and elementary way. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_14094 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Simple Algorithm for Worst-Case Optimal Join and Sampling Capelli, Florent Irwin, Oliver Salvati, Sylvain Databases We present an elementary branch and bound algorithm with a simple analysis of why it achieves worstcase optimality for join queries on classes of databases defined respectively by cardinality or acyclic degree constraints. We then show that if one is given a reasonable way for recursively estimating upper bounds on the number of answers of the join queries, our algorithm can be turned into algorithm for uniformly sampling answers with expected running time $O(UP/OUT)$ where $UP$ is the upper bound, $OUT$ is the actual number of answers and $O(\cdot)$ ignores polylogarithmic factors. Our approach recovers recent results on worstcase optimal join algorithm and sampling in a modular, clean and elementary way. |
| title | A Simple Algorithm for Worst-Case Optimal Join and Sampling |
| topic | Databases |
| url | https://arxiv.org/abs/2409.14094 |