Incomplete database

An incomplete database^[1]^[2] is a kind of uncertain database which consists in a compact representation of a set of (potentially infinite) possible worlds.

Formal definition

An incomplete database model is a set ${\mathcal {D}}$ of representations that are compact encodings of a set of possible worlds. Formally, to each representation $D\in {\mathcal {D}}$ we associate a set $\Vert D\Vert$ of possible worlds, each possible world being a regular database.

To be more concrete, we need to fix a database model. Let us consider the relational model.

The following are incomplete database models over the relational models:

Relations with NULL values, also called Codd tables
c-tables^[1]

References

^ ^a ^b Imieliński, Tomasz; Lipski, Witold (1984-09-20). "Incomplete Information in Relational Databases". Journal of the ACM. 31 (4): 761–791. doi:10.1145/1634.1886. ISSN 0004-5411.
^ Abiteboul, Serge; Hull, Richard; Vianu, Victor (1995). "Incomplete information" (PDF). Foundations of Databases. Addison-Wesley. ISBN 0-201-53771-0.

[il1984-1] Imieliński, Tomasz; Lipski, Witold (1984-09-20). "Incomplete Information in Relational Databases". Journal of the ACM. 31 (4): 761–791. doi:10.1145/1634.1886. ISSN 0004-5411.

[2] Abiteboul, Serge; Hull, Richard; Vianu, Victor (1995). "Incomplete information" (PDF). Foundations of Databases. Addison-Wesley. ISBN 0-201-53771-0.

[1]

[2]