III: Small: Towards Scalable and Comprehensive Uncertain Data Management

由于不确定数据在大量应用中的重要性，最近对不确定数据的数据库支持产生了很大的兴趣。这一领域的现有工作包括不确定数据的新模型、原型实现以及针对特定类型查询的高效查询处理算法。尽管最近的努力，不确定数据管理的几个重要方面仍然没有得到探索。这个项目解决了其中的两个领域：查询优化和对非关系运算符的支持。第一个目标是关于不确定数据查询的高效执行。与传统数据一样，有效的执行对于确保不确定数据管理系统的可行性是必要的。然而，由于确保正确结果的复杂性，以及对概率分布的CPU密集型操作的需求，该目标是关键和具有挑战性的。在这个项目中，自动查询优化，通过查询重写规则，涉及概率阈值操作，相应的访问方法，和成本估计函数的发展。该项目旨在提高跟踪不确定输入的确切影响的能力，因为数据是由任意程序处理的，利用程序分析领域的先进技术。一个关键的问题与传统的蒙特卡洛为基础的解决方案在于正确识别的独立性在outputof Monte Carlo simulations。为了解决这个问题，本文提出了一种基于程序依赖跟踪的二进制代码执行过程中不确定性传播的跟踪方法。该技术不依赖于蒙特卡罗模拟，也不需要访问源代码或领域知识。欲了解更多信息，请参阅项目网页：http://www.cs.purdue.edu/homes/sunil/uncertainty

Due to the importance of uncertain data for a large number of applications,there has been significant recent interest in database support for uncertaindata. Existing work in this area includes new models for uncertain data,prototype implementations, and efficient query processing algorithms forspecific types of queries. Despite the recent efforts, several important aspectsof uncertain data management remain unexplored. This project addresses twoof these areas: Query Optimization and Support for Non-Relational Operators.The first goal is about efficient execution of uncertain data queries. As withtraditional data, efficient execution is necessary for ensuring the viability ofuncertain data management systems. However, due to the complications ofensuring correct results, and the need for CPU-intensive operations overprobability distributions, the goal is critical and challenging. In this project,automatic query optimizations are developed, through query rewriting rulesthat involve probability threshold operators, corresponding access methods,and cost estimation functions.The difficulty of handling uncertainty when dealing with non-relationaloperators has been expressed in many domains. The project aims toadvance the capability of tracking the exact impact of uncertain inputs asdata is processed by arbitrary programs, leveraging advanced techniquesfrom the area of program analysis. A key problem with traditional MonteCarlo based solutions lies in correctly identifying independence in the outputof Monte Carlo simulations. Data lineage tracing, which identifies the set ofinputs used to compute an output value, is used to address the challenge.Furthermore, a program dependence tracing based approach is devised totrace the propagation of uncertainty during execution of arbitrary binarycode. The technique does not rely on Monte Carlo simulations, and doesnot require access to source code or domain knowledge.For further information see the project web page:http://www.cs.purdue.edu/homes/sunil/uncertainty