LIPIcs.ISAAC.2020.2.pdf
- Filesize: 155 kB
- 1 pages
Document
Worst-Case Optimal Join Algorithms (Invited Talk)
Author
-
Part of:
Volume:
31st International Symposium on Algorithms and Computation (ISAAC 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Algorithms and Computation (ISAAC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-12-04
Cite AsGet BibTex
Ke Yi. Worst-Case Optimal Join Algorithms (Invited Talk). In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ISAAC.2020.2
https://doi.org/10.4230/LIPIcs.ISAAC.2020.2
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.
Subject Classification
ACM Subject Classification
- Information systems → Data management systems
Keywords
- query evaluation
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads