Worst-case Optimal Join Algorithms

作     者：Ngo, Hung Q. Porat, Ely Re, Christopher Rudra, Atri 

作者机构：Univ Buffalo SUNY Buffalo NY 14260 USA Bar Ilan Univ IL-5290002 Ramat Gan Israel Stanford Univ Stanford CA 94305 USA Univ Buffalo 338 Davis Hall Buffalo NY 14214 USA Gates Comp Sci Bldg353 Serra Mall Stanford CA 94305 USA 

出 版 物：《JOURNAL OF THE ACM》 (美国计算机学会志)

年 卷 期：2018年第65卷第3期

页      面：16-16页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：NSF [CCF-1161196, CCF-1319402, CCF-0844796] National Science Foundation (NSF) under CAREER [IIS-1353606, CCF-1356918] Office of Naval Research (ONR) [N000141210041, N000141310129] Sloan Research Fellowship Moore Foundation Data Driven Investigator award 

主　　题：Join Algorithms fractional cover bound Loomis-Whitney inequality Bollobas-Thomason inequality 

摘      要：Efficient join processing is one of the most fundamental and well-studied tasks in database research. In this work, we examine algorithms for natural join queries over many relations and describe a new algorithm to process these queries optimally in terms of worst-case data complexity. Our result builds on recent work by Atserias, Grohe, and Marx, who gave bounds on the size of a natural join query in terms of the sizes of the individual relations in the body of the query. These bounds, however, are not constructive: they rely on Shearer s entropy inequality, which is information-theoretic. Thus, the previous results leave open the question of whether there exist algorithms whose runtimes achieve these optimal bounds. An answer to this question may be interesting to database practice, as we show in this article that any project-join style plans, such as ones typically employed in a relational database management system, are asymptotically slower than the optimal for some queries. We present an algorithm whose runtime is worst-case optimal for all natural join queries. Our result may be of independent interest, as our algorithm also yields a constructive proof of the general fractional cover bound by Atserias, Grohe, and Marx without using Shearer s inequality. This bound implies two famous inequalities in geometry: the Loomis-Whitney inequality and its generalization, the Bollobas-Thomason inequality. Hence, our results algorithmically prove these inequalities as well. Finally, we discuss how our algorithm can be used to evaluate full conjunctive queries optimally, to compute a relaxed notion of joins and to optimally (in the worst-case) enumerate all induced copies of a fixed subgraph inside of a given large graph.