Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/28068
Title: | Parallel-Correctness and Transferability for Conjunctive Queries under Bag Semantics | Authors: | KETSMAN, Bas NEVEN, Frank VANDEVOORT, Brecht |
Issue Date: | 2018 | Publisher: | Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik | Source: | Kimelfeld, Benny; Amsterdamer, Yael (Ed.). 21st International Conference on Database Theory (ICDT 2018), Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik,p. 1-16 (Art N° 18) | Series/Report: | Leibniz International Proceedings in Informatics (LIPIcs) | Series/Report no.: | 98 | 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. | Keywords: | conjunctive queries; distributed evaluation; bag semantics | Document URI: | http://hdl.handle.net/1942/28068 | ISBN: | 9783959770637 | DOI: | 10.4230/LIPIcs.ICDT.2018.18 | Rights: | © Bas Ketsman, Frank Neven, and Brecht Vandevoort; licensed under Creative Commons License CC-BY | Category: | C1 | Type: | Proceedings Paper |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
LIPIcs-ICDT-2018-18.pdf | Published version | 604.63 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
1
checked on Sep 3, 2020
Page view(s)
46
checked on Sep 7, 2022
Download(s)
14
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.