An uncertain database is a kind of

database In computing, a database is an organized collection of data or a type of data store based on the use of a database management system (DBMS), the software that interacts with end users, applications, and the database itself to capture and a ...

studied in

database theory Database theory encapsulates a broad range of topics related to the study and research of the theoretical realm of databases and database management systems. Theoretical aspects of data management include, among other areas, the foundations of q ...

. The goal of uncertain databases is to manage information on which there is some

uncertainty Uncertainty or incertitude refers to situations involving imperfect or unknown information. It applies to predictions of future events, to physical measurements that are already made, or to the unknown, and is particularly relevant for decision ...

. Uncertain databases make it possible to explicitly represent and manage uncertainty on the data, usually in a succinct way.

Formal definition

At the basis of uncertain databases is the notion of

possible world A possible world is a complete and consistent way the world is or could have been. Possible worlds are widely used as a formal device in logic, philosophy, and linguistics in order to provide a semantics for intensional and modal logic. Their met ...

. Specifically, a possible world of an uncertain database is a (certain) database which is one of the possible realizations of the uncertain database. A given uncertain database typically has more than one, and potentially infinitely many, possible worlds. A formalism to represent uncertain databases then explains how to succinctly represent a set of possible worlds into one uncertain database.

Types of uncertain databases

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 Null may refer to: Science, technology, and mathematics Astronomy *Nuller, an optical tool using interferometry to block certain sources of light Computing *Null (SQL) (or NULL), a special marker and keyword in SQL indicating that a data value do ...

in SQL, arguably the most commonplace instantiation of uncertain databases, is an example of incomplete database model. *

Probabilistic database 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 da ...

s are a compact representation of a

probability distribution In probability theory and statistics, a probability distribution is a Function (mathematics), function that gives the probabilities of occurrence of possible events for an Experiment (probability theory), experiment. It is a mathematical descri ...

over the set of possible worlds. * Fuzzy databases are a compact representation of a

fuzzy set Fuzzy or Fuzzies may refer to: Music * Fuzzy (band), a 1990s Boston indie pop band * Fuzzy (composer), Danish composer Jens Vilhelm Pedersen (born 1939) * Fuzzy (album), ''Fuzzy'' (album), 1993 debut album of American rock band Grant Lee Buffalo ...

of the possible worlds. Though mostly studied in the relational setting, uncertain database models can also be defined in other

relational model The relational model (RM) is an approach to managing data using a structure and language consistent with first-order predicate logic, first described in 1969 by English computer scientist Edgar F. Codd, where all data are represented in terms of t ...

s such as

graph database A graph database (GDB) is a database that uses graph structures for semantic queries with nodes, edges, and properties to represent and store data. A key concept of the system is the graph (or edge or relationship). The graph relates the dat ...

s or

XML database An XML database is a data persistence software system that allows data to be specified, and stored, in XML format. This data can be queried, transformed, exported and returned to a calling system. XML databases are a flavor of document-oriented ...

Incomplete database

The most common

database model A database model is a type of data model that determines the logical structure of a database. It fundamentally determines in which manner data can be stored, organized and manipulated. The most popular example of a database model is the relatio ...

is the

. Multiple incomplete database models have been defined over the relational model, that form extensions to the

relational algebra In database theory, relational algebra is a theory that uses algebraic structures for modeling data and defining queries on it with well founded semantics (computer science), semantics. The theory was introduced by Edgar F. Codd. The main applica ...

. These have been called Imieliński–Lipski algebras: * Relations with

values, also called Codd tables * c-tables * v-tables

Example

The following table is a relation of an incomplete database, described in the formalism of

values: There are infinitely many possible worlds for this incomplete database, obtained by replacing the "NULL" values with concrete values. For instance, the following relation is a possible world: {, class="wikitable" , - ! id ! Name ! Salary , - , 1 , Alice , 10,000 , - , 2 , Bob , 8,000 , - , 3 , Charlie , 12,000

References

Data management Database theory