Вероятностная база данных
Большинство реальных баз данных содержат данные, корректность которых сомнительна. Для работы с такими данными необходимо количественно оценить целостность данных. Это достигается за счет использования вероятностных баз данных.
Вероятностная база данных — это неопределенная база данных , в которой возможные миры имеют связанные вероятности . Вероятностные системы управления базами данных в настоящее время являются активной областью исследований. «Хотя в настоящее время коммерческих систем вероятностных баз данных не существует, существует несколько исследовательских прототипов…» [1]
Вероятностные базы данных различают логическую модель данных и физическое представление данных так же, как это делают реляционные базы данных в архитектуре ANSI-SPARC . по размеру одного мира (классическая база данных ) В вероятностных базах данных это еще более важно, поскольку такие базы данных должны кратко представлять очень большое количество возможных миров, часто экспоненциальное . [2] [3]
Терминология [ править ]
В вероятностной базе данных каждый кортеж связан с вероятностью от 0 до 1, где 0 означает, что данные заведомо неверны, а 1 означает, что они заведомо верны.
Возможные миры [ править ]
Вероятностная база данных может существовать в нескольких состояниях. Например, если существует неопределенность относительно существования кортежа в базе данных, то база данных может находиться в двух разных состояниях по отношению к этому кортежу: первое состояние содержит кортеж, а второе — нет. Аналогично, если атрибут может принимать одно из значений x , y или z , то база данных может находиться в трех разных состояниях относительно этого атрибута.
Каждое из этих состояний называется возможным миром.
Рассмотрим следующую базу данных:
| А | Б |
|---|---|
| а1 | б1 |
| а2 | б2 |
| а3 | {b3, b3', b3''} |
(Здесь {b3, b3', b3''} означает, что атрибут может принимать любое из значений b3 , b3' или b3'' )
- Предположим, что существует неопределенность в отношении первого кортежа, определенность в отношении второго кортежа и неопределенность в отношении значения атрибута B в третьем кортеже.
Тогда фактическое состояние базы данных может содержать или не содержать первый кортеж (в зависимости от того, правильный он или нет). Аналогично, значение атрибута B может быть b3 , b3' или b3'' .
Следовательно, возможные миры, соответствующие базе данных, следующие:
| А | Б |
|---|---|
| а1 | б1 |
| а2 | б2 |
| а3 | б3 |
| А | Б |
|---|---|
| а1 | б1 |
| а2 | б2 |
| а3 | б3' |
| А | Б |
|---|---|
| а1 | б1 |
| а2 | б2 |
| а3 | б3'' |
| А | Б |
|---|---|
| а2 | б2 |
| а3 | б3 |
| А | Б |
|---|---|
| а2 | б2 |
| а3 | б3' |
| А | Б |
|---|---|
| а2 | б2 |
| а3 | б3'' |
Типы неопределенностей [ править ]
По сути, в вероятностной базе данных могут существовать два типа неопределенностей, как описано в таблице ниже:
| Неопределённость на уровне кортежа | Неопределённость на уровне атрибутов |
|---|---|
| Неопределенность в том, корректен ли кортеж или нет, то есть должен ли он существовать в базе данных или нет. | Неопределенность относительно значений, которые может принимать атрибут кортежа, то есть он может принимать одно из нескольких возможных значений. |
| Каждому неопределенному кортежу соответствуют два возможных мира: один включает кортеж, а другой — нет. | Каждому неопределенному атрибуту, который может принимать одно из значений a 1 ,...,an , соответствует n возможных миров. |
| Неопределенность на уровне кортежа можно рассматривать как логическую случайную величину, связанную с каждым неопределенным кортежем. | Неопределенность на уровне атрибута можно рассматривать как случайную величину, связанную с каждым неопределенным атрибутом, который может принимать значения a 1 ,..., an . |
Присваивая значения случайным переменным, связанным с элементами данных, можно представить различные возможные миры.
История [ править ]
Первое опубликованное использование термина «вероятностная база данных», вероятно, было в документе конференции VLDB 1987 года «Теория вероятностных баз данных» Кавалло и Питтарелли. [4] Название (11-страничной статьи) было задумано как шутка, поскольку 600-страничная монография Дэвида Майера «Теория реляционных баз данных» была в то время знакома многим участникам конференции и читателям материалов конференции. .
Ссылки [ править ]
- ^ Винод Мутусами, Хайфэн Лю, Ханс-Арно Якобсен: Прогнозируемое сопоставление публикации/подписки. Университет Торонто.
- ^ Нилеш Н. Далви , Дэн Сучу : Эффективная оценка запросов в вероятностных базах данных. Журнал VLDB 16 (4): 523–544 (2007).
- ^ Люблена Антова , Кристоф Кох , Дэн Олтяну : 10^(10^6) Миры и за их пределами: эффективное представление и обработка неполной информации. ICDE 2007: 606–615.
- ^ Роджер Кавалло, Майкл Питтарелли: Теория вероятностных баз данных. В VLDB'87, Материалы 13-й Международной конференции по очень большим базам данных, 1–4 сентября 1987 г., Брайтон: 71–81 (1987).
Внешние ссылки [ править ]
- Проект MayBMS в Корнельском университете ( сайт проекта sourceforge.net )
- Проект MystiQ в Вашингтонском университете
- Проект Орион в Университете Пердью
- Проект Трио в Стэнфордском университете
- Проект BayesStore в Калифорнийском университете в Беркли.
- Проект PrDB в Университете Мэриленда, Колледж-Парк
- Проект Мимир в Университете Буффало
| Типы | |
|---|---|
| Концепции | |
| Объекты | |
| Компоненты | |
| Функции | |
| Связанные темы | |
