Принцип замикання множини атрибутів

Принцип замикання множини атрибутів є фундаментальним принципом, що лежить в основі усіх правил поводження із функціональними залежностями. Цей принцип можливо пояснити на такому прикладі. Існує деяка множина атрибутів, яка послідовно розширюється шляхом додання в нього атрибутів до правих частин функціональних залежностей, у яких вже присутні атрибути лівих частин множини. На певному кроці цієї процедури подальше розширення множини атрибутів стає неможливим. Отримана таким чином кінцева множина атрибутів стає замкненою. Нижче наведений опис алгоритму визначення замкнення множини атрибутів { А₁ , А₂ ,. А_n } по відношенню до деякої множини FD.

1. Хай змінна Х представляє множину атрибутів, яке підлягає розширенню до моменту досягнення замикання. Початковим значенням Х є множина атрибутів
{ А₁ , А₂ ,. А_n }.

2. Виконується пошук деякої FD В ₁ , В₂, В_n → С, такої, що усі атрибути
В ₁ , В₂, В_n належать множині Х, а С – ні. Якщо вказана FD існує, С додається у множину Х.

3. Крок 2 повторюється до тих пір, доки існують відповідні FD, атрибути яких підлягають включенню у множину Х. На певному кроці процес розширення припиняється, оскілки кількість атрибутів певної предметної області, яку описує множина Х, є кінцевою.

4. Після завершення процедури розширення множина Х містить шукане значення замкнення, яке позначається як { А₁ , А₂ ,. А_n }⁺

Приклад 2. У початкове відношення уключені атрибути A, B, C, D, E і F. Виконуються такі FD: А В → С, B C → A D, D → E, C F → B. Які атрибути будуть належати до замкненої множини, якщо первинною множиною атрибутів була множина {A,B}?

Для пошуку рішення застосуємо алгоритм.

1. Хай Х = { A,B }. Це означає, що до лівої частини відношення належать спочатку атрибути А, В.
2. Відшукуємо серед FD такої, яка у лівій частині містить атрибути первинної множини. Це А В → С. Згідно кроку 2 алгоритму атрибут С може бути включений до складу первинної множини атрибутів, тобто {A, B, С}
   Повторимо крок 2 алгоритму для розширеної множини {A, B, С}. Серед FD буде вірним B C → A D, у якому атрибут А у правій частині є тривіальним, а атрибут D новим. Атрибут D уключається до відношення, тобто {A, B, С, D}
   Повторимо крок 2 алгоритму для множини {A, B, С, D}.Серед FD буде вірним
   D → E, у якому атрибут Е у правій частині є новим. Атрибут Е уключається до відношення, тобто {A, B, С, D, Е}
   Знову повторюємо крок 2 для перевірки атрибуту F на предмет його включення у відношення {A, B, С, D, Е}.Але FD (C F → B), до якої він входить, є невірним і атрибут F не може бути уключений до відношення {A, B, С, D, Е}. Оскільки усі FD перевірені, переходимо до кроку 3.
3. Отримана множина є замкненою, тобто {A,B, С, D, Е}⁺

Правило транзитивності дозволяє об’єднувати функціональні залежності у логічний ланцюг.

• Якщо для відношення R справедливі FD
  
  А₁ , А₂ ,. А_n → В ₁ , В₂ , В_m
  В ₁ , В₂, В_m → С₁, С₂, С_k
  
  то справедлива і FD
  
  А₁ , А₂ ,. А_n → С₁, С₂, С_k

Приклад 3.. Для множини сутностей Movies справедливі є FD

title year → studioName
studioName → studioAddr

Чи є справедливою FD title year → studioAdd?

Правило транзитивності дає позитивну відповідь на це питання.

Поиск по сайту: