ACM通信
研究突出了
技术角度:快速连接的数据分布
当我们谈到大数据和数据分析时，一些大人物说，其中最大的组成部分是所谓的数据争吵:提取、集成、查询，以及为有意义的分析算法应用准备数据。数据争论依赖于众所周知和可信的数据库技术，但许多经典的数据库问题现在在新的环境下被提出。其中一个原因是并行处理对于处理大量数据非常重要。在新的环境中，由于大规模并行导致的成本占了标准数据库环境的通常I/O成本，这使得对经典数据库问题的研究得到了稳定的发展。这些新的成本主要与沟通有关。
对于并行数据处理算法(例如查询计算)来说，降低通信成本的最有效方法是什么?如果我们可以在单轮通信中将数据分发到服务器，让它们完成它们的工作，然后收集结果来生成我们的查询的答案，那将是理想的。这正是下面这篇论文所研究的问题。它着眼于连接算法:数据库查询处理中最常见和最重要的任务，并研究连接上的条件，使一轮并行算法产生正确的结果。
他们并不是第一个关注这个问题的人。2010年，Afrati和Ullman开始了这种多连接算法的研究。2013年，Beame、koutis和Suciu提出了一种改进的超立方体算法。在这些算法中，网络拓扑是一个超立方体。要计算查询的值，需要在多个节点中复制每个元组，然后让每个节点执行计算。虽然超立方体是一种相当自然的分布策略，但它肯定不是唯一的。但是我们能推断出任意分配策略下的单轮join评估吗?
此外，分发策略是依赖于查询的。虽然为所有场景找到一种策略当然是不现实的，但更实际的需求是什么:如果我们已经知道策略对查询有效问，也许我们可以对另一个查询使用相同的策略问，而不重新分配数据?本文解决了这些问题。
形式主义。它是非常简单和优雅的。网络是节点名称的集合;分布策略将关系中的每个元组分配给一组节点。这是沟通环节。查询问然后在每个节点本地执行。如果这样的分布式计算得到的结果是并行正确的问；也就是元组的答案问正是那些在网络节点本地产生的。
接下来，如果我们有两个查询问而且问，我们知道每一个分配政策问平行校正对问，我们说并行正确性从问来问”。在这种情况下，所做的工作问在寻找正确的分发策略方面，不需要再做问”。
结果，以及结果告诉我们什么。这是一篇理论论文;主要结果是并行正确性和并行可转移性的检验复杂度。它主要关注连接查询类，即比多路连接更通用的查询。
下面的文章着眼于连接算法:数据库查询处理中最常见和最重要的任务。
在温和的假设下，并行正确性是
的推进。也就是说，它比NP或coNP稍微难一点，但仍然在多项式空间内。在实践中，这意味着检查分布策略是否保证所有数据库的正确性可以在指数级时间内完成。注意，这是一个静态分析问题(数据库不是输入)，指数时间是可以接受的，实际上是连接查询的最佳情况(因为它们的包含是NP-complete的)。
然后，作者展示了具有否定要求的连接查询的相同问题(对一些复杂性理论假设取模)。双也就是说，-指数时间实际上是不可解的，这意味着需要将注意力限制在简单连接上。
最后，连接查询并行正确性的可转移性在指数级时间内是可解决的(记住，这是一个关于查询的问题，而不是关于数据的问题)，而且重要的是，对于许多类的连接查询，它在NP中是可解决的，比如多连接(这暗示了在实践中使用高效NP求解器来解决这个问题的可能性)。
最后，我想解释一下为什么我认为这是一篇模型数据库理论论文。这样的论文应该包含以下几个关键成分:
- 它应该考虑在实践中感兴趣的真实数据管理问题;
- 它应该提供一种干净、简单的形式主义，让理论家和实践者都能遵循;
- 它应该提供理论结果，使我们了解原来的实际问题。
这篇论文满足了所有这些条件:它为一个重要的实际问题提供了优雅的理论研究，并给出了一组良好的结果，划定了可行性边界。
数字图书馆是由计算机协会出版的。版权所有©2017 ACM股份有限公司
没有发现记录