Incomplete database

An incomplete database is a kind of database, and more specifically of uncertain database, studied in database theory. An incomplete database is a compact representation of a set of (potentially infinite) possible worlds, each of which are themselves a database.

Formal definition

Generally speaking, an incomplete database model is a set ${\mathcal {D}}$ of representations that are compact encodings of a set of possible worlds. The representations are the incomplete databases, and the possible worlds are the concrete databases that can be obtained from an incomplete database. Formally, to each representation $D\in {\mathcal {D}}$ we associate a set $\Vert D\Vert$ of possible worlds, with each possible world being a regular database.

To be more concrete, we need to fix a database model. The most common choice is the relational model. Multiple incomplete database models have been defined over the relational model, that form extensions to the relational algebra. These have been called Imieliński–Lipski algebras:

• Relations with NULL 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 NULL values:

id	Name	Salary
1	Alice	10,000
2	Bob	NULL
3	Charlie	NULL

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:

id	Name	Salary
1	Alice	10,000
2	Bob	8,000
3	Charlie	12,000