Probabilistisk database - Probabilistic database

De fleste virkelige databaser inneholder data som er usikre på korrektheten. For å jobbe med slike data er det behov for å tallfeste dataintegriteten. Dette oppnås ved bruk av sannsynlighetsdatabaser.

En sannsynlighetsdatabase er en usikker database der mulige verdener har tilhørende sannsynligheter . Probabilistiske databasesystemer er for tiden et aktivt forskningsområde. "Selv om det for tiden ikke er kommersielle sannsynlighetsdatabasesystemer, finnes det flere forskningsprototyper ..."

Probabilistiske databaser skiller mellom den logiske datamodellen og den fysiske representasjonen av dataene omtrent som relasjonsdatabaser gjør i ANSI-SPARC Architecture . I sannsynlighetsdatabaser er dette enda viktigere, siden slike databaser må representere et stort antall mulige verdener, ofte eksponentielt i størrelsen på en verden (en klassisk database ), kortfattet .

Terminologi

I en sannsynlighetsdatabase er hver tuple assosiert med en sannsynlighet mellom 0 og 1, hvor 0 representerer at dataene absolutt er feil, og 1 som representerer at de absolutt er korrekte.

Mulige verdener

En sannsynlig database kan eksistere i flere stater. For eksempel, hvis det er usikkerhet om eksistensen av en tupel i databasen, kan databasen være i to forskjellige tilstander med hensyn til den tupelen - den første tilstanden inneholder tupelen, mens den andre ikke gjør det. Tilsvarende, hvis et attributt kan ta en av verdiene x , y eller z , kan databasen være i tre forskjellige tilstander med hensyn til det attributtet.

Hver av disse tilstandene kalles en mulig verden.

Vurder følgende database:

En ufullstendig database
EN B
a1 b1
a2 b2
a3 {b3, b3 ′, b3 ′ ′}

(Her angir {b3, b3 ′, b3 ′ ′} at attributtet kan ta noen av verdiene b3 , b3 ′ eller b3 ′ ′ )

  • Forutsatt at det er usikkerhet om den første tupelen, sikkerheten om den andre tupelen, og usikkerheten om verdien av attributt B i den tredje tupelen.

Da kan den faktiske tilstanden til databasen inneholde den første tupelen eller ikke (avhengig av om den er riktig eller ikke). Tilsvarende kan verdien av attributtet B være b3 , b3 ' eller b3' ' .

Følgelig er de mulige verdenene som tilsvarer databasen som følger:

Verden 1
EN B
a1 b1
a2 b2
a3 b3
Verden 2
EN B
a1 b1
a2 b2
a3 b3 ′
Verden 3
EN B
a1 b1
a2 b2
a3 b3 ′ ′
Verden 4
EN B
a2 b2
a3 b3
Verden 5
EN B
a2 b2
a3 b3 ′
Verden 6
EN B
a2 b2
a3 b3 ′ ′

Typer av usikkerheter

Det er i hovedsak to slags usikkerheter som kan eksistere i en sannsynlighetsdatabase, som beskrevet i tabellen nedenfor:

Typer av usikkerheter
Usikkerhet på to nivåer Usikkerhet på attributtnivå
Usikkerhet om en tuple er riktig eller ikke, det vil si om den skal eksistere i databasen eller ikke. Usikkerhet om verdiene som et attributt til en tupel kan ta, det vil si at det kan ta en av de flere mulige verdiene.
Tilsvarende hver usikker tuple er det to mulige verdener: en som inkluderer tupelen, mens den andre ikke gjør det. Tilsvarende hver usikre attributt som kan ta en av verdiene a 1 , ..., a n , er det n mulige verdener.
Usikkerhet på tonivå kan sees på som en boolsk tilfeldig variabel assosiert med hver usikker tuple. Usikkerhet på attributtnivå kan sees på som en tilfeldig variabel assosiert med hvert usikkert attributt som kan ta verdiene a 1 , ..., a n .

Ved å tilordne verdier til tilfeldige variabler tilknyttet dataelementene, kan forskjellige mulige verdener representeres.

Historie

Den første publiserte bruken av begrepet "probabilistisk database" var sannsynligvis i VLDB-konferanseavisen "The theory of probabilistic databases" fra 1987, av Cavallo og Pittarelli. Tittelen (på papiret på 8 sider) var ment som en litt vits, siden David Maiers monografi på 600 sider, Theory of Relational Databases, ville vært kjent på den tiden for de fleste av konferansedeltakerne og leserne av konferansesaken. .

Referanser

  1. ^ Vinod Muthusamy, Haifeng Liu, Hans-Arno Jacobsen: Predictive Publish / Subscribe Matching. University of Toronto.
  2. ^ Nilesh N. Dalvi , Dan Suciu : Effektiv spørreevaluering på sannsynlighetsdatabaser. VLDB J. 16 (4): 523-544 (2007)
  3. ^ Lyublena Antova , Christoph Koch , Dan Olteanu : 10 ^ (10 ^ 6) Worlds and Beyond: Effektiv representasjon og behandling av ufullstendig informasjon. ICDE 2007: 606-615

Eksterne linker