Incomplete database

An incomplete database^[1]^[2] 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^[3] Imieliński–Lipski algebras:

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. pp. 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. pp. 31–40. doi:10.1145/1265530.1265535. ISBN 978-1-59593-685-1.

[1]

[2]

[3]