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..." Vinod Muthusamy, Haifeng Liu, Hans-Arno Jacobsen: Predictive Publish/Subscribe Matching. University of Toronto.

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

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 4ABa2b2a3b3 +Mondo 5ABa2b2a3b3′ +Mondo 6ABa2b2a3b3′′

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

Collegamenti esterni 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 )

Categoria:Teoria delle basi di dati Categoria:Database management system Categoria:Ragionamento probabilistico