Baza probabilistyczna - Probabilistic database

Większość rzeczywistych baz danych zawiera dane, których poprawność jest niepewna. Aby pracować z takimi danymi, istnieje potrzeba ilościowego określenia integralności danych. Osiąga się to za pomocą probabilistycznych baz danych.

Probabilistyczny baza danych jest niepewna baza danych , w której możliwe światy są związane prawdopodobieństw . Probabilistyczne systemy zarządzania bazami danych są obecnie aktywnym obszarem badań. „Chociaż obecnie nie ma komercyjnych probabilistycznych systemów baz danych, istnieje kilka prototypów badawczych…”

Probabilistyczne bazy danych rozróżniają między logicznym modelem danych a fizyczną reprezentacją danych, podobnie jak relacyjne bazy danych w architekturze ANSI-SPARC . W probabilistycznych bazach danych jest to tym bardziej istotne, że takie bazy muszą reprezentować bardzo dużą liczbę możliwych światów, często wykładniczych w rozmiarze jednego świata ( baza klasyczna ), zwięźle .

Terminologia

W probabilistycznej bazie danych każda krotka jest powiązana z prawdopodobieństwem od 0 do 1, przy czym 0 oznacza, że ​​dane są z pewnością nieprawidłowe, a 1 oznacza, że ​​są one z pewnością poprawne.

Możliwe światy

Baza danych probabilistycznych może istnieć w wielu stanach. Na przykład, jeśli istnieje niepewność co do istnienia krotki w bazie danych, wówczas baza danych może znajdować się w dwóch różnych stanach w odniesieniu do tej krotki — pierwszy stan zawiera krotkę, a drugi nie. Podobnie, jeśli atrybut może przyjąć jedną z wartości x , y lub z , baza danych może znajdować się w trzech różnych stanach w odniesieniu do tego atrybutu.

Każdy z tych stanów nazywany jest światem możliwym.

Rozważ następującą bazę danych:

Niekompletna baza danych
ZA b
a1 b1
a2 b2
a3 {b3, b3′, b3′′}

(Tutaj {b3, b3′, b3′′} oznacza, że ​​atrybut może przyjąć dowolną z wartości b3 , b3′ lub b3′′ )

  • Zakładając, że istnieje niepewność co do pierwszej krotki, pewność co do drugiej krotki i niepewność co do wartości atrybutu B w trzeciej krotce.

Wtedy rzeczywisty stan bazy danych może zawierać lub nie pierwszą krotkę (w zależności od tego, czy jest poprawny, czy nie). Podobnie, wartością atrybutu B może być b3 , b3′ lub b3′′ .

W związku z tym możliwe światy odpowiadające bazie danych są następujące:

Świat 1
ZA b
a1 b1
a2 b2
a3 b3
Świat 2
ZA b
a1 b1
a2 b2
a3 b3′
Świat 3
ZA b
a1 b1
a2 b2
a3 b3′′
Świat 4
ZA b
a2 b2
a3 b3
Świat 5
ZA b
a2 b2
a3 b3′
Świat 6
ZA b
a2 b2
a3 b3′′

Rodzaje niepewności

Zasadniczo istnieją dwa rodzaje niepewności, które mogą istnieć w probabilistycznej bazie danych, jak opisano w poniższej tabeli:

Rodzaje niepewności
Niepewność na poziomie krotki Niepewność na poziomie atrybutów
Niepewność, czy krotka jest poprawna, czy nie, to znaczy, czy powinna istnieć w bazie danych, czy nie. Niepewność co do wartości, jakie może przyjąć atrybut krotki, to znaczy, że może przyjąć jedną z kilku możliwych wartości.
Odpowiadające każdej niepewnej krotce, istnieją dwa możliwe światy: jeden, który zawiera krotkę, a drugi nie. Odpowiadając każdemu niepewnemu atrybutowi, który może przyjąć jedną z wartości a 1 ,...,a n , istnieje n możliwych światów.
Niepewność na poziomie krotki może być postrzegana jako boolowska zmienna losowa powiązana z każdą niepewną krotką. Niepewność na poziomie atrybutu może być postrzegana jako zmienna losowa związana z każdym niepewnym atrybutem, który może przyjmować wartości a 1 ,..., an .

Przypisując wartości do zmiennych losowych powiązanych z elementami danych, można reprezentować różne możliwe światy.

Historia

Pierwsze opublikowane użycie terminu „probabilistyczna baza danych” nastąpiło prawdopodobnie w artykule z konferencji VLDB z 1987 r. „Teoria baz danych probabilistycznych” autorstwa Cavallo i Pittarelli. Tytuł (8-stronicowej pracy) miał być trochę żartem, ponieważ 600-stronicowa monografia Davida Maiera Teoria relacyjnych baz danych byłaby wówczas znana większości uczestników konferencji i czytelników materiałów konferencyjnych. .

Bibliografia

  1. ^ Vinod Muthusamy, Haifeng Liu, Hans-Arno Jacobsen: Przewidywanie publikowania/subskrybowania dopasowywania. Uniwersytet w Toronto.
  2. ^ Nilesh N. Dalvi , Dan Suciu : Efektywna ocena zapytań na probabilistycznych bazach danych. VLDB J. 16(4): 523-544 (2007)
  3. ^ Lyublena Antova , Christoph Koch , Dan Olteanu : 10^(10^6) Worlds and Beyond: Efektywna reprezentacja i przetwarzanie niekompletnych informacji. ICDE 2007: 606-615

Linki zewnętrzne