Stanford InfoLab Publication Server

Representing Uncertain Data: Models, Properties, and Algorithms

Das Sarma, Anish and Benjelloun, Omar and Halevy, Alon and Nabar, Shubha and Widom, Jennifer (2009) Representing Uncertain Data: Models, Properties, and Algorithms. VLDB Journal .




In general terms, an uncertain relation encodes a set of possible certain relations. There are many ways to represent uncertainty, ranging from alternative values for attributes to rich constraint languages. Among the possible models for uncertain data, there is a tension between simple and intuitive models, which tend to be {\em incomplete}, and complete models, which tend to be nonintuitive and more complex than necessary for many applications. We present a space of models for representing uncertain data based on a variety of uncertainty constructs and tuple-existence constraints. We explore a number of properties and results for these models. We study completeness of the models, as well as closure under relational operations, and we give results relating closure and completeness. We then examine whether different models guarantee unique representations of uncertain data, and for those models that do not, we provide complexity results and algorithms for testing equivalence of representations. The next problem we consider is that of minimizing the size of representation of models, showing that minimizing the number of tuples also minimizes the size of constraints. We show that minimization is intractable in general and study the more restricted problem of maintaining minimality incrementally when performing operations. Finally, we present several results on the problem of approximating uncertain data in an insufficiently expressive model.

Item Type:Article
Additional Information:This article combines and improves upon two papers: (1) Working Models for Uncertain Data, ICDE, 2006, (2) Representing Uncertainty: Uniqueness, Equivalence, Minimization and Approximation, Technical Report, 2005,
ID Code:924
Deposited By:Anish Das Sarma
Deposited On:15 May 2009 20:09
Last Modified:15 May 2009 20:09

Download statistics

Repository Staff Only: item control page