Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/25630

Title: Parallel-Correctness and Transferability for Conjunctive Queries
Authors: Ameloot, Tom J.
Geck, Gaetano
Ketsman, Bas
Neven, Frank
Schwentick, Thomas
Issue Date: 2017
Citation: JOURNAL OF THE ACM, 64(5) (Art N° 36)
Abstract: A dominant cost for query evaluation in modern massively distributed systems is the number of communication rounds. For this reason, there is a growing interest in single-round multiway join algorithms where data are first reshuffled over many servers and then evaluated in a parallel but communication-free way. The reshuffling itself is specified as a distribution policy. We introduce a correctness condition, called parallel-correctness, for the evaluation of queries w.r.t. a distribution policy. We study the complexity of parallel-correctness for conjunctive queries as well as transferability of parallel-correctness between queries. We also investigate the complexity of transferability for certain families of distribution policies, including the Hypercube distribution policies.
URI: http://hdl.handle.net/1942/25630
DOI: 10.1145/3106412
ISSN: 0004-5411
Category: A1
Type: Journal Contribution
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
Published version725.81 kBAdobe PDF
Proof of peer review310.52 kBAdobe PDF
Peer-reviewed author version551.17 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.