AF: SMALL: Relational Algorithms

关系数据库将数据以关系形式存储在多个表中，这在美国企业和组织中是一种普遍存在的技术。四个最常用的数据库(Oracle、MySQL、Microsoft SQL Server、PostgreSQL)都是关系型数据库。使用机器学习从他们的数据中收集竞争对手的见解，也是美国企业和组织中普遍存在的一项技术。因此，关系数据上的机器学习任务无处不在。然而，基本上所有标准的机器学习算法都要求输入是单个表的形式，因此这些算法不能直接操作以关系形式存储的数据。此外，人们是否以及如何调整这些机器学习算法，以有效地操作关系形式的数据，这一点还远不明显。因此，标准做法是首先将关系数据库中的多个表连接到一个更大的表中，然后将该表导出到标准的机器学习包中。连接表是一项耗时的操作，在最坏的情况下需要指数级的时间和内存。这个项目的目标是为常见的机器学习问题开发关系算法，这是一种直接在关系表上工作的高效算法，从而避免了昂贵的连接操作。对于关系数据上的标准机器学习问题，更有效的算法将使美国公司和组织能够更有效地从他们的关系数据中收集竞争对手的见解。这个项目有四个目标。第一个目标是开发基本几何问题的相关算法，这些问题是许多常见机器学习问题的基础。然后可以使用这些算法作为构建块，为更复杂的机器学习问题开发关系算法。第二个目标是为标准的机器学习问题开发相关算法。方案A是设计标准算法的关系实现，方案B是设计与标准算法具有相同性能保证的替代关系算法，方案C是设计具有替代合理性能保证的关系算法。第三个目标是开发基本的算法设计和分析技术。第四个目标是了解关系算法的局限性，因为在关系算法不可能的情况下很可能会出现问题。调查人员将确定标准算法工具包中的无数算法工具中哪些对开发关系算法有用。在某些情况下，一项已知技术的应用需要一些新奇的东西。在某些情况下，现有的算法工具无法完成这项工作，调查人员将发明新的算法设计和分析技术。作为算法基础研究的标准，在为特定问题设计和分析算法的过程中，对特定算法设计或分析技术具有广泛适用性的认识以及对这些技术局限性的理解自然会发生。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

The use of relational databases, which store data in relational form in multiple tables, is a ubiquitous technology among American businesses and organizations. The four most commonly used databases (Oracle, MySQL, Microsoft SQL Server, PostgreSQL) are all relational. The use of machine learning to glean competitive insights from their data is also a ubiquitous technology among American businesses and organizations. Thus machine-learning tasks on relational data are ubiquitous. However, essentially all standard machine-learning algorithms require the input be in the form of a single table, and thus these algorithms can not operate directly on data hat is stored in relational form. Further, it is far from obvious if and how one can adapt many of these machine-learning algorithms to efficiently operate on data in relational form. Thus the standard practice is to first join together multiple tables inside the relational database into a single larger table, and then export this table to a standard machine-learning package. Joining tables is a time-consuming operation, requiring exponential time and memory in the worst case. The goal of this project is to develop relational algorithms, which are efficient algorithms that work directly on the relational tables and thus avoid expensive join operations, for common machine-learning problems. More efficient algorithms for standard machine learning problems on relational data would allow American companies and organizations to more efficiently glean competitive insights from their relational data. There are four goals for this project. The first goal is to develop relational algorithms for basic geometric problems that underlie many common machine-learning problems. These algorithms can then be used as the building blocks to develop relational algorithms for more complicated machine-learning problems. The second goal is to develop relational algorithms for standard machine-learning problems. Plan A is to design a relational implementation of the standard algorithm, plan B is to design an alternate relational algorithm with the same performance guarantee as the standard algorithm, and plan C is to design a relational algorithm with an alternate reasonable performance guarantee. The third goal is to develop foundational algorithmic-design and -analysis techniques. The fourth goal is to understand the limitations of relational algorithms as there may well be problems where relational algorithms are not possible. The investigators will determine which of the myriad algorithmic tools in the standard algorithmic toolkit are of utility in developing relational algorithms. In some cases the application of a known technique will require some novelty. In some cases no existing algorithmic tool will do the job, and the investigators will invent new algorithmic-design and -analysis techniques. As is the norm in algorithmic foundations research, the recognition that a particular algorithm-design or -analysis technique is of wide applicability, and the understanding of the limitations of these techniques occurs naturally during the process of the design and analysis of algorithms for specific problems.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.