# 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.

 BibTeX DublinCore EndNote HTML

 Preview
PDF
200Kb

## Abstract

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: Uncontrolled Keywords: Techreport (Technical Report) Uncertainty in databases, data modelling, representation schemes Miscellaneous Miscellaneous Project Homepage http://infolab.stanford.edu/ 702 Import Account 02 Dec 2005 16:00 22 Dec 2008 17:58