We study the problem of computing a conjunctive query q in parallel, using p
of servers, on a large database. We consider algorithms with one round of
communication, and study the complexity of the communication. We are especially
interested in the case where the data is skewed, which is a major challenge for
scalable parallel query processing. We establish a tight connection between the
fractional edge packings of the query and the amount of communication, in two
cases. First, in the case when the only statistics on the database are the
cardinalities of the input relations, and the data is skew-free, we provide
matching upper and lower bounds (up to a poly log p factor) expressed in terms
of fractional edge packings of the query q. Second, in the case when the
relations are skewed and the heavy hitters and their frequencies are known, we
provide upper and lower bounds (up to a poly log p factor) expressed in terms
of packings of residual queries obtained by specializing the query to a heavy
hitter. All our lower bounds are expressed in the strongest form, as number of
bits needed to be communicated between processors with unlimited computational
power. Our results generalizes some prior results on uniform databases (where
each relation is a matching) [4], and other lower bounds for the MapReduce
model [1].

研究使用 p 个服务器在大型数据库上并行计算简单查询 q 的通信复杂性，特别关注数据倾斜的情况下的情况，建立了查询的分数边覆盖与通信量之间的紧密联系，并提供了查询分数边覆盖的匹配上界和下界，所有下界都以比特通信量的形式表达。