Probabilistisk databas

De flesta riktiga databaser innehåller data vars riktighet är osäker. För att kunna arbeta med sådan data finns det ett behov av att kvantifiera dataintegriteten. Detta uppnås genom att använda probabilistiska databaser.

En probabilistisk databas är en osäker databas där de möjliga världarna har associerade sannolikheter . Probabilistiska databashanteringssystem är för närvarande ett aktivt forskningsområde. "Även om det för närvarande inte finns några kommersiella probabilistiska databassystem, finns det flera forskningsprototyper..."

Probabilistiska databaser skiljer mellan den logiska datamodellen och den fysiska representationen av data, ungefär som relationsdatabaser gör i ANSI-SPARC-arkitekturen . I probabilistiska databaser är detta ännu mer avgörande eftersom sådana databaser måste representera ett mycket stort antal möjliga världar, ofta exponentiella i storleken av en värld (en klassisk databas ), kortfattat .

Terminologi

I en sannolikhetsdatabas är varje tupel associerad med en sannolikhet mellan 0 och 1, där 0 representerar att data säkert är felaktiga och 1 representerar att det verkligen är korrekt.

Möjliga världar

En probabilistisk databas kan finnas i flera stater. Till exempel, om det finns osäkerhet om förekomsten av en tuppel i databasen, kan databasen vara i två olika tillstånd med avseende på den tupeln - det första tillståndet innehåller tupeln, medan det andra inte gör det. På liknande sätt, om ett attribut kan ta ett av värdena x , y eller z , kan databasen vara i tre olika tillstånd med avseende på det attributet.

Var och en av dessa tillstånd kallas en möjlig värld.

Tänk på följande databas:

En ofullständig databas

A	B
a1	b1
a2	b2
a3	{b3, b3′, b3′′}

(Här anger {b3, b3′, b3′′} att attributet kan ta vilket som helst av värdena b3 , b3′ eller b3′′ )

• Om man antar att det råder osäkerhet om den första tupeln, säkerhet om den andra tupeln och osäkerhet om värdet av attribut B i den tredje tupeln.

Då kan databasens faktiska tillstånd innehålla eller inte innehålla den första tupeln (beroende på om den är korrekt eller inte). På liknande sätt kan värdet på attributet B vara b3 , b3′ eller b3′′ .

Följaktligen är de möjliga världarna som motsvarar databasen följande:

Värld 1

A	B
a1	b1
a2	b2
a3	b3

Värld 2

A	B
a1	b1
a2	b2
a3	b3′

Värld 3

A	B
a1	b1
a2	b2
a3	b3′′

Värld 4

A	B
a2	b2
a3	b3

Värld 5

A	B
a2	b2
a3	b3′

Värld 6

A	B
a2	b2
a3	b3′′

Typer av osäkerheter

Det finns i huvudsak två typer av osäkerheter som kan finnas i en probabilistisk databas, som beskrivs i tabellen nedan:

Typer av osäkerheter

Osäkerhet på tupelnivå	Osäkerhet på attributnivå
Osäkerhet om en tupel är korrekt eller inte, det vill säga om den ska finnas i databasen eller inte.	Osäkerhet om de värden som ett attribut hos en tuppel kan ta, det vill säga det kan ta ett av flera möjliga värden.
Motsvarande varje osäker tupel finns det två möjliga världar: en som inkluderar tupeln medan den andra som inte gör det.	Motsvarande varje osäkert attribut som kan ta ett av värdena a 1 ,...,a n , finns det n möjliga världar.
Osäkerhet på tuppelnivå kan ses som en boolesk slumpvariabel associerad med varje osäker tupel.	Osäkerhet på attributnivå kan ses som en slumpvariabel associerad med varje osäker attribut som kan ta värdena a 1 ,...,a n .

Genom att tilldela värden till slumpvariabler associerade med dataposterna kan olika möjliga världar representeras.

Historia

Den första publicerade användningen av termen "probabilistic databas" var förmodligen i 1987 VLDB konferensrapport "The theory of probabilistic databases", av Cavallo och Pittarelli. Titeln (på det 11 sidor långa uppsatsen) var tänkt som lite av ett skämt, eftersom David Maiers 600-sidiga monografi, The Theory of Relational Databases, skulle ha varit bekant vid den tiden för de flesta av konferensdeltagarna och läsarna av konferenshandlingarna .

externa länkar

• MayBMS-projektet vid Cornell University ( sourceforge.net-projektwebbplatsen )
• MystiQ - projektet vid University of Washington
• Orion - projektet vid Purdue University
• Trioprojektet vid Stanford University
• BayesStore - projektet vid University of California, Berkeley
• PrDB - projektet vid University of Maryland, College Park
• Mimir - projektet vid universitetet i Buffalo