Content deleted Content added
m Open access bot: url-access updated in citation with #oabot. |
m Open access bot: arxiv updated in citation with #oabot. |
||
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 ==
| |||