Banco de dados probabilístico - Probabilistic database

A maioria dos bancos de dados reais contém dados cuja exatidão é incerta. Para trabalhar com esses dados, é necessário quantificar a integridade dos dados. Isso é conseguido usando bancos de dados probabilísticos.

Um banco de dados probabilístico é um banco de dados incerto no qual os mundos possíveis têm probabilidades associadas . Os sistemas de gerenciamento de banco de dados probabilísticos são atualmente uma área ativa de pesquisa. "Embora atualmente não existam sistemas de banco de dados probabilísticos comerciais, existem vários protótipos de pesquisa ..."

Os bancos de dados probabilísticos distinguem entre o modelo de dados lógico e a representação física dos dados de maneira muito semelhante à que os bancos de dados relacionais fazem na Arquitetura ANSI-SPARC . Em bancos de dados probabilísticos, isso é ainda mais crucial, uma vez que tais bancos de dados têm que representar um grande número de mundos possíveis, muitas vezes exponenciais no tamanho de um mundo (um banco de dados clássico ), de forma sucinta .

Terminologia

Em um banco de dados probabilístico, cada tupla está associada a uma probabilidade entre 0 e 1, com 0 representando que os dados estão certamente incorretos e 1 representando que estão certamente corretos.

Mundos possíveis

Um banco de dados probabilístico pode existir em vários estados. Por exemplo, se houver incerteza sobre a existência de uma tupla no banco de dados, então o banco de dados poderia estar em dois estados diferentes com relação a essa tupla - o primeiro estado contém a tupla, enquanto o segundo não. Da mesma forma, se um atributo pode assumir um dos valores x , y ou z , então o banco de dados pode estar em três estados diferentes com relação a esse atributo.

Cada um desses estados é chamado de mundo possível.

Considere o seguinte banco de dados:

Um banco de dados incompleto
UMA B
a1 b1
a2 b2
a3 {b3, b3 ′, b3 ′ ′}

(Aqui {b3, b3 ′, b3 ′ ′} denota que o atributo pode assumir qualquer um dos valores b3 , b3 ′ ou b3 ′ ′ )

  • Supondo que haja incerteza sobre a primeira tupla, certeza sobre a segunda tupla e incerteza sobre o valor do atributo B na terceira tupla.

Então, o estado real do banco de dados pode ou não conter a primeira tupla (dependendo se está correto ou não). Da mesma forma, o valor do atributo B pode ser b3 , b3 ′ ou b3 ′ ′ .

Consequentemente, os mundos possíveis correspondentes ao banco de dados são os seguintes:

Mundo 1
UMA B
a1 b1
a2 b2
a3 b3
Mundo 2
UMA B
a1 b1
a2 b2
a3 b3 ′
Mundo 3
UMA B
a1 b1
a2 b2
a3 b3 ′ ′
Mundo 4
UMA B
a2 b2
a3 b3
Mundo 5
UMA B
a2 b2
a3 b3 ′
Mundo 6
UMA B
a2 b2
a3 b3 ′ ′

Tipos de incertezas

Existem essencialmente dois tipos de incertezas que podem existir em um banco de dados probabilístico, conforme descrito na tabela abaixo:

Tipos de incertezas
Incerteza no nível de tupla Incerteza de nível de atributo
Incerteza se uma tupla está correta ou não, ou seja, se deveria ou não existir no banco de dados. Incerteza sobre os valores que um atributo de uma tupla pode assumir, ou seja, pode assumir um dos vários valores possíveis.
Correspondendo a cada tupla incerta, existem dois mundos possíveis: um que inclui a tupla e o outro que não inclui. Correspondendo a cada atributo incerto que pode assumir um dos valores a 1 , ..., a n , existem n mundos possíveis.
A incerteza no nível da tupla pode ser vista como uma variável aleatória booleana associada a cada tupla incerta. A incerteza de nível de atributo pode ser vista como uma variável aleatória associada a cada atributo incerto que pode assumir valores a 1 , ..., a n .

Ao atribuir valores a variáveis ​​aleatórias associadas aos itens de dados, diferentes mundos possíveis podem ser representados.

História

O primeiro uso publicado do termo "banco de dados probabilísticos" foi provavelmente no artigo da conferência do VLDB de 1987 "A teoria dos bancos de dados probabilísticos", de Cavallo e Pittarelli. O título (do artigo de 8 páginas) pretendia ser uma piada, uma vez que a monografia de 600 páginas de David Maier, The Theory of Relational Databases, seria familiar na época para a maioria dos participantes da conferência e leitores dos anais da conferência. .

Referências

  1. ^ Vinod Muthusamy, Haifeng Liu, Hans-Arno Jacobsen: Correspondência de publicação / assinatura preditiva. Universidade de Toronto.
  2. ^ Nilesh N. Dalvi , Dan Suciu : Avaliação eficiente da consulta em bancos de dados probabilísticos. VLDB J. 16 (4): 523-544 (2007)
  3. ^ Lyublena Antova , Christoph Koch , Dan Olteanu : 10 ^ (10 ^ 6) Mundos e além: Representação eficiente e processamento de informações incompletas. ICDE 2007: 606-615

links externos