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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Функціональна залежність (далі часто ФЗ) — концепція, що лежить в основі багатьох питань, пов'язаних з реляційними базами даних, включаючи, зокрема, їхнє проектування. Математично являє собою бінарне відношення між множинами атрибутів даного відношення і є, по суті, зв'язком типу «один-до-багатьох». ФЗ забезпечує основу для наукового підходу до розв'язання деяких проблем, оскільки володіє багатим набором цікавих формальних властивостей.

Визначення[ред.ред. код]

Функціональна залежність[ред.ред. код]

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

r\left( R \right),\ A\subseteq R,\ B\subseteq R
\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)

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

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

\left( B\subseteq A \right)\Rightarrow \left( A\to B \right)

Замикання множини залежностей[ред.ред. код]

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

\left( A\to B \right)\wedge \left( B\to C \right)\Rightarrow \left( A\to C \right).

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

Замикання множини атрибутів[ред.ред. код]

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

r\left( R \right),\ S,\ Z\subseteq R,\ {{A}_{i}}\subseteq R,\ i=\overline{1,n}
{{Z}^{+}}=\left\{ {{A}_{i}}:\left( Z\to {{A}_{i}} \right)\in {{S}^{+}} \right\}

Незвідні множини залежностей[ред.ред. код]

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

  • Якщо будь-яка функціональна залежність з {{S}_{1}} входить і в {{S}_{2}}, тоді {{S}_{2}} називають покриттям множини функціональних залежностей {{S}_{1}}.
  • Якщо {{S}_{2}} — покриття для {{S}_{1}}, а {{S}_{1}} — для {{S}_{2}} (тобто S_{1}^{+}=S_{2}^{+}), тоді такі множини називаються еквівалентними.
  • Множина ФЗ S називається незвідною тоді і тільки тоді, коли виконуються наступні вимоги:
    • В кожній ФЗ залежна частина містить лише один елемент;
    • Детермінант кожної ФЗ є незвідним (ні один атрибут не може буди видаленим з детермінанта без зміни замкнення {{S}^{+}});
    • Жодну ФЗ з S неможна виключити без зміни замкнення {{S}^{+}}.
  • Для будь-якої множини ФЗ існує не менше ніж одна еквівалентна множина, яка є незвідною. Така множина називається незвідним покриттям.

Обчислення замкнень[ред.ред. код]

Правило виводу Армстронга[ред.ред. код]

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

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

  • Рефлексивність:
    \left( B\subseteq A \right)\Rightarrow \left( A\to B \right)
  • Поповнення:
    \left( A\to B \right)\Rightarrow \left( AC\to BC \right)
  • Транзитивність:
    \left( A\to B \right)\wedge \left( B\to C \right)\Rightarrow \left( A\to C \right)

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

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

  • Самовизначення:
    A\to A
  • Декомпозиція:
    \left( A\to BC \right)\Rightarrow \left( A\to B \right)\wedge \left( A\to C \right)
  • Об'єднання:
    \left( A\to B \right)\wedge \left( A\to C \right)\Rightarrow \left( A\to BC \right)
  • Композиція:
    \left( A\to B \right)\wedge \left( C\to D \right)\Rightarrow \left( AC\to BD \right)
  • Теорема загального об'єднання Дарвена:
    \left( A\to B \right)\wedge \left( C\to D \right)\Rightarrow \left( A\cup \left( C-B \right)\to BD \right)

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

Замкнення множини атрибутів[ред.ред. код]

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

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

Застосування[ред.ред. код]

Проектування БД[ред.ред. код]

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

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

Декомпозиція відношень[ред.ред. код]

Теорема Хіта[ред.ред. код]

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

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

\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)

Див. також[ред.ред. код]

Література[ред.ред. код]