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.ICDT.2020.21
URN: urn:nbn:de:0030-drops-119453
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11945/
Go to the corresponding LIPIcs Volume Portal

Navarro, Gonzalo ; Reutter, Juan L. ; Rojas-Ledesma, Javiel

Optimal Joins Using Compact Data Structures

pdf-format:
LIPIcs-ICDT-2020-21.pdf (1 MB)

Abstract

Worst-case optimal join algorithms have gained a lot of attention in the database literature. We now count with several algorithms that are optimal in the worst case, and many of them have been implemented and validated in practice. However, the implementation of these algorithms often requires an enhanced indexing structure: to achieve optimality we either need to build completely new indexes, or we must populate the database with several instantiations of indexes such as B+-trees. Either way, this means spending an extra amount of storage space that may be non-negligible.
We show that optimal algorithms can be obtained directly from a representation that regards the relations as point sets in variable-dimensional grids, without the need of extra storage. Our representation is a compact quadtree for the static indexes, and a dynamic quadtree sharing subtrees (which we dub a qdag) for intermediate results. We develop a compositional algorithm to process full join queries under this representation, and show that the running time of this algorithm is worst-case optimal in data complexity. Remarkably, we can extend our framework to evaluate more expressive queries from relational algebra by introducing a lazy version of qdags (lqdags). Once again, we can show that the running time of our algorithms is worst-case optimal.

BibTeX - Entry

@InProceedings{navarro_et_al:LIPIcs:2020:11945,
  author =	{Gonzalo Navarro and Juan L. Reutter and Javiel Rojas-Ledesma},
  title =	{{Optimal Joins Using Compact Data Structures}},
  booktitle =	{23rd International Conference on Database Theory (ICDT 2020)},
  pages =	{21:1--21:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-139-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{155},
  editor =	{Carsten Lutz and Jean Christoph Jung},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11945},
  URN =		{urn:nbn:de:0030-drops-119453},
  doi =		{10.4230/LIPIcs.ICDT.2020.21},
  annote =	{Keywords: Join algorithms, Compact data structures, Quadtrees, AGM bound}
}

Keywords: Join algorithms, Compact data structures, Quadtrees, AGM bound
Collection: 23rd International Conference on Database Theory (ICDT 2020)
Issue Date: 2020
Date of publication: 11.03.2020
Supplementary Material: Video of the Presentation: https://doi.org/10.5446/46823

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