Функціональна залежність

Нехай маємо відношення ${\displaystyle r}$ зі схемою (заголовком) ${\displaystyle R}$, ${\displaystyle A}$ і ${\displaystyle B}$ — деякі підмножини множини атрибутів відношення ${\displaystyle r}$. Множина ${\displaystyle B}$ функціонально залежить від ${\displaystyle A}$ тоді і тільки тоді, коли кожне значення множини ${\displaystyle A}$ зв'язане точно з одним значенням множини ${\displaystyle B}$. Іншими словами, якщо два кортежі збігаються за атрибутами ${\displaystyle A}$, то вони збігаються і за атрибутами ${\displaystyle B}$.

${\displaystyle r\left(R\right),\ A\subseteq R,\ B\subseteq R}$

${\displaystyle \left(A\to B\right)\Leftrightarrow \left(\left(\forall {{t}_{1}},{{t}_{2}}\in r:{{t}_{1}}\left(A\right)={{t}_{2}}\left(A\right)\right)\Rightarrow \left({{t}_{1}}\left(B\right)={{t}_{2}}\left(B\right)\right)\right)}$

У такому разі ${\displaystyle A}$ — детермінант, ${\displaystyle B}$ — залежна частина.

ФЗ називається тривіальною, якщо залежна частина є підмножиною детермінанта.

${\displaystyle \left(B\subseteq A\right)\Rightarrow \left(A\to B\right)}$

Одні функціональні залежності можуть припускати інші функціональні залежності. Наприклад,

${\displaystyle \left(A\to B\right)\wedge \left(B\to C\right)\Rightarrow \left(A\to C\right)}$.

Множина ${\displaystyle {{S}^{+}}}$ всіх ФЗ, які припускаються даною множиною ФЗ ${\displaystyle S}$ називається замкненням множини ${\displaystyle S}$.

Нехай ${\displaystyle Z}$ — деяка множина атрибутів відношення ${\displaystyle r}$, а ${\displaystyle S}$ — множина функціональних залежностей цього відношення. Замкненням ${\displaystyle {{Z}^{+}}}$ множини атрибутів ${\displaystyle Z}$ в межах ${\displaystyle S}$ називається така множина атрибутів ${\displaystyle {{A}_{i}}}$ відношення ${\displaystyle r}$, що функціональна залежність ${\displaystyle Z\to {{A}_{i}}}$ є членом замкнення ${\displaystyle {{S}^{+}}}$.

${\displaystyle r\left(R\right),\ S,\ Z\subseteq R,\ {{A}_{i}}\subseteq R,\ i={\overline {1,n}}}$

${\displaystyle {{Z}^{+}}=\left\{{{A}_{i}}:\left(Z\to {{A}_{i}}\right)\in {{S}^{+}}\right\}}$

Нехай ${\displaystyle {{S}_{1}}}$ і ${\displaystyle {{S}_{2}}}$ — деякі множини функціональних залежностей.

• Якщо будь-яка функціональна залежність з ${\displaystyle {{S}_{1}}}$ входить і в ${\displaystyle {{S}_{2}}}$, тоді ${\displaystyle {{S}_{2}}}$ називають покриттям множини функціональних залежностей ${\displaystyle {{S}_{1}}}$.

• Якщо ${\displaystyle {{S}_{2}}}$ — покриття для ${\displaystyle {{S}_{1}}}$, а ${\displaystyle {{S}_{1}}}$ — для ${\displaystyle {{S}_{2}}}$ (тобто ${\displaystyle S_{1}^{+}=S_{2}^{+}}$), тоді такі множини називаються еквівалентними.

• Множина ФЗ ${\displaystyle S}$ називається незвідною тоді і тільки тоді, коли виконуються наступні вимоги:
  • В кожній ФЗ залежна частина містить лише один елемент;
  • Детермінант кожної ФЗ є незвідним (ні один атрибут не може буди видаленим з детермінанта без зміни замкнення ${\displaystyle {{S}^{+}}}$);
  • Жодну ФЗ з ${\displaystyle S}$ не можна виключити без зміни замкнення ${\displaystyle {{S}^{+}}}$.

• Для будь-якої множини ФЗ існує не менше ніж одна еквівалентна множина, яка є незвідною. Така множина називається незвідним покриттям.

В 1974 Вільям Армстронг запропонував набір правил виводу нових ФЗ на основі даних.

