III COR: Query Evaluation and View Materialization in Probabilistic Data

概率数据中的查询评估和视图物化PI：Dan Suciu(U.Washington)奖：IIS-0713576数据库和数据管理工具具有确定性语义：数据项要么在数据集中，要么不在数据集中。但是，当数据来自多个来源或被自动提取时，它通常包含各种难以使用标准确定性语义建模的不精确信息：同一数据项在不同来源可能具有不同的表示，并且匹配算法不精确；不同来源的模式不同，模式匹配工具不精确或不完整，或者两者兼而有之；不同来源的数据可能包含相互矛盾的信息；最后，一些数据，如传感器数据，本质上是概率的，因此不精确。该项目以统一的方式将所有不精确源表示为具有概率语义的数据，并扩展了S的数据管理工具以高效地管理具有概率语义的数据。重新设计数据库以处理概率数据是一项艰巨的任务。本项目研究了概率数据管理的两个核心问题：概率数据库查询评估问题的复杂性和视图物化问题(决定一个视图是否可以物化以及它是否可以用于其他查询计划)。这项研究的结果将包括在通用概率查询处理器中使用的一系列基本技术。该项目在几个不同领域的交集上做出了新的贡献：逻辑、概率论、知识表示以及传统的查询处理和优化。该项目提高了对概率数据查询评估问题的理解，开发了有效评估此类查询和物化视图的新算法，同时利用了现有的数据库技术。搜索大型信息空间(Web、大型科学数据库集合、国土安全数据)是计算机科学的新领域，也是最具挑战性的领域之一。支持扩展到大型和异类信息空间的复杂搜索所需的创新必须来自数据管理研究社区。该项目有助于扩大我们搜索大型信息空间的能力。如果成功，该项目将是帮助数据管理技术经历新的范式转换的部分之一，从支持具有确定性语义的复杂查询到支持具有概率语义的复杂探索。项目URL:http://www.cs.washington.edu/homes/suciu/project-probD

Query Evaluation and View Materialization in Probabilistic DataPI: Dan Suciu (U. Washington)Award: IIS-0713576Databases and data management tools have a deterministic semantics: a data item either is in the data set or is not. But when data comes from multiple sources,or is extracted automatically, it often contains a variety of imprecisions thatare difficult to model using the standard deterministic semantics: the same data item may have different representations in different sources and matching algorithms are imprecise; schemas differ across sources and schema matching tools are imprecise or incomplete or both; data at different sources may hold contradictory information; finally, some data, such as sensor data, is inherently probabilistic and hence imprecise. This project represents all sources of imprecision in a single uniform way, as data with a probabilisticsemantics, and extends today''s data management tools to manage efficiently data with probabilistic semantics.Re-designing databases to handle probabilistic data is a daunting task.This project studies two problems that lie at the core of probabilistic data management: the complexity of the query evaluation problem on probabilistic databases, and the view materialization problem (deciding whether a view can be materialized and whether it can be used in other query plans). The results of this research will consists of a range of fundamental techniques to be used in a general purpose probabilistic query processor.Intellectual Merits. The project makes new contributions that lie at the intersection of several disparate fields: logic, probability theory, knowledge representation, and traditional query processing and optimization. The project enhances the understanding of the query evaluation problem on probabilistic data, develops new algorithms for efficiently evaluating such queries and for materializing views, while leveraging existing database technology.Broader Impact. Searching large information spaces (the Web; large collectionsof scientific databases; Homeland Security data) is one the new and most challenging frontiers in Computer Science. The innovation that is needed to support complex searches that scale to large and heterogeneous information spaces, has to come from the data management research community. This project makes contributions to broaden our ability to search large information spaces. If successful, the project will be one of the piecesthat will help data management technology undergo a new paradigm shift, from supporting complex queries with deterministic semantics,to supporting complex explorations with probabilistic semantics.Project URL:http://www.cs.washington.edu/homes/suciu/project-probD