Аксиомы Армстронга - Armstrongs axioms - Wikipedia

Аксиомы Армстронга набор ссылок (точнее, правила вывода ) используется для вывода всех функциональные зависимости на реляционная база данных. Они были разработаны Уильям У. Армстронг в его статье 1974 года.[1] Аксиомы звук в генерации только функциональных зависимостей в закрытие набора функциональных зависимостей (обозначаемых как ) применительно к этому набору (обозначается как ). Они также полный в этом повторном применении этих правил будут генерироваться все функциональные зависимости в замыкании .

Более формально, пусть обозначают реляционную схему над набором атрибутов с набором функциональных зависимостей . Мы говорим, что функциональная зависимость логически подразумевается , и обозначим его тогда и только тогда, когда для каждого экземпляра из который удовлетворяет функциональным зависимостям в , также удовлетворяет . Обозначим через набор всех функциональных зависимостей, которые логически подразумеваются .

Кроме того, в отношении набора правил вывода , мы говорим, что функциональная зависимость выводится из функциональных зависимостей в по набору правил вывода , и обозначим его через если и только если можно получить путем повторного применения правил вывода в функциональным зависимостям в . Обозначим через набор всех функциональных зависимостей, которые выводятся из по правилам вывода в .

Затем набор правил вывода является правильным тогда и только тогда, когда выполняется следующее:

то есть мы не можем получить с помощью функциональные зависимости, которые логически не подразумеваются .Набор правил вывода называется завершенным, если выполняется следующее:

проще говоря, мы можем получить все функциональные зависимости, которые логически подразумеваются .

Аксиомы (первичные правила)

Позволять быть схемой отношений над набором атрибутов . В дальнейшем будем обозначать буквами , , любое подмножество и, для краткости, объединение двух наборов атрибутов и к вместо обычного ; это обозначение довольно стандартно в теория баз данных при работе с наборами атрибутов.

Аксиома рефлексивности

Если это набор атрибутов и это подмножество , тогда держит . Настоящим держит [] Значит это функционально определяет .

Если тогда .

Аксиома увеличения

Если держит и это набор атрибутов, то держит . Это означает, что атрибут в зависимостях не изменяет базовые зависимости.

Если , тогда для любого .

Аксиома транзитивности

Если держит и держит , тогда держит .

Если и , тогда .

Дополнительные правила (Secondary Rules)

Эти правила могут быть выведены из приведенных выше аксиом.

Разложение

Если тогда и .

Доказательство

1. (Данный)
2. (Рефлексивность)
3. (Транзитивность 1 и 2)

Сочинение

Если и тогда .

Доказательство

1. (Данный)
2. (Данный)
3. (Увеличение 1 и A)
4. (Разложение 3)
5. (Дополнение 2 и X)
6. (Разложение 5)
7. (Союз 4 и 6)

Союз (Обозначение)

Если и тогда .

Псевдотранзитивность

Если и тогда .

Доказательство

1. (Данный)
2. (Данный)
3. (Увеличение 1 и Z)
4. (Транзитивность 3 и 2)

Самоопределение

для любого . Это прямо следует из аксиомы рефлексивности.

Экстенсивность

Следующее свойство является частным случаем увеличения, когда .

Если , тогда .

Экстенсивность может заменить увеличение как аксиому в том смысле, что увеличение может быть доказано из экстенсивности вместе с другими аксиомами.

Доказательство

1. (Рефлексивность)
2. (Данный)
3. (Транзитивность 1 и 2)
4. (Экстенсивность 3)
5. (Рефлексивность)
6. (Транзитивность 4 и 5)

Отношение Армстронга

Учитывая набор функциональных зависимостей , Отношение Армстронга это отношение, удовлетворяющее всем функциональным зависимостям в замыкании и только эти зависимости. К сожалению, отношение Армстронга минимального размера для данного набора зависимостей может иметь размер, который является экспоненциальной функцией количества атрибутов в рассматриваемых зависимостях.[2]

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

  1. ^ Уильям Уорд Армстронг: Структуры зависимостей отношений в базе данных, стр. 580-583. Конгресс ИФИП, 1974 г.
  2. ^ Beeri, C .; Дауд, М .; Fagin, R .; Статман, Р. (1984). «О структуре отношений Армстронга для функциональных зависимостей» (PDF). Журнал ACM. 31: 30–46. CiteSeerX  10.1.1.68.9320. Дои:10.1145/2422.322414.

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