Stanford InfoLab Publication Server

Representing Uncertain Data: Uniqueness, Equivalence, Minimization, and Approximation

Das Sarma, Anish and U. Nabar, Shubha and Widom, Jennifer (2005) Representing Uncertain Data: Uniqueness, Equivalence, Minimization, and Approximation. Technical Report. Stanford.




Many schemes have been proposed for representing uncertain data, where an uncertain database is defined as a set of {\em possible instances} for the database. Some important properties of representation schemes, such as {\em completeness} and {\em closure}, have already been considered. In this paper we identify several other interesting properties and obtain results for them with respect to a variety of different representation schemes. We first consider the {\em uniqueness} of representations, i.e., whether there is at most one representation for a set of possible instances in a particular representation scheme. For schemes that do not guarantee unique representations, we provide algorithms and complexity results for testing {\em equivalence} of representations. We also consider the problem of {\em minimizing} the size of the representation for a set of possible instances, obtaining a strong result for uncertainty schemes comprised of tuples and constraints: minimizing the number of tuples also minimizes the size of constraints. We show the NP-hardness of minimizing a representation, and study the more restricted problem of maintaining minimality when performing operations on the data. Next, we present several results on the problem of {\em approximating} an uncertain database when we wish to use a simple (incomplete) representation scheme. Finally, we give an interesting result relating closure and completeness for uncertain databases.

Item Type:Techreport (Technical Report)
Uncontrolled Keywords:Uncertainty in databases, data modelling, representation schemes
Related URLs:Project Homepage
ID Code:702
Deposited By:Import Account
Deposited On:02 Dec 2005 16:00
Last Modified:22 Dec 2008 17:58

Download statistics

Repository Staff Only: item control page