Database probabilistico
La maggior parte dei database reali contengono dati la cui correttezza è incerta. Per poter lavorare con tali dati è necessario quantificarne l'integrità. Si può raggiungere tale obiettivo utilizzando database probabilistici.
Un database probabilistico è un tipo di database incerto in cui ai mondi possibili (definiti nel seguito) sono associate delle probabilità. I sistemi di gestione di database probabilistici costituiscono attualmente un campo di ricerca molto attivo. "Sebbene attualmente non esistano sistemi commerciali per la gestione di database probabilistici, esistono diversi prototipi proposti dalla ricerca..." [1]
I database probabilistici distinguono il modello logico dei dati dalla rappresentazione fisica dei dati, proprio come i database relazionali nell'architettura ANSI-SPARC. Nei database probabilistici ciò è ancora più importante poiché tali database devono rappresentare un numero molto grande di mondi possibili, spesso esponenziale nella dimensione di un mondo (un database classico), in modo succinto.[2][3]
Terminologia
[modifica | modifica wikitesto]In un database probabilistico, a ogni tupla è associata una probabilità compresa tra 0 e 1, dove 0 rappresenta il fatto che i dati siano sicuramente errati e 1 il fatto che siano sicuramente corretti.
Mondi possibili
[modifica | modifica wikitesto]Un database probabilistico può trovarsi in più stati. Ad esempio, se non vi è certezza sull'esistenza di una tupla nel database, esso si potrebbe trovare in due stati distinti rispetto a tale tupla: il primo contiene la tupla, mentre il secondo non la contiene. Allo stesso modo, se un attributo può assumere uno dei valori x, y o z, allora il database può trovarsi in tre stati distinti rispetto a quell'attributo.
Ciascuno di questi stati si definisce come mondo possibile.
Si consideri il seguente database:
| A | B |
|---|---|
| a1 | b1 |
| a2 | b2 |
| a3 | {b3, b3′, b3′′} |
(Qui l'insieme {b3, b3′, b3′′} indica che l'attributo può assumere uno qualunque dei valori b3, b3′ o b3′′ )
Si assuma che vi sia incertezza sulla prima tupla, certezza sulla seconda tupla e incertezza sul valore dell'attributo B nella terza tupla.
In tal caso lo stato effettivo del database potrebbe contenere o meno la prima tupla (a seconda che sia corretta o meno). Analogamente, il valore dell'attributo B può essere b3, b3′ o b3′′. Di conseguenza, i mondi possibili corrispondenti al database incompleto sono i seguenti:
| A | B |
|---|---|
| a1 | b1 |
| a2 | b2 |
| a3 | b3 |
| A | B |
|---|---|
| a1 | b1 |
| a2 | b2 |
| a3 | b3' |
| A | B |
|---|---|
| a1 | b1 |
| a2 | b2 |
| a3 | b3'' |
| A | B |
|---|---|
| a2 | b2 |
| a3 | b3 |
| A | B |
|---|---|
| a2 | b2 |
| a3 | b3′ |
| A | B |
|---|---|
| a2 | b2 |
| a3 | b3′′ |
Tipi di incertezza
[modifica | modifica wikitesto]Esistono essenzialmente due tipi di incertezza che potrebbero essere in un database probabilistico, così come descritto nella tabella seguente:
| Incertezza a livello di tupla | Incertezza a livello di attributo |
|---|---|
| Incertezza sulla correttezza di una tupla, ossia sul fatto che debba esistere o meno nel database. | Incertezza sui valori che può assumere un attributo di una tupla, ovvero sulla possibilità di assumere uno dei diversi valori del suo dominio. |
| A ogni tupla incerta corrispondono due mondi possibili: uno che contiene la tupla e uno che non la contiene. | In corrispondenza di ciascun attributo incerto che possa assumere uno fra i valori a1,...,an, si hanno n mondi possibili. |
| L'incertezza a livello di tupla può essere vista come una variabile aleatoria booleana associata a ciascuna tupla incerta. | L'incertezza a livello di attributo può essere vista come una variabile aleatoria associata a ciascun attributo incerto che può assumere valori a1,...,an. |
Assegnando valori alle variabili aleatorie associate a tuple e attributi incerti, si possono rappresentare diversi mondi possibili.
Storia
[modifica | modifica wikitesto]Il primo utilizzo del termine "database probabilistico" in una pubblicazione è stato probabilmente nel documento della conferenza VLDB del 1987 "The theory of probabilistic databases", di Cavallo e Pittarelli.[4] Il titolo dell'articolo (di 11 pagine) voleva richiamare quello di "The Theory of Relational Databases" di David Maier, un noto testo di 600 pagine, familiare a molti dei partecipanti alla conferenza e dei lettori dei suoi atti.
Note
[modifica | modifica wikitesto]- ^ Vinod Muthusamy, Haifeng Liu, Hans-Arno Jacobsen: Predictive Publish/Subscribe Matching. University of Toronto.
- ^ Nilesh N. Dalvi, Dan Suciu: Efficient query evaluation on probabilistic databases. VLDB J. 16(4): 523–544 (2007)
- ^ Lyublena Antova, Christoph Koch, Dan Olteanu: 10^(10^6) Worlds and Beyond: Efficient Representation and Processing of Incomplete Information. ICDE 2007: 606–615
- ^ Roger Cavallo, Michael Pittarelli: The Theory of Probabilistic Databases. In VLDB'87, Proceedings of 13th International Conference on Very Large Data Bases, September 1–4, 1987, Brighton: 71–81 (1987)
Collegamenti esterni
[modifica | modifica wikitesto]- Progetto MayBMS presso la Cornell University (sito del progetto su sourceforge.net)
- Progetto MystiQ presso l'Università di Washington
- Progetto Orion presso la Purdue University
- Progetto Trio presso la Stanford University
- Progetto BayesStore presso l'Università della California, Berkeley
- Progetto PrDB presso l'Università del Maryland, College Park
- Progetto Mimir presso l'Università di Buffalo
- Progetto ProvSQL presso l'École normale supérieure (Parigi) (modulo per PostgreSQL )