Uncertain database

An uncertain database is a kind of database studied in database theory.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

An uncertain database[1] is a kind of database studied in database theory. The goal of uncertain databases is to manage information on which there is some uncertainty. Uncertain databases make it possible to explicitly represent and manage uncertainty on the data, usually in a succinct way.

Contents

Formal definition

edit edit source

At the basis of uncertain databases is the notion of possible world. 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

edit edit source

Uncertain database models differ in how they represent and quantify these possible worlds:

Though mostly studied in the relational setting, uncertain database models can also be defined in other relational models such as graph databases[6] or XML databases.

Incomplete database

edit edit source

The most common database model 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[7] Imieliński–Lipski algebras:

  • Relations with NULL values, also called Codd tables
  • c-tables[2]
  • v-tables[2]

Example

edit edit source

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

References

edit edit source
  1. ^ Aggarwal, Charu C., ed. (2009). Managing and Mining Uncertain Data. Advances in Database Systems. Vol. 35. Bibcode:2009mmud.book.....A. doi:10.1007/978-0-387-09690-2. ISBN 978-0-387-09689-6. ISSN 1386-2944. Wikipedia revision 1292435540, retrieved 2026-11-20
  2. ^ 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. Wikipedia revision 1292435540, retrieved 2026-11-20
  3. ^ Abiteboul, Serge; Hull, Richard; Vianu, Victor (1995). "Incomplete information" (PDF). Foundations of Databases. Addison-Wesley. ISBN 0-201-53771-0. Wikipedia revision 1292435540, retrieved 2026-11-20
  4. ^ Suciu, Dan; Olteanu, Dan; Ré, Christopher; Koch, Christoph (2011). "Probabilistic Databases". Synthesis Lectures on Data Management. doi:10.1007/978-3-031-01879-4. ISBN 978-3-031-00751-4. ISSN 2153-5418. S2CID 264145434.{{cite journal}}: CS1 maint: periodical has ISBN (link) Wikipedia revision 1292435540, retrieved 2026-11-20
  5. ^ Petry, Frederick E. (1996). "Fuzzy Databases". International Series in Intelligent Technologies. 5. doi:10.1007/978-1-4613-1319-9. ISBN 978-1-4612-8566-3. ISSN 1382-3434.{{cite journal}}: CS1 maint: periodical has ISBN (link) Wikipedia revision 1292435540, retrieved 2026-11-20
  6. ^ Khan, Arijit; Ye, Yuan; Chen, Lei (2018). "On Uncertain Graphs". Synthesis Lectures on Data Management. doi:10.1007/978-3-031-01860-2. ISBN 978-3-031-00732-3. ISSN 2153-5418.{{cite journal}}: CS1 maint: periodical has ISBN (link) Wikipedia revision 1292435540, retrieved 2026-11-20
  7. ^ 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. Wikipedia revision 1292435540, retrieved 2026-11-20

Text derived from https://en.wikipedia.org/w/index.php?oldid=1292435540 under CC BY-SA 4.0; modifications have been made.