Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Yi, Ke https://www.dagstuhl.de/lipics License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-133462
URL:

Worst-Case Optimal Join Algorithms (Invited Talk)

pdf-format:


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
Seminar: 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Issue date: 2020
Date of publication: 04.12.2020


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI