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..."

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.

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:

(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:

Tipi di incertezza

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

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. 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.