Probabilistic Databases

Most real databases contain data whose correctness is uncertain. In order to work with such data, there is a need to quantify the integrity of the data. This is achieved by using probabilistic databases.

A probabilistic database is an uncertain database in which the possible worlds have associated probabilities. Probabilistic database management systems are currently an active area of research. "While there are currently no commercial probabilistic database systems, several research prototypes exist..."

Probabilistic databases distinguish between the logical data model and the physical representation of the data much like relational databases do in the ANSI-SPARC Architecture.
In probabilistic databases this is even more crucial since such databases have to represent very large numbers of possible worlds, often exponential in the size of one world (a classical database), succinctly.

Terminology

In a probabilistic database, each tuple is associated with a probability between 0 and 1, with 0 representing that the data is certainly incorrect, and 1 representing that it is certainly correct.

Possible Worlds

A probabilistic database could exist in multiple states. For example, if there is uncertainty about the existence of a tuple in the database, then the database could be in two different states with respect to that tuple—the first state contains the tuple, while the second one does not. Similarly, if an attribute can take one of the values ''x'', ''y'' or ''z'', then the database can be in three different states with respect to that attribute.

Each of these ''states'' is called a possible world.

Consider the following database:

(Here ' denotes that the attribute can take any of the values ''b3'', ''b3′'' or ''b3′′'')

*Assuming that there is uncertainty about the first tuple, certainty about the second tuple, and uncertainty about the value of attribute B in the third tuple.

Then the actual state of the database may or may not contain the first tuple (depending on whether it is correct or not). Similarly, the value of the attribute B may be ''b3'', ''b3′'' or ''b3′′''.

Consequently, the possible worlds corresponding to the database are as follows:

Types of Uncertainties

There are essentially two kinds of uncertainties that could exist in a probabilistic database, as described in the table below:

By assigning values to random variables associated with the data items, different possible worlds can be represented.

History

The first published use of the term "probabilistic database" was probably in the 1987 VLDB conference paper "The theory of probabilistic databases", by Cavallo and Pittarelli.Roger Cavallo, Michael Pittarelli: The Theory of Probabilistic Databases. In VLDB'87, Proceedings of 13th International Conference on Very Large Data Bases, September 1-4, 1987, Brighton: 71-81 (1987) The title (of the 11 page paper) was intended as a bit of a joke, since David Maier's 600 page monograph, The Theory of Relational Databases, would have been familiar at that time to most of the conference participants and readers of the conference proceedings.

References

External links

* The MayBMS project at Cornell University
sourceforge.net project site

* Th

project at the University of Washington
* Th
Orion
project at Purdue University
* Th
Trio
project at Stanford University
* Th
BayesStore
project at the University of California, Berkeley
* Th
PrDB
project at the University of Maryland, College Park
* Th
Mimir
project at the University at Buffalo

{{databases

Database management systems
Types of databases
Database theory
Fuzzy logic