License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2020.2
URN: urn:nbn:de:0030-drops-133462
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13346/
Yi, Ke
Worst-Case Optimal Join Algorithms (Invited Talk)
Abstract
Join is the most important operator in relational databases, and remains the most expensive one despite years of research and engineering efforts. Following the ground-breaking work of Atserias, Grohe, and Marx in 2008, worst-case optimal join algorithms have been discovered, which has led to not only a series of beautiful theoretical results, but also new database systems based on drastically different query evaluation techniques. In this talk, I will present an overview of this topic, including algorithms in various computation models (sequential and parallel), variants of the problem (full, Boolean, and counting), and approximate solutions.
BibTeX - Entry
@InProceedings{yi:LIPIcs:2020:13346,
author = {Ke Yi},
title = {{Worst-Case Optimal Join Algorithms (Invited Talk)}},
booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)},
pages = {2:1--2:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-173-3},
ISSN = {1868-8969},
year = {2020},
volume = {181},
editor = {Yixin Cao and Siu-Wing Cheng and Minming Li},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13346},
URN = {urn:nbn:de:0030-drops-133462},
doi = {10.4230/LIPIcs.ISAAC.2020.2},
annote = {Keywords: query evaluation}
}
|
Keywords: |
|
query evaluation |
|
Collection: |
|
31st International Symposium on Algorithms and Computation (ISAAC 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
04.12.2020 |
