III: Small: Query Compilation on Probabilistic Databases

概率数据库的目标是管理数据不确定的大型数据库。应用包括Web规模的信息提取，RFID系统，科学数据管理，生物医学数据集成，商业智能，数据清洗，近似模式映射和数据重复删除。尽管有巨大的需求和密集的最近的研究概率数据库，没有强大的概率数据库系统存在的日期。原因是概率推理问题一般来说是棘手的。幸运的是，在数据库中，概率推理问题有两个不同的输入：查询和数据库实例。这导致最近发现的安全查询，这是查询，可以有效地评估任何输入数据库，和新的概率推理算法，利用查询的结构。然而，不安全查询仍然是概率数据库中的一个主要挑战，本项目研究新的算法来评估概率数据库上的不安全查询，并保证性能。它使用了一种新的方法，查询编译，它将查询转换为四个目标之一：OBDD，FBDD，d-DNNF和使用包含/排除节点的电路。该项目追求两个目标：（1）它开发了依赖于实例的编译技术，大大扩展了安全查询中使用的独立于实例的技术的范围。(2)它开发了近似查询编译技术，即使在棘手的查询，实例对，通过牺牲准确性，始终有效地运行。这些算法是保守的，在这个意义上，他们返回正确的概率在所有情况下，当输入查询，实例对是tractable.The智力优点这个项目包括新的技术，编译查询到四个编译目标之一，OBDD，FBDD，d-DNNF，和包含/排除为基础的推理，使用两个精确推理（没有性能保证）和近似推理（有性能保证）。它扩展了我们对概率推理的理解，并为概率数据库引擎提供了实用的方法。作为更广泛的影响，该项目受益于大量需要对不确定数据进行通用管理的应用程序，从大规模信息提取系统到科学数据管理，再到商业智能。该项目逐渐将概率数据的主题纳入研究生教育的课程;查询编译已经在PI关于概率数据库的书（http：//dx.doi.org/10.2200/S00362ED1V01Y201105DTM016）中进行了讨论，这是一本研究生级别的教科书。http://www.cs.washington.edu/homes/suciu/project-querycompilation.html

The goal of probabilistic databases is to manage large databases where the data is uncertain. Applications include Web-scale information extraction, RFID systems, scientific data management, biomedical data integration, business intelligence, data cleaning, approximate schema mappings, and data deduplication. Despite the huge demand and the intense recent research on probabilistic databases, no robust probabilistic database systems exist to date. The reason is that the probabilistic inference problem is, in general, intractable. Fortunately, in databases there are two distinct inputs to the probabilistic inference problem: the query and the database instance. This has led recently to the discovery of safe queries, which are queries that can be evaluated efficiently on any input database, and to new probabilistic inference algorithms that exploit the structure of the query. However, unsafe queries remain a major challenge in probabilistic databases.This project studies novel algorithms for evaluating unsafe queries on probabilistic database, with guaranteed performance. It uses a novel approach, query compilation, which translates the query into one of four targets: OBDDs, FBDDs, d-DNNFs, and circuits using inclusion/exclusion nodes. The project pursues two thrusts: (1) It develops instance-dependent compilation techniques that significantly extend the reach of instance-independent techniques used in safe queries. (2) It develops approximate query compilation techniques , which always run efficiently, even on intractable query, instance pairs, by sacrificing accuracy. These algorithms are conservative, in the sense that they return correct probabilities in all cases when the input query, instance pair is tractable.The Intellectual Merit of this project consists of new techniques for compiling queries into one of four compilation targets, OBDD, FBDD, d-DNNF, and inclusion/exclusion-based inference, using both exact inference (without performance guarantees), and approximate inference (with performance guarantees). It expands our understanding of probabilistic inference, and leads to practical approaches for probabilistic database engines. As Broader Impact, the project benefits a large class of applications that require general purpose management of uncertain data, ranging from large-scale information extraction systems, to scientific data management, to business intelligence. The project gradually incorporates topics from probabilistic data into into a curriculum for graduate level education; query compilation is already discussed in the PI's book on Probabilistic Databases ( http://dx.doi.org/10.2200/S00362ED1V01Y201105DTM016), a graduate-level textbook.For further information see the project web site at the URL: http://www.cs.washington.edu/homes/suciu/project-querycompilation.html