АссистентНовый вопросИсторияОбласти знаний
Партнёрские проектыСпецпроектыСтать автором
Сменить язык
О РУВИКИ
ТехнологииДанные, аналитика и ИИХранение и обработка данныхВероятностная база данных

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

Экспертиза РАН

Logo-ran-black.png
Проведена экспертиза
Российской академией наук
Подробнее
Aprove.svg

Экспертиза РАН

Arrow-Right.png
Logo-ran.png
Проведена экспертиза
Российской академией наук
Подробнее

Вероятностная база данных — это разновидность неопределённой базы данных, в которой множествам возможных миров сопоставлены определённые вероятности. Системы управления вероятностными базами данных в настоящее время являются активно развивающейся областью научных исследований. Хотя коммерческих СУБД с поддержкой вероятностных баз данных пока что не существует, имеется ряд экспериментальных прототипов, предложенных в научной среде[1].

Описание

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

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

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

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

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

Пример неполной базы данных
A B
a1 b1
a2 b2
a3 {b3, b3′, b3′′}

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

Пусть относительно первой кортежи есть неопределённость, относительно второй — уверенность, а для третьей кортежи сомнения относительно значения атрибута B.

В результате, реальное состояние базы может либо включать первую кортеж, либо нет (в зависимости от её правильности). Аналогично, атрибут B третьей кортежи может быть равен b3, b3′ или b3′′. Следовательно, возможные миры для этой неполной базы данных следующие:

Мир 1
A B
a1 b1
a2 b2
a3 b3
Мир 2
A B
a1 b1
a2 b2
a3 b3'
Мир 3
A B
a1 b1
a2 b2
a3 b3
Мир 4
A B
a2 b2
a3 b3
Мир 5
A B
a2 b2
a3 b3'
Мир 6
A B
a2 b2
a3 b3

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

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

Типы неопределённости
Неопределённость на уровне кортежа Неопределённость на уровне атрибута
Неопределённость относительно корректности кортежа — должен ли он присутствовать в базе данных. Неопределённость относительно значений, которые может принимать атрибут кортежа, то есть возможность принять одно из нескольких значений из области определения.
Для каждого неопределённого кортежа существует два возможных мира: один с этим кортежем и другой без него. Для каждого неопределённого атрибута, который может принимать значения a1,...,an, существует n возможных миров.
Неопределённость на уровне кортежа можно интерпретировать как булеву случайную переменную, связанную с каждым неопределённым кортежем. Неопределённость на уровне атрибута можно рассматривать как случайную переменную, связанную с каждым атрибутом, который может принимать значения a1,...,an.

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

История

Первое употребление термина «вероятностная база данных» в публикации, вероятно, относится к докладу на конференции VLDB 1987 года «The theory of probabilistic databases», авторами которого были Кавалло и Питтарелли[4]. Название этой статьи (11 страниц) было выбрано по аналогии с «The Theory of Relational Databases» Дэвида Майера, широко известной 600-страничной монографией, знакомой многим участникам конференции и читателям её материалов.

Примечания

  1. ↑ Vinod Muthusamy, Haifeng Liu, Hans-Arno Jacobsen. Predictive Publish/Subscribe Matching (англ.). University of Toronto. Дата обращения: 29 июня 2024. Архивировано 24 февраля 2024 года.
  2. ↑ Nilesh N. Dalvi, Dan Suciu. “Efficient query evaluation on probabilistic databases”. VLDB Journal [англ.]. 16 (4): 523—544. 2007.
  3. ↑ Lyublena Antova, Christoph Koch, Dan Olteanu. “10^(10^6) Worlds and Beyond: Efficient Representation and Processing of Incomplete Information”. ICDE 2007 [англ.]: 606—615. 2007.
  4. ↑ Roger Cavallo, Michael Pittarelli. “The Theory of Probabilistic Databases”. VLDB'87, Proceedings of 13th International Conference on Very Large Data Bases, September 1–4, 1987, Brighton [англ.]: 71—81. 1987.

Ссылки

Категории