Parallel-correctness and transferability for conjunctive queries

DOI10.1145/3106412MaRDI QIDQ4640302zbMATH OpenOpenAlexFDO

Authors Tom J. Ameloot, Gaetano Geck, Bas Ketsman, Frank Neven, Thomas Schwentick

Publication date 17 May 2018

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.4030

zbMATH Keywords

distributed databasesdistribution policiesone-round evaluationparallel query evaluation

Mathematics Subject Classification ID

Database theory (68P15) Distributed algorithms (68W15)

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 is 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, for instance, the Hypercube distribution.

Recommendations

• Parallel-correctness and transferability for conjunctive queries under bag semantics
• Parallel-Correctness and Containment for Conjunctive Queries with Union and Negation
• Parallel-correctness and containment for conjunctive queries with union and negation
• Distribution policies for Datalog
• Distribution policies for Datalog

Cited in

(11)

• Parallel-correctness and transferability for conjunctive queries under bag semantics
• Correctness of query execution strategies in distributed databases
• A Case for Stale Synchronous Distributed Model for Declarative Recursive Computation
• Parallel-Correctness and Containment for Conjunctive Queries with Union and Negation
• scientific article; zbMATH DE number 7561474 (Why is no real title available?)
• Parallel-correctness and containment for conjunctive queries with union and negation
• GYM: a multiround distributed join algorithm
• Distribution policies for Datalog
• Distribution policies for Datalog
• Communication steps for parallel query processing
• Worst-case optimal algorithms for parallel query processing

This page was built for publication: Parallel-correctness and transferability for conjunctive queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4640302)