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—dataminimal
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. Finally, we show how ULDBs enable
a new approach to query processing in probabilistic databases.
ULDBs form the basis of the Trio system under development at
Stanford.
%0 Conference Paper
%1 DBLP:conf/vldb/BenjellounSHW06
%A Benjelloun, Omar
%A Sarma, Anish D.
%A Halevy, Alon Y.
%A Widom, Jennifer
%B VLDB
%D 2006
%K pdm
%P 953--964
%T ULDBs: Databases with Uncertainty and Lineage.
%U http://www.vldb.org/conf/2006/p953-benjelloun.pdf
%X 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—dataminimal
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. Finally, we show how ULDBs enable
a new approach to query processing in probabilistic databases.
ULDBs form the basis of the Trio system under development at
Stanford.
@inproceedings{DBLP:conf/vldb/BenjellounSHW06,
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—dataminimal
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. Finally, we show how ULDBs enable
a new approach to query processing in probabilistic databases.
ULDBs form the basis of the Trio system under development at
Stanford.},
added-at = {2009-03-12T15:42:50.000+0100},
author = {Benjelloun, Omar and Sarma, Anish D. and Halevy, Alon Y. and Widom, Jennifer},
biburl = {https://www.bibsonomy.org/bibtex/236af03713e18230c88c0e8f9bf5362f1/lillejul},
booktitle = {VLDB},
citeulike-article-id = {1419525},
interhash = {4c72cb427cd4043b966b502659e10777},
intrahash = {36af03713e18230c88c0e8f9bf5362f1},
keywords = {pdm},
pages = {953--964},
posted-at = {2007-06-28 14:05:07},
priority = {4},
timestamp = {2009-03-12T15:42:53.000+0100},
title = {ULDBs: Databases with Uncertainty and Lineage.},
url = {http://www.vldb.org/conf/2006/p953-benjelloun.pdf},
year = 2006
}