Вероятностная база данных - Probabilistic database

Большинство реальных баз данных содержат данные, правильность которых сомнительна. Чтобы работать с такими данными, необходимо количественно оценить целостность данных. Это достигается за счет использования вероятностных баз данных.

А вероятностная база данных является неопределенная база данных в которой возможные миры связаны вероятности. Вероятностный системы управления базами данных в настоящее время являются активной областью исследований. «Хотя в настоящее время нет коммерческих систем вероятностных баз данных, существует несколько исследовательских прототипов ...»[1]

Вероятностные базы данных различают логическая модель данных и физическое представление данных очень похоже на реляционные базы данных делать в Архитектура ANSI-SPARC В вероятностных базах данных это еще более важно, поскольку такие базы данных должны представлять очень большое количество возможных миров, часто экспоненциально по размеру одного мира (классический база данных ), лаконично.[2][3]

Терминология

В вероятностной базе данных каждый кортеж связан с вероятностью от 0 до 1, где 0 означает, что данные определенно неверны, а 1 означает, что они определенно верны.

Возможные миры

Вероятностная база данных может существовать в нескольких состояниях. Например, если мы не уверены в существовании кортежа в базе данных, то база данных может находиться в двух разных состояниях по отношению к этому кортежу - первое состояние содержит кортеж, а второе - нет. Аналогично, если атрибут может принимать одно из значений Икс, у или z, то база данных может находиться в трех разных состояниях по отношению к этому атрибуту.

Каждый из них состояния называется возможным миром.

Рассмотрим следующую базу данных:

Неполная база данных
АB
а1b1
а2Би 2
а3{b3, b3 ′, b3 ′ ′}

(Вот {b3, b3 ′, b3 ′ ′} означает, что атрибут может принимать любое из значений b3,b3 ′ или b3 ′ ′)

  • Предположим, что мы не уверены в первом кортеже, уверены во втором кортеже и не уверены в значении атрибута B в третьем кортеже.

Тогда фактическое состояние базы данных может содержать или не содержать первый кортеж (в зависимости от того, правильный он или нет). Аналогично значение атрибута B может быть b3,b3 ′ или b3 ′ ′.

Следовательно, возможные миры, соответствующие базе данных, следующие:

Мир 1
АB
а1b1
а2Би 2
а3b3
Мир 2
АB
а1b1
а2Би 2
а3b3 ′
Мир 3
АB
а1b1
а2Би 2
а3b3 ′ ′
Мир 4
АB
а2Би 2
а3b3
Мир 5
АB
а2Би 2
а3b3 ′
Мир 6
АB
а2Би 2
а3b3 ′ ′

Типы неопределенностей

По сути, существует два вида неопределенностей, которые могут существовать в вероятностной базе данных, как описано в таблице ниже:

Типы неопределенностей
Неопределенность на уровне кортежаНеопределенность на уровне атрибутов
Здесь мы не уверены, правильный кортеж или нет, то есть должен ли он существовать в базе данных или нет.Здесь мы не уверены в том, какие значения может принимать атрибут кортежа, то есть он может принимать одно из нескольких возможных значений.
В соответствии с каждым неопределенным кортежем существует два возможных мира: один включает кортеж, а другой - нет.Соответствует каждому неопределенному атрибуту, который может принимать одно из значений а1, ..., ап, есть п возможные миры.
Неопределенность на уровне кортежа можно рассматривать как логическую случайную величину, связанную с каждым неопределенным кортежем.Неопределенность на уровне атрибута можно рассматривать как случайную величину, связанную с каждым неопределенным атрибутом, которая может принимать значения. а1, ..., ап.

Присваивая значения случайным переменным, связанным с элементами данных, мы можем представлять различные возможные миры.

История

Впервые термин «вероятностная база данных» был опубликован, вероятно, в статье Кавалло и Питтарелли на конференции VLDB 1987 года «Теория вероятностных баз данных».[нужна цитата ] Название (8-страничного доклада) было задумано как шутка, поскольку 600-страничная монография Дэвида Майера «Теория реляционных баз данных» была бы известна в то время большинству участников конференции и читателям материалов конференции. .

Рекомендации

  1. ^ Винод Мутусами, Хайфэн Лю, Ханс-Арно Якобсен: Предиктивное сопоставление публикации / подписки. Университет Торонто.
  2. ^ Нилеш Н. Далви, Дэн Сучиу: Эффективная оценка запросов к вероятностным базам данных. VLDB J. 16 (4): 523-544 (2007).
  3. ^ Люблена Антова, Кристоф Кох, Дэн Олтяну: 10 ^ (10 ^ 6) Миры и за их пределами: эффективное представление и обработка неполной информации. ICDE 2007: 606-615

внешняя ссылка