III: Small: Query Compilation on Probabilistic Databases

III：小：概率数据库上的查询编译

• 批准号: 1115188
• 负责人: Dan Suciu
• 金额: $ 50万
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-08-01 至 2015-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1115188&HistoricalAwards=false
• 关键词: III; Small; Query; Compilation; Probabilistic

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

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