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

Abstract

Many schemes have been proposed for representing un-certain data, where an uncertain database is defined as a set of possible instances for the database. Some impor-tant properties of representation schemes, such as com-pleteness and closure, have already been considered. In this paper we identify several other interesting proper-ties and obtain results for them with respect to a vari-ety of different representation schemes. We first consider the 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 al-gorithms and complexity results for testing equivalence of representations. We also consider the problem of min-imizing the size of the representation for a set of pos-sible instances, obtaining a strong result for representa-tion schemes comprised of tuples and constraints: min-imizing 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. We present several results on the problem of ap-proximating an uncertain database when we wish to use a simple (incomplete) representation scheme. Finally, we give an interesting result relating closure and complete-ness for uncertain databases.