Parallel-Correctness and Transferability for Conjunctive Queries under Bag Semantics
Parallel-Correctness and Transferability for Conjunctive Queries under Bag Semantics
复制标题
包语义下联合查询的并行正确性和可传递性
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Brecht Vandevoort
中科院分区：
文献类型：
--
作者：
Bas Ketsman;F. Neven;Brecht Vandevoort
单轮多路连接算法首先在许多服务器上重新洗牌数据，然后以并行和无通信的方式评估手头的查询。一个关键的问题是，一个给定的分配策略的改组是足够的计算一个给定的查询。这个属性被称为并行正确性。另一个关键问题是检测在评估后续查询时是否可以避免数据重排步骤。后一个问题被称为并行正确性的转移。本文扩展了并行正确性的研究和转移的并行正确性的合取查询，将包语义。我们提供了这两个问题的语义特征，获得复杂性的界限，并讨论了与它们的集合语义对应的关系。最后，我们重新审视这两个问题下修改的分布模型，利用线性顺序的计算节点，并获得严格的复杂性界限。
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.