Stanford InfoLab Publication Server

ULDBs: Databases with Uncertainty and Lineage

Benjelloun, Omar and Das Sarma, Anish and Halevy, Alon and Widom, Jennifer (2005) ULDBs: Databases with Uncertainty and Lineage. Technical Report. Stanford.




This paper introduces \uldb s, an extension of relational databases with simple yet expressive constructs for representing and manipulating both {\em lineage} and {\em uncertainty}. Uncertain data and data lineage are two important areas of data management that have been considered extensively but 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 {\em complete}, and that it permits straightforward implementation of many relational operations. We define two notions of \uldb\ minimality---{\em data-minimal} and {\em 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 algorithms 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. \uldb s form the basis of the {\em Trio} system, under development at Stanford.

Item Type:Techreport (Technical Report)
Additional Information:A previous version of the paper was titled: "The Symbiosis of Lineage and Uncertainty"
Uncontrolled Keywords:Data uncertainty, lineage (provenance); data modeling; probabilistic databases;
Related URLs:Project Homepage
ID Code:703
Deposited By:Import Account
Deposited On:05 Dec 2005 16:00
Last Modified:22 Dec 2008 17:53

Download statistics

Repository Staff Only: item control page