Аксиомы Армстронга

Аксиомы Армстронга — это набор ссылок (или, точнее, правил вывода ), используемых для вывода всех функциональных зависимостей от реляционной базы данных . Они были разработаны Уильямом Армстронгом в его статье 1974 года. Аксиомы верны при генерации только функциональных зависимостей при замыкании множества функциональных зависимостей (обозначаемых как $F^{+}$) при применении к этому набору (обозначается как $F$). Они также полны в том смысле, что повторное применение этих правил создаст все функциональные зависимости в замыкании. $F^{+}$.

Более формально, пусть $\langle R(U),F\rangle$ обозначают реляционную схему над набором атрибутов $U$ с набором функциональных зависимостей $F$. Мы говорим, что функциональная зависимость $f$ логически подразумевается $F$, и обозначим его через $F\models f$ тогда и только тогда, когда для каждого экземпляра $r$ из $R$ который удовлетворяет функциональным зависимостям в $F$, $r$ также удовлетворяет $f$. Обозначим через $F^{+}$ совокупность всех функциональных зависимостей, которые логически подразумеваются $F$.

Кроме того, по отношению к набору правил вывода $A$, мы говорим, что функциональная зависимость $f$ выводится из функциональных зависимостей в $F$ по набору правил вывода $A$, и мы обозначаем его через $F\vdash _{A}f$ тогда и только тогда, когда $f$ можно получить путем многократного применения правил вывода в $A$ к функциональным зависимостям в $F$. Обозначим через $F_{A}^{*}$ совокупность всех функциональных зависимостей, которые вытекают из $F$ по правилам вывода в $A$.

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

$F_{A}^{*}\subseteq F^{+}$

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

$F^{+}\subseteq F_{A}^{*}$

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

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

Позволять $R(U)$ быть схемой отношений по набору атрибутов $U$. В дальнейшем будем обозначать буквами $X$, $Y$, $Z$ любое подмножество $U$ и, короче говоря, объединение двух наборов атрибутов $X$ и $Y$ к $XY$ вместо обычного $X\cup Y$; это обозначение довольно стандартно в теории баз данных при работе с наборами атрибутов.

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

Если $X$ представляет собой набор атрибутов и $Y$ является подмножеством $X$, затем $X$ держит $Y$. Настоящим, $X$ держит $Y$ [ $X\to Y$] означает, что $X$ функционально определяет $Y$.

Если $Y\subseteq X$ затем $X\to Y$.

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

Если $X$ держит $Y$ и $Z$ представляет собой набор атрибутов, то $XZ$ держит $YZ$. Это означает, что атрибут в зависимостях не меняет базовые зависимости.

Если $X\to Y$, затем $XZ\to YZ$ для любого $Z$.

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

Если $X$ держит $Y$ и $Y$ держит $Z$, затем $X$ держит $Z$.

Если $X\to Y$ и $Y\to Z$, затем $X\to Z$.

Дополнительные правила (Вторичные правила)

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

Разложение

Если $X\to YZ$ затем $X\to Y$ и $X\to Z$.

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

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

Состав

Если $X\to Y$ и $A\to B$ затем $XA\to YB$.

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

1. $X\to Y$	(Данный)
2. $A\to B$	(Данный)
3. $XA\to YA$	(Увеличение 1 и А)
4. $XA\to Y$	(Разложение 3)
5. $XA\to XB$	(Увеличение 2 и X)
6. $XA\to B$	(Разложение 5)
7. $XA\to YB$	(Союз 4 и 6)

Союз

Если $X\to Y$ и $X\to Z$ затем $X\to YZ$.

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

1. $X\to Y$	(Данный)
2. $X\to Z$	(Данный)
3. $X\to XZ$	(Увеличение 2 и X)
4. $XZ\to YZ$	(Увеличение 1 и Z)
5. $X\to YZ$	(Транзитивность 3 и 4)

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

Если $X\to Y$ и $YZ\to W$ затем $XZ\to W$.

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

1. $X\to Y$	(Данный)
2. $YZ\to W$	(Данный)
3. $XZ\to YZ$	(Увеличение 1 и Z)
4. $XZ\to W$	(Транзитивность 3 и 2)

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

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

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

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

Если $X\to Y$, затем $X\to XY$.

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

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

1. $XZ\to X$	(Рефлексивность)
2. $X\to Y$	(Данный)
3. $XZ\to Y$	(Транзитивность 1 и 2)
4. $XZ\to XYZ$	(Расширенность 3)
5. $XYZ\to YZ$	(Рефлексивность)
6. $XZ\to YZ$	(Транзитивность 4 и 5)

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

Учитывая набор функциональных зависимостей $F$ — отношение Армстронга это отношение, которое удовлетворяет всем функциональным зависимостям замыкания $F^{+}$ и только эти зависимости. К сожалению, отношение Армстронга минимального размера для данного набора зависимостей может иметь размер, который является экспоненциальной функцией количества атрибутов в рассматриваемых зависимостях.

Внешние ссылки

• UMBC CMSC 461, весна '99
• Конспекты лекций CS345 от Стэнфордского университета