Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems
Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems
复制标题
最坏情况最优连接算法：技术、结果和未解决的问题
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
H. Ngo
中科院分区：
文献类型：
--
作者：
H. Ngo
最坏情况最优连接算法是一类连接算法，其运行时匹配给定连接查询的最坏情况输出大小。虽然第一个可证明的最坏情况下的最优连接算法是最近才发现的，但围绕这些算法的技术和结果是从广泛领域的数十年研究中发展出来的，这些领域将图论，算法，信息论，约束满足，数据库理论和几何不等式紧密联系在一起。这些想法不仅仅是纸质的：除了学术项目的实现，这些算法的两个变体是商业数据库和数据分析引擎的工作马连接算法。本文旨在简要介绍最坏情况下的最优连接算法的设计和分析。我们讨论了证明运行时间和输出大小界限的关键技术。我们特别关注连接算法和信息论不等式之间的迷人联系，以及如何将证明转化为算法的想法。最后，我们得出一个有代表性的清单，在这一领域的基本开放的问题。
Worst-case optimal join algorithms are the class of join algorithms whose runtime match the worst-case output size of a given join query. While the first provably worse-case optimal join algorithm was discovered relatively recently, the techniques and results surrounding these algorithms grow out of decades of research from a wide range of areas, intimately connecting graph theory, algorithms, information theory, constraint satisfaction, database theory, and geometric inequalities. These ideas are not just paperware: in addition to academic project implementations, two variations of such algorithms are the work-horse join algorithms of commercial database and data analytics engines. This paper aims to be a brief introduction to the design and analysis of worst-case optimal join algorithms. We discuss the key techniques for proving runtime and output size bounds. We particularly focus on the fascinating connection between join algorithms and information theoretic inequalities, and the idea of how one can turn a proof into an algorithm. Finally, we conclude with a representative list of fundamental open problems in this area.