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

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

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:

Un database incompleto
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:

Mondo 1
A	B
a1	b1
a2	b2
a3	b3

Mondo 2
A	B
a1	b1
a2	b2
a3	b3'

Mondo 3
A	B
a1	b1
a2	b2
a3	b3''

Mondo 4
A	B
a2	b2
a3	b3

Mondo 5
A	B
a2	b2
a3	b3′

Mondo 6
A	B
a2	b2
a3	b3′′

Tipi di incertezza

Esistono essenzialmente due tipi di incertezza che potrebbero essere in un database probabilistico, così come descritto nella tabella seguente:

Tipi di incertezza
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 a₁,...,a_n, 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 a₁,...,a_n.

Assegnando valori alle variabili aleatorie associate a tuple e attributi incerti, si possono rappresentare diversi mondi possibili.

Storia

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

^ 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)