Parallel-Correctness and Transferability for Conjunctive Queries
Parallel-Correctness and Transferability for Conjunctive Queries
复制标题
联合查询的并行正确性和可转移性
作者：
Tom J. Ameloot;Gaetano Geck;Bas Ketsman;F. Neven;T. Schwentick
在现代大规模分布式系统中，查询评估的主要成本是通信轮数。出于这个原因，人们对单轮多路连接算法越来越感兴趣，其中数据首先在许多服务器上重新洗牌，然后以并行但无通信的方式进行评估。重新洗牌本身被指定为分配策略。我们引入了一个正确性条件，称为并行正确性，评估查询w.r.t.分配政策。我们研究了合取查询的并行正确性的复杂性以及查询之间的并行正确性的可转移性。我们还调查了某些家庭的分配政策，包括超立方体分配政策的可转移性的复杂性。
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.