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

Аксіоми Армстронга — множина аксіом (або, точніше, правил висновування), що використовуються для висновування всіх функціональних залежностей у реляційній базі даних. Їх розробив Вільям В. Армстронг у своїй газетній статті 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 і A)
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$.

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

Якщо $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 Spring '99. Архів оригіналу за 27 вересня 2011. Процитовано 11 серпня 2020.
• CS345 Lecture Notes from Stanford University. Архів оригіналу за 20 вересня 2006. Процитовано 11 серпня 2020.