Pravděpodobnostní databáze - Probabilistic database

Většina skutečných databází obsahuje data, jejichž správnost je nejistá. Aby bylo možné s takovými daty pracovat, je nutné kvantifikovat integritu dat. Toho je dosaženo použitím pravděpodobnostních databází.

A pravděpodobnostní databáze je nejistá databáze ve kterém možné světy přidružili pravděpodobnosti. Pravděpodobnostní systémy pro správu databází jsou v současné době aktivní oblastí výzkumu. „I když v současné době neexistují žádné komerční pravděpodobnostní databázové systémy, existuje několik výzkumných prototypů ...“[1]

Pravděpodobnostní databáze rozlišují mezi logický datový model a podobná fyzická reprezentace dat relační databáze dělat v Architektura ANSI-SPARC V pravděpodobnostních databázích je to ještě důležitější, protože tyto databáze musí představovat velmi velký počet možných světů, často exponenciálních ve velikosti jednoho světa (klasický databáze ), stručně.[2][3]

Terminologie

V pravděpodobnostní databázi je každá n-tice spojena s pravděpodobností mezi 0 a 1, kde 0 představuje, že data jsou jistě nesprávná, a 1 představuje, že je jistě správná.

Možné světy

Pravděpodobnostní databáze by mohla existovat ve více státech. Například pokud si nejsme jisti existencí n-tice v databázi, pak by databáze mohla být ve dvou různých stavech vzhledem k této n-tice - první stav obsahuje n-tici, zatímco druhý nikoli. Podobně, pokud atribut může nabývat jedné z hodnot X, y nebo z, pak může být databáze ve třech různých stavech s ohledem na tento atribut.

Každý z těchto státy se nazývá možný svět.

Zvažte následující databázi:

Neúplná databáze
AB
a1b1
a2b2
a3{b3, b3 ′, b3 ′ ′}

(Tady {b3, b3 ′, b3 ′ ′} označuje, že atribut může nabývat kterékoli z hodnot b3,b3 ' nebo b3 ′ ′)

  • Předpokládejme, že si nejsme jisti první n-ticí, jistou druhou n-ticí a nejistou hodnotou atributu B ve třetí n-tici.

Skutečný stav databáze pak může nebo nemusí obsahovat první n-tici (podle toho, zda je správná nebo ne). Podobně hodnota atributu B možná b3,b3 ' nebo b3 ′ ′.

Možné světy odpovídající databázi jsou tedy následující:

Svět 1
AB
a1b1
a2b2
a3b3
Svět 2
AB
a1b1
a2b2
a3b3 '
Svět 3
AB
a1b1
a2b2
a3b3 ′ ′
Svět 4
AB
a2b2
a3b3
Svět 5
AB
a2b2
a3b3 '
Svět 6
AB
a2b2
a3b3 ′ ′

Druhy nejistot

V pravděpodobnostní databázi mohou existovat v zásadě dva druhy nejistot, jak je popsáno v následující tabulce:

Druhy nejistot
Nejistota na úrovni n-ticeNejistota na úrovni atributů
Tady si nejsme jisti, zda je n-tice správná nebo ne, tedy zda by měla existovat v databázi nebo ne.Tady si nejsme jisti hodnotami, které může mít atribut n-tice, to znamená, že by mohl mít jednu z několika možných hodnot.
Odpovídající každé nejisté n-tici existují dva možné světy: jeden, který obsahuje n-tici, a druhý, který nikoli.Odpovídá každému nejistému atributu, který může nabývat jedné z hodnot A1,...,An, existují n možné světy.
Nejistotu na úrovni n-tice lze považovat za booleovskou náhodnou proměnnou spojenou s každou nejistou n-ticí.Nejistotu na úrovni atributu lze považovat za náhodnou proměnnou spojenou s každým nejistým atributem, která může nabývat hodnot A1,...,An.

Přiřazením hodnot náhodným proměnným přidruženým k datovým položkám můžeme představovat různé možné světy.

Dějiny

První publikované použití termínu „pravděpodobnostní databáze“ bylo pravděpodobně v konferenčním příspěvku VLDB z roku 1987 „Teorie pravděpodobnostních databází“, autori Cavallo a Pittarelli.[Citace je zapotřebí ] Název (8stránkového příspěvku) byl zamýšlen jako trochu vtip, protože 600stránková monografie Davida Maiera Theory of Relational Database byla v té době známá většině účastníků konference a čtenářům sborníku konference .

Reference

  1. ^ Vinod Muthusamy, Haifeng Liu, Hans-Arno Jacobsen: Prediktivní publikování / odběr shody. University of Toronto.
  2. ^ Nilesh N. Dalvi, Dan Suciu: Efektivní vyhodnocení dotazu na pravděpodobnostních databázích. VLDB J. 16 (4): 523-544 (2007)
  3. ^ Lyublena Antova, Christoph Koch, Dan Olteanu: 10 ^ (10 ^ 6) Worlds and Beyond: Efektivní reprezentace a zpracování neúplných informací. ICDE 2007: 606-615

externí odkazy