III: Medium: Table-as-Query: Unifying Data Discovery and Alignment

在信息提取技术的进步和重视机构开放性和透明度的社会趋势的推动下，结构化数据正在以惊人的速度产生和共享。开放数据共享是支持机构透明度的核心，但如果共享数据无法被发现并与数据科学家、记者和其他人正在研究的其他数据有效地结合起来，透明度就无法实现。这个项目将从根本上促进开放数据共享的新科学。对包含结构化数据的异构表存储库的数据发现和集成的需求与联邦数据集成（例如，集成企业内的所有数据）或数据交换（数据在一小组自治对等体之间交换，例如，在两个机构之间）的需求根本不同。该项目将为表存储库中的数据发现（表的识别、对齐和集成）奠定理论基础。它将有助于开发正确的概念框架来研究这个问题，并有助于设计解决大规模表发现和对齐问题的系统。目前，针对大规模表存储库的数据发现解决方案还处于起步阶段。一些解决方案高度依赖于特定的领域。例如，在大量协作数据（通常称为web表）中查找相关表的解决方案可能假设表是为人类消费而设计的，具有丰富的、人类可读的属性名称或元数据，并且相对较小（设计用于在web页面上显示）。此外，解决方案通常假设数据科学家非常了解可用的数据以及他们希望如何将其与已知数据集成。这些解决方案允许用户查找与指定属性或与查询表联合的表。但是，如果扩展查询表的最佳方式实际上是在几个属性上将它与其他两个表连接起来，然后将扩展的结果与现有的更宽的表联合起来，那么它们就不够了。该项目将开发一种更全面的表发现方法，既可以发现一组可对齐的表，也可以找到将新数据与查询表集成（或对齐）的最佳方法。在这个称为“表即查询”的新范例中，用户不需要预先知道存储库中不同表的哪些属性是最好的。这个项目推动了一个研究议程，在这个议程下，发现发现的不是单个表，而是一组可以与查询表组合（对齐）的表。解决方案将包括表发现过程中的集成选择，查找最适合与查询表对齐的一组表，并找出最佳对齐方式。重要的是，该项目将不依赖于唯一名称假设，该假设声明不同的值引用不同且唯一的实体。真实数据包含同义词（两个值指向同一个实体）和同形异义词（一个值指向多个实体）。这个项目将为研究表的排列和发现定义新的基础和数学原理。搜索空间是巨大的，因此该项目还将开发近似的、可扩展的解决方案，这些解决方案可以快速（以交互速度）在包含数百万个表的大型表存储库中找到一组良好的表和良好的对齐。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Fueled by advances in information extraction and societal trends that value institutional openness and transparency, structured data are being produced and shared at an overwhelming speed. Open data sharing is central to supporting institutional transparency, but transparency is not achieved if shared data cannot be found and effectively aligned with other data being studied by data scientists, journalists, and others. This project will fundamentally contribute to the new science of open data sharing. The requirements for data discovery and integration over heterogeneous table repositories containing structured data are fundamentally different than they are for federated data integration (where for example, all data within an enterprise is integrated) or data exchange (where data is exchanged among a small set of autonomous peers, for example, between two institutions). This project will lay the theoretical foundations of data discovery (identification, alignment, and integration of tables) within table repositories. It will contribute both to developing the right conceptual framework for studying this problem and to designing systems that solve the table discovery and alignment problems at scale.Today, solutions for data discovery over massive table repositories are in their infancy. Some solutions are highly tied to a specific domain. For example, solutions for finding relevant tables in mass collaboration data (often called web tables) may assume tables are designed for human consumption with rich, human-readable attribute names or metadata, and are relatively small (being designed for display on web pages). Furthermore, solutions often assume that the data scientists know a lot about what data is available and exactly how they want to integrate it with known data. These solutions let a user find tables that join with a specified attribute or union with a query table. But they are inadequate if the best way to extend a query table is to actually join it on several attributes with two other tables and then union the extended result with an existing wider table. This project will develop a more holistic approach to table discovery that both discovers a set of alignable tables as well as the best way to integrate (or align) the new data with a query table. In this new paradigm called "table-as-query", the user does not need to know a priori on which attributes various tables in a repository are best aligned. This project promotes a research agenda under which discovery finds not a single table, but a set of tables that can be combined (aligned) with the query table. The solutions will include integration choices within the table discovery process, looking for a set of tables that can best be aligned with a query table and also finding what the best alignment is. Importantly, the project will not rely on the unique name assumption, which states that different values refer to different and unique entities. Real data contains synonyms (two values that refer to the same entity) and homographs (one value that refers to more than one entity). This project will define new foundations and mathematical principles for studying table alignment and discovery. The search space is massive, so the project will also develop approximate, scalable solutions that can quickly (at interactive speeds) find a good set of tables and good alignments over massive table repositories with millions of tables.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.