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, that form extensions to the relational algebra that have been called^[3] Imieliński–Lipski algebra:

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

References

^ ^a ^b ^c 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.
^ Green, Todd J.; Karvounarakis, Grigoris; Tannen, Val (2007-06-11). "Provenance semirings". Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. PODS '07. New York, NY, USA: Association for Computing Machinery: 31–40. doi:10.1145/1265530.1265535. ISBN 978-1-59593-685-1.

[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.

[3] Green, Todd J.; Karvounarakis, Grigoris; Tannen, Val (2007-06-11). "Provenance semirings". Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. PODS '07. New York, NY, USA: Association for Computing Machinery: 31–40. doi:10.1145/1265530.1265535. ISBN 978-1-59593-685-1.

[1]

[2]

[3]