III: Medium: Collaborative Research: U4U - Taming Uncertainty with Uncertainty-Annotated Databases

不确定性在数据分析中普遍存在，无论数据的大小、应用领域或分析类型如何。不确定性的常见来源包括缺失值、传感器误差、偏差、离群值和许多其他因素。传统的确定性数据管理不跟踪不确定性，因此需要在数据被摄入系统之前解决数据质量问题，这通常是不可行的。净效应是，固有的不确定数据被视为确定数据。然而，如果忽略数据的不确定性，则会导致难以追踪的错误，这反过来又会对真实的世界产生严重的影响，例如毫无根据的科学发现，经济损失，甚至是基于错误数据的医疗决策。虽然存在用于管理不完整数据的技术，但这些技术对于现实世界的使用来说通常太重，并且可能对用户隐藏相关信息。这个项目的目标是开发轻量级的技术来管理不确定数据，使广泛的应用程序来管理不确定性。目前管理不确定数据的方法通常是计算昂贵的，只适用于有限类型的查询。计划中的研究将产生管理不确定数据的新方法，弥合确定性和不完整数据管理之间的差距。这个项目的基础是不确定性注释的数据库，它用不确定性标签来丰富数据，并为通过查询传播这些标签提供语义。其结果是经典数据管理的严格概括，结合了确定性数据管理的性能，通用性和易用性与不完整数据库技术的强大正确性保证。实现这一目标是非常重要的，因为不确定数据的查询评估是棘手的，即使是相对简单的不确定数据模型和有限类的查询。将探讨三个主要的研究方向，以解决开发这种技术的主要挑战：（i）不确定性注释的数据库将扩展属性级注释和可能答案的过度近似的紧凑编码。这使得该方法能够处理丢失的数据和处理非单调查询，如查询与聚合;（ii）方法来compounding近似不完整的数据库将被开发来处理大的，甚至无限的可能的结果集查询不确定的数据;（iii）针对不确定性的查询评估的优化算法-将开发附加说明的数据库，以解决查询不确定数据的性能限制问题。这项计划中的工作将首次以合理的成本为复杂查询提供有原则的不确定性管理，从而显著提高不确定性数据管理的最新水平。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Uncertainty is prevalent in data analysis, no matter what the size of the data, the application domain, or type of analysis. Common sources of uncertainty include missing values, sensor errors, bias, outliers, and many other factors. Classical deterministic data management does not track uncertainty and, thus requires data quality issues to be resolved before data is ingested into the system, which is often not feasible. The net effect is that inherently uncertain data is being treated as certain. However, if ignored, data uncertainty results in hard to trace errors, which in turn can have severe real world implications such as unfounded scientific discoveries, financial damages, or even medical decisions based on incorrect data. While there exist techniques for managing incomplete data, these techniques are generally too heavy-weight for real-world usage and may hide relevant information from users. The goal of this project is to develop light-weight techniques for managing uncertain data that empower a wide range of applications to manage uncertainty.Current methods for managing uncertain data are often computationally expensive and are only applicable to limited types of queries. The planned research will result in novel methods for managing uncertain data that bridge the gap between deterministic and incomplete data management. The foundation of this project are uncertainty-annotated databases, which enrich data with uncertainty labels and provide semantics for propagating these labels through queries. The result is a strict generalization of classical data management that combines the performance, generality, and ease-of-use of deterministic data management with the strong correctness guarantees of incomplete database techniques. Achieving this goal is highly non-trivial, because query evaluation over uncertain data is intractable, even for relatively simple uncertain data models and restricted classes of queries. Three main research thrusts will be explored that address the main challenges in developing such a technique: (i) uncertainty-annotated databases will be extended with attribute-level annotations and an compact encoding of an over-approximation of possible answers. This enables the approach to handle missing data and to deal with non-monotone queries such as queries with aggregation; (ii) methods to compactly approximating incomplete databases will be developed to deal with the large or even infinite sets of possible results produced by queries over uncertain data; (iii) optimized algorithms for query evaluation over uncertainty-annotated databases will be developed to address the performance limitations of queries over uncertain data. The planned work will significantly enhance the state-of-the-art in uncertain data management by, for the first time, enabling principled uncertainty management for complex queries at a reasonable cost.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.