Uncertain database#Types of uncertain databases
{{Short description|Type of database}}
An uncertain database{{Cite book |date=2009 |editor-last=Aggarwal |editor-first=Charu C. |title=Managing and Mining Uncertain Data |url=https://link.springer.com/book/10.1007/978-0-387-09690-2 |series=Advances in Database Systems |volume=35 |language=en |doi=10.1007/978-0-387-09690-2 |bibcode=2009mmud.book.....A |isbn=978-0-387-09689-6 |issn=1386-2944}} 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.
Formal definition
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
Uncertain database models differ in how they represent and quantify these possible worlds:
- Incomplete databases{{Cite journal |last1=Imieliński |first1=Tomasz |last2=Lipski |first2=Witold |date=1984-09-20 |title=Incomplete Information in Relational Databases |url=https://dl.acm.org/doi/10.1145/1634.1886 |journal=Journal of the ACM |language=en |volume=31 |issue=4 |pages=761–791 |doi=10.1145/1634.1886 |issn=0004-5411|author-link=Tomasz Imieliński|author-link2=Witold Lipski}}{{Cite book |last1=Abiteboul |first1=Serge |url=http://webdam.inria.fr/Alice/ |title=Foundations of Databases |last2=Hull |first2=Richard |last3=Vianu |first3=Victor |publisher=Addison-Wesley |year=1995 |isbn=0-201-53771-0 |author-link=Serge Abiteboul |author-link3=Victor Vianu|chapter=Incomplete information|chapter-url=http://webdam.inria.fr/Alice/pdfs/Chapter-19.pdf}} are a compact representation of the set of possible worlds – the use of NULL in SQL, arguably the most commonplace instantiation of uncertain databases, is an example of incomplete database model.
- Probabilistic databases{{Cite journal |last1=Suciu |first1=Dan |last2=Olteanu |first2=Dan |last3=Ré |first3=Christopher |last4=Koch |first4=Christoph |date=2011 |title=Probabilistic Databases |url=https://link.springer.com/book/10.1007/978-3-031-01879-4 |journal=Synthesis Lectures on Data Management |language=en |doi=10.1007/978-3-031-01879-4 |isbn=978-3-031-00751-4 |s2cid=264145434 |issn=2153-5418|author-link=Dan Suciu|author-link3=Christopher Ré}} are a compact representation of a probability distribution over the set of possible worlds.
- Fuzzy databases{{Cite journal |last=Petry |first=Frederick E. |date=1996 |title=Fuzzy Databases |url=https://link.springer.com/book/10.1007/978-1-4613-1319-9 |journal=International Series in Intelligent Technologies |volume=5 |language=en |doi=10.1007/978-1-4613-1319-9 |isbn=978-1-4612-8566-3 |issn=1382-3434}} are a compact representation of a fuzzy set of the possible worlds.
Though mostly studied in the relational setting, uncertain database models can also be defined in other relational models such as graph databases{{Cite journal |last1=Khan |first1=Arijit |last2=Ye |first2=Yuan |last3=Chen |first3=Lei |date=2018 |title=On Uncertain Graphs |url=https://link.springer.com/book/10.1007/978-3-031-01860-2 |journal=Synthesis Lectures on Data Management |language=en |doi=10.1007/978-3-031-01860-2 |isbn=978-3-031-00732-3 |issn=2153-5418}} or XML databases.
=Incomplete database=
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{{Cite book |last1=Green |first1=Todd J. |last2=Karvounarakis |first2=Grigoris |last3=Tannen |first3=Val |chapter=Provenance semirings |date=2007-06-11 |title=Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems |chapter-url=https://doi.org/10.1145/1265530.1265535 |series=PODS '07 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=31–40 |doi=10.1145/1265530.1265535 |isbn=978-1-59593-685-1}} Imieliński–Lipski algebras:
= Example =
The following table is a relation of an incomplete database, described in the formalism of NULL values:
| class="wikitable" |
| 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:
| class="wikitable" |
| id
! Name ! Salary |
|---|
| 1
| Alice | 10,000 |
| 2
| Bob | 8,000 |
| 3
| Charlie | 12,000 |