III: Small: Datalog with Aggregates: Complexity, Optimization, Evaluation

计算机应用程序越来越受数据驱动。他们依赖于处理大型数据集，从中学习驱动应用程序的模型。如今，领先的软件公司和学术机构经常在大规模数据集上进行机器学习，然而，有效使用机器学习工具仍然是一种模糊的实践，主要由机器学习专家完成。ML的未来应用将由数据科学家开发，他们需要友好的工具来帮助他们管理大规模的数据。该项目的目标是为构建此类工具奠定基础。它扩展了当今已经广泛使用的关系数据库，使其能够执行机器学习应用程序中不可或缺的迭代。关系数据库是迄今为止最好的工程系统之一，它们通常用于处理从小到大的数据集。但是它们支持的查询语言SQL只针对不需要迭代的查询进行了优化。然而，几乎所有现代数据科学任务都需要某种形式的迭代。由于SQL不支持迭代，数据科学家不会使用SQL来满足他们的大部分需求。Datlog是几十年前提出的一种查询语言，正是为了支持迭代，然而，Datlog不支持汇总，例如求和或计数，而这些在任何数据科学任务中都是不可或缺的。这个项目克服了基本的障碍，防止datastrum通过使用一个新的抽象，其中标准的关系扩展到半环上的关系支持聚合。 这一修改允许所有传统的SQL优化被转移到数据库中，同时它允许递归和聚合自由交错。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Computer applications are increasingly data driven. They rely on processing large datasets from which they learn models that drive the application. Machine learning on massive datasets is routinely done today by leading software companies and academic institutions, however, using ML tools effectively is still an obscure practice mostly done by ML experts. Future applications of ML will be developed by data scientists, who need friendly tools to help them manage data of massive scale. The goal of this project is to lay the foundations for building such tools. It extends relational databases that are already widely used today with the ability to perform iterations that are indispensable in machine learning applications.Relational databases are some of the best engineered systems to date, and they are used routinely to process datasets from small to massive. But the query language that they support, SQL, is only optimized for queries that do not require iteration. Yet virtually all modern data science tasks require some form of iteration. As SQL does not support iteration well, data scientists do not use SQL for most of their needs. Datalog is a query language proposed decades ago, precisely to support iteration, however, datalog does not support aggregates, such as summation or counting, which are indispensable in any data science task. This project overcomes the fundamental roadblock that prevents datalog from supporting aggregates by using a new abstraction, where standard relations are extended to relations over a semiring. This modification allows all traditional SQL optimizations to be carried over to datalog, and at the same time it allows recursion and aggregates to be interleaved freely.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.