Визначення
Функціональна залежність (ФЗ) - концепція, що лежить в основі багатьох питань, пов'язаних з реляційними базами даних. Математично являє собою бінарне відношення між множинами атрибутів даного відношення і є, по суті, зв'язком типу «один-до-багатьох». Позначається як “→”
Таблиця (Відношення) R (Назва таблиці) з двома атрибутами (стовпцями): x, y.
X | Y |
|---|---|
1 | 2 |
3 | 4 |
У цієї таблиці є наступна функціональна залежність
ФЗ: X → Y
Це означає, що атрибут X визначає атрибут Y. Грубо кажучи, якщо я скажу вам значення Х, то ви по цьому значенню зможете знайти відповідне значення Y в таблиці.
X називають детермінант, Y - залежна частина.
Повторення значень в атрибуті
Якщо у атрибуті X значення будуть повторюватись, тобто буде декілька “2“, “3“ і тд, то ми відразу не знаємо яке значення Y підібрати, для того, щоб існувала ФЗ X → Y навіть, якщо у X є дублікати, то для кожного дубліката має повторюватись його значення Y.
Припустимо значення атрибуту Y визначається за формулою: y = x²
X | Y |
|---|---|
2 | 4 |
4 | 16 |
5 | 25 |
-5 | 25 |
Якщо Х рівний 5, то Y завжди повинен бути рівний 25, бо дані добавляються в R за принципом y = x². Для одного значення X має завжди бути одне значення Y. Але зверніть увагу, якщо x = -5, то Y однаково буде 25, для ствердження ФЗ це допустимо.
Підсумовуючи:
Зрозуміло, якщо значення унікальне в атрибуті X, то ніяких проблем, ФЗ зберігається.
Ми розглянули поки тільки приклад з двома атрибутами, але важливо розуміти, що ФЗ також працює для множин атрибутів.
ABC → DEF
Приклад з п’ятьма атрибутами
Таблиця Студент
No | Name | Masks | Department | Course |
|---|---|---|---|---|
1 | a | 78 | CS | C1 |
2 | b | 60 | EE | C1 |
3 | a | 78 | CS | C2 |
4 | b | 60 | EE | C3 |
5 | c | 80 | IT | C3 |
6 | d | 80 | EC | C2 |
Перевірка ФЗ-стей для цієї таблиці:
No → Name; Ми бачимо, що усі значення в атрибуті унікальні, тобто ФЗ коректна.
Name → No; ФЗ не існує, бо існують дублікати і правило для дублікатів не працює.
No → Masks; Атрибут не маж дублікатів, ФЗ коректна.
Department → Course; ФЗ не існує, бо існують дублікати і правило для дублікатів не працює.
Course → Department; ФЗ не існує, бо існують дублікати і правило для дублікатів не працює.
ФЗ для множини атрибутів:
No, Name → Masks; У цьому випадку не має комбінації No і Name, яка би повторвалась, бо No унікальний, тобто ФЗ існує.
Name → Masks; Не всі дублікати у Name задовільняють праивло для дублікатів, тобто ФЗ не існує.
Name, Masks → Department, Course; Існують дублікати (a/78)але у обох повтореннях різне значення множини атрибутів (CS/C1 & CS/C2), правило для дублікатів не задовільняється, ФЗ не існує.
Тривіальна залежність
ФЗ називається тривіальною, якщо залежна частина є підмножиною детермінанта, простіше кажучи, якщо атрибути в правій частині є підмножиною атрибутів у лівій частині, то залежність тривіальна.
A | B |
|---|---|
1 | X |
2 | Y |
3 | Z |
4 | W |
У цій таблиці є такі тривіальні залежності:
A→A або AB→A
Якщо детермінант вже містить в собі залежну частину: детермінант (AB), то очевидно, що він матиме ФЗ і на B і на A.
Замикання множини залежностей
Одні функціональні залежності можуть припускати інші функціональні залежності. Наприклад:
Якщо A → B та B → С, то A → C. Всі логічно виведені залежності (A → C) з початкової множини функціональний залежностей (A → B; B → C) F, позначається як F+ (Замикання множини залежностей).
Множина функціональних залежностей F завжди є підмножиною свого замикання F+.
Замикання множини атрибутів
Замикання множини атрибутів (closure of a set of attributes) у реляційній базі даних — це набір всіх атрибутів, які можна функціонально визначити за допомогою даної множини атрибутів на основі заданої множини функціональних залежностей.
Є початкова множина атрибутів X(A, B, С, D) і у цієї множини атрибутів є множина функціональних залежностей F(A → B; B → C; C → D). Для того, щоб знайти X+ (замкнення множини атрибутів) необхідно виконати наступні наступний алгоритм замикання:
Ініціалізація: X+ = Xi
Розширення: Перебирайте кожну функціональну залежність (A → B) з F, якщо детермінант (A) є підмножиною X+, то додаємо атрибут залежної частини (B) в X+.
Повторюємо пункт 2 допоки неможливо буде додати жодний атрибут до X+.
Приклад для R(A, B, C, D)
Ініціалізація: X+ = {A}
Розширення: A → B, => {A} підмножина X+. Додаємо B до X+ : X+ ={A, B}
Розширення: B → C, => {B} підмножина X+. Додаємо C до X+ : X+ ={A, B, C}
Розширення: C → D, => {C} підмножина X+. Додаємо D до X+ : X+ ={A, B, C, D}
Завершення: Більше неможливо додати нових атрибутів.
Отже замикання множини атрибутів X+ є {A, B, C, D}.
Математичний опис з вікіпедії:
Тут описано, що множина замикання атрибутів Z+, береться з тих ФЗ які є членами замикання залежностей S+. (Початкофі ФЗ є підномножиною S+)
Незвідні множини залежностей
Нехай S1 та S2 деякі множини функціональних залежностей.
Якщо будь-яка функціональна залежність з 𝑆1 входить і в 𝑆2, тоді 𝑆2
називають покриттям множини функціональних залежностей 𝑆1.
Якщо S2 - покриття для S1, а S1 - для S2 (тобто S1+ = S2+), тоді такі множини називаються еквівалентними.
Множина ФЗ-ей 𝑆 називається незвідною тоді і тільки тоді, коли виконуються наступні вимоги
В кожній ФЗ залежна частина містить лише один елемент;
Детермінант кожної ФЗ є незвідним (ні один атрибут не може буди видаленим з детермінанта без зміни замкнення 𝑆+);
Жодну ФЗ з 𝑆 не можна виключити без зміни замкнення 𝑆+
Для будь-якої множини ФЗ існує не менше ніж одна еквівалентна множина, яка є незвідною. Така множина називається незвідним покриттям.
Використання
Замикання допомагає визначити мінімальний ключ (найменший можливий набір атрибутів в базі даних, який однозначно ідентифікує кожен рядок в таблиці) для відношення, тобто набір атрибутів, який однозначно ідентифікує кожний рядок в таблиці та використовується при нормалізації бази даних для розбиття таблиць на менші і більш стабільні форми, що допомагає уникнути аномалій оновлення, вставки та видалення даних. Також може бути корисним для оптимізації запитів до бази даних, оскільки дозволяє прогнозувати, які індекси або структури даних можуть бути використані для ефективного виконання запитів.
При кожному оновленні БД повинна перевіряти дотримання ФЗ. Значить, наявність великої кількості ФЗ небажане, інакше це призводить до уповільнення роботи. Для спрощення задачі необхідно скоротити набір ФЗ до мінімально необхідного. Якщо I є незвідним покриттям початкової множини ФЗ S, то перевірка виконання ФЗ з I автоматично гарантує виконання всіх ФЗ з S. Таким чином, задача пошуку мінімально необхідного набору ФЗ зводиться до пошуку незвідного покриття множини ФЗ, яке і буде використовуватись замість початкової множини.
