A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries
A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries
复制标题
联合查询并行计算的最坏情况最优多轮算法
DOI：
10.1145/3034786.3034788
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Dan Suciu
中科院分区：
文献类型：
--
作者：
Bas Ketsman;Dan Suciu
我们研究了计算P分布式服务器上完整连接的查询Q的最佳通信成本。已知两个先前的结果。首先，对于无偏度数据的单轮算法，每个服务器的最佳通信成本为m/p^（1/tau*），其中m是最大输入关系的大小，而tau*是分数覆盖号码查询超图。其次，对于多轮算法和不受限制的数据库实例，证明任何算法都需要至少M/p^（1/rho*）每台服务器的通信成本，其中Rho*是覆盖查询超格的分数边缘；但是，由于这种情况，没有匹配的算法（两个受限的查询：链和周期）。在本文中，我们描述了一种多轮算法，该算法在所有输入关系都是二进制的情况下，计算每个服务器的负载m/p^（1/rho*）的查询。因此，我们证明这是二进制输入关系的所有查询的最佳负载。我们的算法代表了先前的链和周期算法的非平地扩展，并利用了图的某些独特特性，而图形不再适用于Hyper-Graphs。
We study the optimal communication cost for computing a full conjunctive query Q over p distributed servers. Two prior results were known. First, for one-round algorithms over skew-free data the optimal communication cost per server is m/p^(1/tau*), where m is the size of the largest input relation, and tau* is the fractional vertex covering number of the query hypergraph. Second, for multi-round algorithms and unrestricted database instances, it was shown that any algorithm requires at least m/p^(1/rho*) communication cost per server, where rho* is the fractional edge covering number of the query hypergraph; but no matching algorithms were known for this case (except for two restricted queries: chains and cycles). In this paper we describe a multi-round algorithm that computes any query with load m/p^(1/rho*) per server, in the case when all input relations are binary. Thus, we prove this to be the optimal load for all queries over binary input relations. Our algorithm represents a non-trivial extension of previous algorithms for chains and cycles, and exploits some unique properties of graphs, which no longer hold for hyper-graphs.