Content deleted Content added
m Open access bot: arxiv updated in citation with #oabot. |
m Open access bot: arxiv updated in citation with #oabot. |
||
| (One intermediate revision by the same user not shown) | |||
Line 4:
A '''worst-case optimal join algorithm''' is an [[algorithm]] for computing [[Join (SQL)|relational joins]] with a runtime that is bounded by the [[Worst-case complexity|worst-case]] output size of the join. Traditional ''binary join'' algorithms such as [[hash join]] operate over two relations at a time; joins between more than two relations are implemented by repeatedly applying binary joins. Worst-case optimal join algorithms are asymptotically faster in worst case than any join algorithm based on such iterated binary joins.
The first worst-case optimal join algorithm, ''generic join'', was published in 2012.<ref>{{Cite arXiv |last1=Ngo |first1=Hung Q. |last2=Porat |first2=Ely |last3=Ré |first3=Christopher |last4=Rudra |first4=Atri |date=2012-03-08 |title=Worst-case Optimal Join Algorithms |class=cs.DB |eprint=1203.1952 }}</ref> Worst-case optimal join algorithms have been implemented in commercial database systems, including the [[LogicBlox|LogicBlox system]].<ref>{{Cite arXiv |last=Veldhuizen |first=Todd L. |date=2013-12-20 |title=Leapfrog Triejoin: a worst-case optimal join algorithm |class=cs.DB |eprint=1210.0481 }}</ref><ref>{{Cite journal |last1=Freitag |first1=Michael |last2=Bandle |first2=Maximilian |last3=Schmidt |first3=Tobias |last4=Kemper |first4=Alfons |last5=Neumann |first5=Thomas |date=2020-07-01 |title=Adopting worst-case optimal joins in relational database systems |url=https://doi.org/10.14778/3407790.3407797 |journal=Proceedings of the VLDB Endowment |volume=13 |issue=12 |pages=1891–1904 |doi=10.14778/3407790.3407797 |s2cid=221115321 |issn=2150-8097|url-access=subscription }}</ref> Worst-case optimal joins have been applied to build a worst-case optimal algorithm for [[e-matching]].<ref>{{Cite journal |last1=Zhang |first1=Yihong |last2=Wang |first2=Yisu Remy |last3=Willsey |first3=Max |last4=Tatlock |first4=Zachary |date=2022-01-12 |title=Relational e-matching |journal=Proceedings of the ACM on Programming Languages |volume=6 |issue=POPL |pages=35:1–35:22 |doi=10.1145/3498696|s2cid=236924583 |doi-access=free |arxiv=2108.02290 }}</ref>
== References ==
Line 11:
=== Sources ===
*{{Cite journal |last1=Ngo |first1=Hung Q. |last2=Porat |first2=Ely |last3=Ré |first3=Christopher |last4=Rudra |first4=Atri |date=2018-03-13 |title=Worst-case Optimal Join Algorithms |url=https://doi.org/10.1145/3180143 |journal=Journal of the ACM |volume=65 |issue=3 |pages=16:1–16:40 |doi=10.1145/3180143 |issn=0004-5411|arxiv=1203.1952 }}
*{{Cite journal |last1=Ngo |first1=Hung Q |last2=Ré |first2=Christopher |last3=Rudra |first3=Atri |date=2014-02-28 |title=Skew strikes back: new developments in the theory of join algorithms |url=https://doi.org/10.1145/2590989.2590991 |journal=ACM SIGMOD Record |volume=42 |issue=4 |pages=5–16 |doi=10.1145/2590989.2590991 |s2cid=6384477 |issn=0163-5808|url-access=subscription }}
== External links ==
| |||