III:Small: Optimal Query Processing meets Information Theory: from Proofs to Algorithms

分析大型数据集的需求正在以比我们从数据中计算有意义的见解的能力更快的速度增长。 尽管在查询处理、查询优化和新型硬件方面取得了进步，但高效的查询评估仍然是数据库社区迄今为止面临的主要挑战。 这个项目将探索新的方法来设计查询处理算法，使用信息理论的技术。 信息论领域在过去的70年里得到了发展，并且已经发现了从通信到机器学习的许多应用，但它还没有以重要的方式用于支持查询处理。 该项目将信息论的技术转移到处理大量数据的任务中。该项目引入了一种新的查询评估范式，称为“从证明到算法”，将查询上界的信息论证明映射到最佳查询评估算法。该项目将追求四个目标。 在第一个推力，它将使用信息理论，以数据库统计数据的基础上，查询答案的新的界限。 第二个推力将开发一个映射，从信息论不等式关系运算符，并从完整的证明查询大小的一个完整的查询计划，可证明的最佳运行时间。 第三个重点是将这些技术扩展到更细粒度的统计数据，包括草图，不同的值和重量级人物。 最后，第四个推力将扩展算法的查询与预测，聚合，和group-by的。这个奖项反映了NSF的法定使命，并已被认为是值得的支持，通过评估使用基金会的智力价值和更广泛的影响审查标准。

The demand to analyze large datasets is increasing at a rate faster than our ability to compute meaningful insights from the data. Despite the advances in query processing, query optimization, and novel hardware, efficient query evaluation remains a major challenge for the database community to date. This project will explore new ways to design query processing algorithms by using techniques from information theory. The field of information theory has been developed over the last seven decades and has found many applications ranging from communications to machine learning, but it has not been used yet in a significant way to support query processing. This project transfers techniques from information theory to the task of processing massive amounts of data.The project introduces a new paradigm for query evaluation, called "from proofs to algorithms," which maps an information-theoretic proof of a query's upper bounds into optimal query evaluation algorithms. The project will pursue four thrusts. In the first thrust it will use information theory to derive new bounds on the query answer based on database statistics. The second thrust will develop a mapping from the information theoretic inequalities to relational operators, and from the complete proof of the query size to a complete query plan with provably optimal runtime. The third thrust will extend these techniques to finer grained statistics, including sketches, distinct values, and heavy hitters. Finally, the fourth thrust will extend the algorithm to queries with projections, aggregates, and group-by's.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.