Перегляд вихідного коду сторінки Аксіоми Армстронга

'''Аксіоми Армстронга'''&nbsp;— множина [[Аксіома|аксіом]] (або, точніше, [[Правило висновування|правил висновування]]), що використовуються для висновування всіх [[Функціональна залежність|функціональних залежностей]] у [[Реляційна база даних|реляційній базі даних]]. Їх розробив {{нп|Вільям Ворд Армстронг|Вільям В. Армстронг|en|William Ward Armstrong}} у своїй газетній статті 1974 року<ref>{{Cite paper|last=Armstrong|first=William Ward|url=https://ipfs.io/ipfs/QmWYWTGUZyTm2iRFTZY2pTr2x1vWkDiJr2CBp2PGVpSVSv|title=Dependency Structures of Data Base Relationships|page=580—583|publisher=IFIP Congress|year=1974|archiveurl=https://web.archive.org/web/20180126091352if_/https://ipfs.io/ipfs/QmWYWTGUZyTm2iRFTZY2pTr2x1vWkDiJr2CBp2PGVpSVSv|archivedate=26 січня 2018}}</ref>. Аксіоми [[Правильність|правильні]] в генеруванні тільки функціональних залежностей у [[Замикання (математика)|замиканні]] множини функціональних залежностей (позначеному <math>F^{+}</math>), коли застосовані до цієї множини (позначеній <math>F</math>). Також вони [[Повнота (логіка)|повні]] в тому, що повторне застосування цих правил генеруватиме всі функціональні залежності в замиканні <math>F^+</math>.

Формальніше, нехай <math>\langle R(U), F \rangle</math> позначає реляційну схему над множиною атрибутів <math>U</math> зі множиною функціональних залежностей <math>F</math>. Скажемо, що функціональна залежність <math>f</math> логічно слідує з <math>F</math>, і позначимо це <math>F \models f</math>, якщо й тільки якщо для кожного примірника <math>r</math> із <math>R</math>, що задовольняє функціональні залежності в <math>F</math>, <math>r</math> також задовольняє <math>f</math>. Позначимо <math>F^{+}</math> множину всіх функціональних залежностей, які логічно слідують із <math>F</math>.

Більше того, з повагою до множини правил висновування <math>A</math>, скажемо, що функціональна залежність <math>f</math> є похідною з функціональних залежностей у <math>F</math> за множиною правил висновування <math>A</math>, і позначимо це <math>F \vdash _{A} f</math>, якщо й тільки якщо <math>f</math> можна отримати шляхом повторного застосування правил висновування в <math>A</math> до функціональних залежностей у <math>F</math>. Позначимо <math>F^{*}_{A}</math> множину всіх функціональних залежностей, які є похідними від <math>F</math> за правилами висновування в <math>A</math>.

Тоді множина правил висновування <math>A</math> правильна, якщо й тільки якщо має місце наступне:

<math>
F^{*}_{A} \subseteq F^{+}
</math>

інакше кажучи, ми не можемо вивести за допомогою <math>A</math> функціональні залежності, які логічно не слідують з <math>F</math>.
Множину правил висновування <math>A</math> називають повною, якщо має місце наступне:

<math>
F^{+} \subseteq F^{*}_{A}
</math>

простіше кажучи, ми здатні вивести за <math>A</math> всі функціональні залежності, які логічно слідують із <math>F</math>.

== Аксіоми (первинні правила) ==
Нехай <math>R(U)</math>&nbsp;— схема відношення над множиною атрибутів <math>U</math>. Надалі позначатимемо літерами <math>X</math>, <math>Y</math>, <math>Z</math> будь-яку підмножину <math>U</math>, а, для стислості, об'єднання двох множин атрибутів <math>X</math> та <math>Y</math> як <math>XY</math> замість звичайного <math>X \cup Y</math>; ця нотація є достатньо стандартною в {{нп|Теорія баз даних|теорії баз даних|en|Database theory}} при роботі зі множинами атрибутів.

=== Аксіома рефлексивності ===
Якщо <math>X</math>&nbsp;— множина атрибутів, а <math>Y</math>&nbsp;— підмножина <math>X</math>, то <math>X</math> вміщує <math>Y</math>. Тоді <math>X</math> вміщує <math>Y</math> [<math>X \to Y</math>] означає, що <math>X</math> функціонально визначає <math>Y</math>.

: Якщо <math>Y \subseteq X</math>, то <math>X \to Y</math>.

=== Аксіома доповнення ===
Якщо <math>X</math> вміщує <math>Y</math>, а <math>Z</math>&nbsp;— множина атрибутів, то <math>X Z</math> вміщує <math>Y Z</math>. Це означає, що атрибут у залежностях не змінює основних залежностей.

: Якщо <math>X \to Y</math>, то <math>X Z \to Y Z</math> для будь-якого <math>Z</math>.

=== Аксіома транзитивності ===
Якщо <math>X</math> вміщує <math>Y</math>, а <math>Y</math> вміщує <math>Z</math>, то <math>X</math> вміщує <math>Z</math>.

: Якщо <math>X \to Y</math> та <math>Y \to Z</math>, то <math>X \to Z</math>.

== Додаткові (другорядні) правила ==
Ці правила можуть виводитися від вищенаведених аксіом.

=== Декомпозиція ===
Якщо <math>X \to Y Z</math>, то <math> X \to Y</math> та <math> X \to Z</math>.

==== Доведення ====
{|
| 1. <math>X \to Y Z</math>
| (Дано)
|-
| 2. <math>Y Z \to Y</math>
| (Рефлексивність)
|-
| 3. <math>X \to Y</math>
| (Транзитивність 1 і 2)
|}

=== Композиція ===
Якщо <math>X \to Y</math> та <math>A \to B</math>, то <math> X A \to Y B</math>.

==== Доведення ====
{|
| 1. <math>X \to Y</math>
| (Дано)
|-
| 2. <math>A \to B</math>
| (Дано)
|-
| 3. <math>X A \to Y A</math>
| (Доповнення 1 і A)
|-
| 4. <math>X A \to Y</math>
| (Декомпозиція 3)
|-
| 5. <math>X A \to X B</math>
| (Доповнення 2 і X)
|-
| 6. <math>X A \to B</math>
| (Декомпозиція 5)
|-
| 7. <math>X A \to Y B</math>
| (Об'єднання 4 і 6)
|}

=== Об'єднання (нотація) ===
Якщо <math>X \to Y</math> та <math>X \to Z</math>, то <math>X \to YZ</math>.

=== Псевдо-транзитивність ===
Якщо <math>X \to Y</math> та <math> Y Z \to W</math>, то <math> X Z\to W</math>.

==== Доведення ====
{|
| 1. <math>X \to Y</math>
| (Дано)
|-
| 2. <math>Y Z \to W</math>
| (Дано)
|-
| 3. <math>X Z \to Y Z</math>
| (Доповнення 1 і Z)
|-
| 4. <math>X Z \to W</math>
| (Транзитивність 3 і 2)
|}

=== Самовизначення ===
<math> I \to I</math> для будь-якої <math>I</math>. Це слідує прямо з аксіоми рефлексивності.

=== Екстенсивність ===
Наступна властивість є особливим випадком доповнення, коли <math>Z=X</math>.

: Якщо <math>X \to Y</math>, то <math>X \to X Y</math>.

Екстенсивність може замінити доповнення як аксіому в сенсі, що доповнення може бути доведене з екстенсивності разом з іншими аксіомами.

==== Доведення ====
{|
| 1. <math>X Z \to X</math>
| (Рефлексивність)
|-
| 2. <math>X \to Y</math>
| (Дано)
|-
| 3. <math>X Z \to Y</math>
| (Транзитивність 1 і 2)
|-
| 4. <math>X Z \to X Y Z</math>
| (Екстенсивність 3)
|-
| 5. <math>X Y Z \to Y Z</math>
| (Рефлексивність)
|-
| 6. <math>X Z \to Y Z</math>
| (Транзитивність 4 і 5)
|}

== Відношення Армстронга ==
Дано множину функціональних залежностей <math>F</math>, '''відношення Армстронга'''&nbsp;— відношення, яке задовольняє всім функціональним залежностям у замиканні <math>F^+</math> й тільки цим залежностям. На жаль, мінімальний розмір відношення Армстронга для даної множини залежностей може бути експоненційною функцією від кількості атрибутів у залежностях, які розглядаються<ref>{{Cite journal|last1=Beeri|first1=C.|last2=Dowd|first2=M.|last3=Fagin|first3=R.|last4=Statman|first4=R.|year=1984|title=On the Structure of Armstrong Relations for Functional Dependencies|url=http://www.almaden.ibm.com/cs/people/fagin/jacm84.pdf|journal=Journal of the ACM|volume=31|pages=30–46|citeseerx=10.1.1.68.9320|doi=10.1145/2422.322414|pmc=|pmid=|accessdate=11 серпня 2020|archive-date=12 березня 2006|archive-url=https://web.archive.org/web/20060312041821/http://www.almaden.ibm.com/cs/people/fagin/jacm84.pdf}}</ref>.

== Примітки ==
{{примітки}}

== Посилання ==
* {{Cite web|url=http://www.cs.umbc.edu/courses/461/current/burt/lectures/lec14/|назва=UMBC CMSC 461 Spring '99|accessdate=11 серпня 2020|archive-date=27 вересня 2011|archive-url=https://web.archive.org/web/20110927014000/http://www.cs.umbc.edu/courses/461/current/burt/lectures/lec14/}}
* {{Cite web|url=http://www-db.stanford.edu/~ullman/cs345notes/slides01-1.ps|назва=CS345 Lecture Notes from Stanford University|accessdate=11 серпня 2020|archive-date=20 вересня 2006|archive-url=https://web.archive.org/web/20060920142140/http://www-db.stanford.edu/~ullman/cs345notes/slides01-1.ps}}

{{СКБД}}
{{Нормалізація баз даних}}

[[Категорія:Моделювання даних]]