Parallel-correctness and transferability for conjunctive queries

DOI10.1145/3106412zbMATH Open1426.68073arXiv1412.4030OpenAlexW2750884547MaRDI QIDQ4640302FDOQ4640302

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)

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.

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

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

zbMATH Keywords

distributed databasesdistribution policiesone-round evaluationparallel query evaluation

Mathematics Subject Classification ID

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

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
• Title not available (Why is that?)
• 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
• Worst-case optimal algorithms for parallel query processing
• Communication steps 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)