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

Tao, Yufei

A Simple Parallel Algorithm for Natural Joins on Binary Relations

pdf-format:
LIPIcs-ICDT-2020-25.pdf (0.6 MB)

Abstract

In PODS'17, Ketsman and Suciu gave an algorithm in the MPC model for computing the result of any natural join where every input relation has two attributes. Achieving an optimal load O(m/p^{1/ρ}) - where m is the total size of the input relations, p the number of machines, and ρ the fractional edge covering number of the join - their algorithm requires 7 rounds to finish. This paper presents a simpler algorithm that ensures the same load with 3 rounds (in fact, the second round incurs only a load of O(p²) to transmit certain statistics to assist machine allocation in the last round). Our algorithm is made possible by a new theorem that provides fresh insight on the structure of the problem, and brings us closer to understanding the intrinsic reason why joins on binary relations can be settled with load O(m/p^{1/ρ}).

BibTeX - Entry

@InProceedings{tao:LIPIcs:2020:11949,
  author =	{Yufei Tao},
  title =	{{A Simple Parallel Algorithm for Natural Joins on Binary Relations}},
  booktitle =	{23rd International Conference on Database Theory (ICDT 2020)},
  pages =	{25:1--25:18},
  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/11949},
  URN =		{urn:nbn:de:0030-drops-119495},
  doi =		{10.4230/LIPIcs.ICDT.2020.25},
  annote =	{Keywords: Natural Joins, Conjunctive Queries, MPC Algorithms, Parallel Computing}
}

Keywords: Natural Joins, Conjunctive Queries, MPC Algorithms, Parallel Computing
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/46826

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