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

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

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.