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.2018.18
URN: urn:nbn:de:0030-drops-86040
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8604/
Go to the corresponding LIPIcs Volume Portal

Ketsman, Bas ; Neven, Frank ; Vandevoort, Brecht

Parallel-Correctness and Transferability for Conjunctive Queries under Bag Semantics

pdf-format:
LIPIcs-ICDT-2018-18.pdf (0.6 MB)

Abstract

Single-round multiway join algorithms first reshuffle data over many servers and then evaluate the query at hand in a parallel and communication-free way. A key question is whether a given distribution policy for the reshuffle is adequate for computing a given query. This property is referred to as parallel-correctness. Another key problem is to detect whether the data reshuffle step can be avoided when evaluating subsequent queries. The latter problem is referred to as transfer of parallel-correctness. This paper extends the study of parallel-correctness and transfer of parallel-correctness of conjunctive queries to incorporate bag semantics. We provide semantical characterizations for both problems, obtain complexity bounds and discuss the relationship with their set semantics counterparts. Finally, we revisit both problems under a modified distribution model that takes advantage of a linear order on compute nodes and obtain tight complexity bounds.

BibTeX - Entry

@InProceedings{ketsman_et_al:LIPIcs:2018:8604,
  author =	{Bas Ketsman and Frank Neven and Brecht Vandevoort},
  title =	{{Parallel-Correctness and Transferability for Conjunctive Queries under Bag Semantics}},
  booktitle =	{21st International Conference on Database Theory (ICDT 2018)},
  pages =	{18:1--18:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-063-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{98},
  editor =	{Benny Kimelfeld and Yael Amsterdamer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8604},
  URN =		{urn:nbn:de:0030-drops-86040},
  doi =		{10.4230/LIPIcs.ICDT.2018.18},
  annote =	{Keywords: Conjunctive queries, distributed evaluation, bag semantics}
}

Keywords: Conjunctive queries, distributed evaluation, bag semantics
Collection: 21st International Conference on Database Theory (ICDT 2018)
Issue Date: 2018
Date of publication: 05.03.2018

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