Аксиомы Армстронга - это набор ссылок (или, точнее, правил вывода ), используемых для вывода всех функциональных зависимостей в реляционной базе данных . Они были разработаны Уильямом У. Армстронгом в его статье 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. | (Увеличение 2 и X) |
4. | (Увеличение 1 и Z) |
5. | (Транзитивность 3 и 4) |
Псевдотранзитивность
Если а также тогда .
Доказательство
1. | (Дано) |
2. | (Дано) |
3. | (Увеличение 1 и Z) |
4. | (Транзитивность 3 и 2) |
Самоопределение
для любой . Это прямо следует из аксиомы рефлексивности.
Экстенсивность
Следующее свойство является частным случаем увеличения, когда .
- Если , тогда .
Экстенсивность может заменить увеличение как аксиому в том смысле, что увеличение может быть доказано на основе экстенсивности вместе с другими аксиомами.
Доказательство
1. | (Рефлексивность) |
2. | (Дано) |
3. | (Транзитивность 1 и 2) |
4. | (Экстенсивность 3) |
5. | (Рефлексивность) |
6. | (Транзитивность 4 и 5) |
Отношение Армстронга
Учитывая набор функциональных зависимостей , отношение Армстронга - это отношение, которое удовлетворяет всем функциональным зависимостям в замыканиии только эти зависимости. К сожалению, отношение Армстронга минимального размера для данного набора зависимостей может иметь размер, который является экспоненциальной функцией количества атрибутов в рассматриваемых зависимостях. [2]
Рекомендации
- ^ Уильям Уорд Армстронг: структуры зависимостей отношений базы данных , стр. 580-583. Конгресс ИФИП, 1974 г.
- ^ Beeri, C .; Дауд, М .; Fagin, R .; Статман, Р. (1984). «О структуре отношений Армстронга для функциональных зависимостей» (PDF) . Журнал ACM . 31 : 30–46. CiteSeerX 10.1.1.68.9320 . DOI : 10.1145 / 2422.322414 .