Нехай у нас є відношення ${\displaystyle r\left(R\right)}$ і множини атрибутів ${\displaystyle A,B,C,D\subseteq R}$. Для скорочення запису замість ${\displaystyle X\cup Y}$ будемо писати просто ${\displaystyle XY}$.

• Рефлексивність:

  ${\displaystyle \left(B\subseteq A\right)\Rightarrow \left(A\to B\right)}$

• Поповнення:

  ${\displaystyle \left(A\to B\right)\Rightarrow \left(AC\to BC\right)}$

• Транзитивність:

  ${\displaystyle \left(A\to B\right)\wedge \left(B\to C\right)\Rightarrow \left(A\to C\right)}$

Правила виводу Армстронга повні (з їхньою допомогою можна вивести решту ФЗ, що маються на увазі даною множиною) і надійні («зайвих» ФЗ вивести не можна; виведена ФЗ справедлива всюди, де справедлива та множина ФЗ, з якої вона була виведена).

Крім того, з даних правил досить просто виводяться, декілька додаткових правил, які спрощують задачу виведення ФЗ.

• Самовизначення:

  ${\displaystyle A\to A}$

• Декомпозиція:

  ${\displaystyle \left(A\to BC\right)\Rightarrow \left(A\to B\right)\wedge \left(A\to C\right)}$

• Об'єднання:

  ${\displaystyle \left(A\to B\right)\wedge \left(A\to C\right)\Rightarrow \left(A\to BC\right)}$

• Композиція:

  ${\displaystyle \left(A\to B\right)\wedge \left(C\to D\right)\Rightarrow \left(AC\to BD\right)}$

• Теорема загального об'єднання Дарвена:

  ${\displaystyle \left(A\to B\right)\wedge \left(C\to D\right)\Rightarrow \left(A\cup \left(C-B\right)\to BD\right)}$

Теорема: ФЗ ${\displaystyle A\to B}$ вивідна з даної множини ФЗ ${\displaystyle S}$ за правилами виводу Армстронга тоді і тільки тоді, коли ${\displaystyle B\subseteq {{A}^{+}}}$.

Якщо застосовувати правила з попереднього розділу до того часу коли утворення нових ФЗ не припиниться, то ми отримаємо замкнення для даної множини ФЗ. На практиці рідко вимагається знаходити це замкнення само по собі, частіше за все нам набагато цікавіше дізнатися, чи входить та або інша ФЗ в замкнення. Для цього нам достатньо вирахувати замкнення детермінанта. Для цього існує доволі простий алгоритм.

1. Нехай ${\displaystyle X}$ — множина атрибутів, яка врешті-решт стане замкненням.
2. Здійснюємо пошук ФЗ виду ${\displaystyle {{B}_{1}}{{B}_{2}}\ldots {{B}_{m}}\to C}$, де ${\displaystyle {{B}_{1}}{{B}_{2}}\ldots {{B}_{m}}\subseteq X}$, а ${\displaystyle C\not \subset X}$. Залежну частину кожної ФЗ додаємо в ${\displaystyle X}$.
3. Повторюємо пункт 2, доки до множини ${\displaystyle X}$ буде неможливо додати атрибути.
4. Множина ${\displaystyle X}$, до якої неможливо додати атрибути і буде замкненням.

ФЗ є обмеженнями цілісності і визначають семантику даних, що зберігаються. При кожному оновленні СКБД повинна перевіряти їхнє дотримання. Значить, наявність великої кількості ФЗ небажане, інакше це призводить до уповільнення роботи. Для спрощення задачі необхідно скоротити набір ФЗ до мінімально необхідного.

Якщо ${\displaystyle I}$ є незвідним покриттям початкової множини ФЗ ${\displaystyle S}$, то перевірка виконання ФЗ з ${\displaystyle I}$ автоматично гарантує виконання всіх ФЗ з ${\displaystyle S}$. Таким чином, задача пошуку мінімально необхідного набору зводиться до пошуку незвідного покриття множини ФЗ, яке і буде використовуватись замість початкової множини.

Нехай дане відношення ${\displaystyle r\left(A,B,C\right)}$.

Якщо ${\displaystyle r}$ задовольняє функціональній залежності ${\displaystyle A\to B}$, тоді воно дорівнює поєднанню його проекцій ${\displaystyle r\left[A,B\right]}$ і ${\displaystyle r\left[A,C\right]}$.

${\displaystyle \left(A\to B\right)\Rightarrow \left(r\left(A,B,C\right)=r\left[A,B\right]\ {\text{JOIN}}\ r\left[A,C\right]\right)}$