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

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

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

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

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

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

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

${\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}$.

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

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

Разложение

Если ${\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 и A)
4. ${\displaystyle XA\to Y}$	(Разложение 3)
5. ${\displaystyle XA\to XB}$	(Дополнение 2 и X)
6. ${\displaystyle XA\to B}$	(Разложение 5)
7. ${\displaystyle XA\to YB}$	(Союз 4 и 6)

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

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

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

Если ${\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)

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

Учитывая набор функциональных зависимостей ${\displaystyle F}$, Отношение Армстронга это отношение, удовлетворяющее всем функциональным зависимостям в замыкании ${\displaystyle F^{+}}$ и только эти зависимости. К сожалению, отношение Армстронга минимального размера для данного набора зависимостей может иметь размер, который является экспоненциальной функцией количества атрибутов в рассматриваемых зависимостях.^[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.

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

• UMBC CMSC 461 Весна '99
• CS345 Лекционные заметки Стэнфордского университета