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

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

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

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

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

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

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

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

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

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

Если — набор атрибутов и — подмножество , то выполняется . При этом выполняется [ ] означает, что функционально определяет .${\displaystyle X}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle X\to Y}$${\displaystyle X}$${\displaystyle Y}$

Если тогда .${\displaystyle Y\subseteq X}$${\displaystyle X\to Y}$

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

Если , то для любого .${\displaystyle X\to Y}$${\displaystyle XZ\to YZ}$${\displaystyle Z}$

Если держится и держится , то держится . ${\displaystyle X}$${\displaystyle Y}$${\displaystyle Y}$${\displaystyle Z}$${\displaystyle X}$${\displaystyle Z}$

Если и , то .${\displaystyle X\to Y}$${\displaystyle Y\to Z}$${\displaystyle X\to Z}$

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

Если то и .${\displaystyle X\to YZ}$${\displaystyle X\to Y}$${\displaystyle X\to Z}$

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

Если и тогда .${\displaystyle X\to Y}$${\displaystyle A\to B}$${\displaystyle XA\to YB}$

1.${\displaystyle X\to Y}$	(Данный)
2.${\displaystyle A\to B}$	(Данный)
3.${\displaystyle XA\to YA}$	(Увеличение 1 и А)
4.${\displaystyle YA\to YB}$	(Увеличение 2 и Y)
5.${\displaystyle XA\to YB}$	(Транзитивность 3 и 4)

Если и тогда .${\displaystyle X\to Y}$${\displaystyle X\to Z}$${\displaystyle X\to YZ}$

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

Если и тогда .${\displaystyle X\to Y}$${\displaystyle YZ\to W}$${\displaystyle XZ\to W}$

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

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

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

Если , то .${\displaystyle X\to Y}$${\displaystyle X\to XY}$

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

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

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

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