| Available via | http://dbpubs.stanford.edu/pub/2007-26 |
|
Submitted on |
21st of August 2007 |
|
Author |
Benjelloun, Omar; Das Sarma, Anish; Halevy, Alon; Theobald, Martin; Widom, Jennifer |
|
Title |
Databases with Uncertainty and Lineage |
|
Date of publication |
2007 |
|
Citation |
Benjelloun, Omar; Das Sarma, Anish; Halevy, Alon; Theobald, Martin; Widom, Jennifer. Databases with Uncertainty and Lineage, |
|
Number of pages |
20 |
|
Language |
English |
|
Project |
Stanford InfoLab |
|
Type |
Conference or Journal Paper |
|
Subject group |
Computer Science |
|
Abstract |
This paper introduces ULDBs, an extension of relational databases with simple yet expressive constructs for
representing and manipulating both lineage and uncertainty.
Uncertain data and data lineage are two important areas of
data management that have been considered extensively in
isolation, however many applications require the features in tandem. Fundamentally, lineage enables simple and consistent representation of uncertain data, it correlates uncertainty in query results with uncertainty in the input data, and query processing with lineage and uncertainty together presents computational benefits over treating them separately.
We show that the ULDB representation is complete, and that it permits straightforward implementation of many relational operations. We define two notions of ULDB minimality ý data-minimal and lineage-minimal ý and study minimization of ULDB representations under both notions. With lineage, derived relations are no longer self-contained: their uncertainty depends on uncertainty in the base data. We provide an algorithm for the new operation of extracting a database subset in the presence of interconnected uncertainty. We also show how ULDBs enable a new approach to query processing in probabilistic databases. Finally, we describe the current state of the Trio system, our implementation of ULDBs under development at Stanford. |
|
Keywords |
Uncertainty in Databases; Lineage; Provenance; Probabilistic data management |
|
Contact address |
anish@cs.stanford.edu |
| Fulltext source |
PDF (pdf, pdf.gz, pdf.zip)
| Management of the document by | siroker@db.stanford.edu
| |