Uncertain database

An uncertain database is a kind of database where the uncertainty in the information contained is explicitly represented and managed, usually in a compact way.

At the basis of uncertain database is the notion of possible world: a possible world of an uncertain database is a (certain) database which is one of the possible realization of the uncertain database. A given uncertain database typically has more than one, and potentially infinitely many, possible worlds.

Uncertain database models differ in how they represent and quantify these possible worlds:

• Incomplete databases are a compact representation of the set of possible worlds – the use of NULL in SQL, arguably the most commonplace instantiation of uncertain databases, is an example of incomplete database model.
• Probabilistic databases are a compact representation of a probability distribution over the set of possible worlds.
• Fuzzy databases are a compact representation of a fuzzy set of the possible worlds.

Though mostly studied in the relational setting, uncertain database models can also be defined in other Relational models such as Graph databases, XML databases.