Надлишкові ФЗ. Мінімальне покриття

Розглянутий алгоритм проектування БД не вільний від проблеми присутності надлишкових залежностей.

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

Оскільки надлишкова ФЗ не містить унікальної інформації, вона може бути видалена з набору ФЗ без негативної дії на результати. Надлишкові ФЗ видаляються на початковому етапі проектування до примінення алгоритму декомпозиції.

Транзитивні залежності. Одним з прикладів надлишкових ФЗ являються транзитивні. Якщо А—»В, В—»С і А—»С входять в набір ФЗ, отже, А—»С є надлишковою і її використання в процесі проектування не потрібне, її слід виключити з набору перед початком проектування.

Малюнок 9 демонструє, як може бути спрощений набір ФЗ за допомогою виключення транзитивних залежностей. Використовуючи процедуру декомпозиції, спрощений набір ФЗ можна привести до нормальної форми Бойса – Кодда (НФБК) R(A,B,C,E):

R1(C, E); R2(B,C); R3(A,B).

Рис. 9

Додавання. Друга причина виникнення надлишкових ФЗ пов'язана з концепцією додавання. Розглянемо два випадки надлишковості цього вигляду (А,В,Z - атрибути, кожен з яких може бути складеним).

- Якщо A→B, то A,Z→B є коректною, але надлишковою ФЗ. Ілюстрація дана на рис. 10.

- Якщо A→B, то A,Z→B,Z є коректною, але збитковою ФЗ. Ілюстрація дана на рис. 11.

Рис. 10

 

Рис. 11

Правила виводу

Визначення транзитивності і концепція додавання торкаються три правил виводу з шести. Ці правила використовуються для спрощення вихідного набору ФЗ. Розглянемо ще три правила:

1. Об’єднання ФЗ: Якщо А→В і А→С, то А→В,С.

2. Декомпозиція ФЗ: Якщо А→В,С, то А→В і А→С.

3. Псевдотранзитивність: Якщо А→В і В,С→Z, то А,С→ Z.

Приведемо приклад застосування правил виводу. Відмітимо, що послідовність застосування неоднозначна.

А) Вихідний набір ФЗ.

Б) B, C → D видалена (додавання B → C)

В) А → B, C заміщена А → B & А → C (декомпозиція)

Г) А → C і А → D заміняються на А → К & К → C і А → B & В → D (транзитивність).

Мінімальне покриття

DEF. Набір ненадлишкових ФЗ, отриманих шляхом видалення всіх надлишкових ФЗ з вихідного набору ФЗ за допомогою шести правил виводу, називається мінімальним покриттям.

 

Рис. 12

 

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

 

Алгоритм проектування

1. Побудувати універсальне відношення для БД.

2. Визначити всі ФЗ, існуючі між атрибутами універсального відношення.

3. Видалити всі надлишкові ФЗ з вихідного набору ФЗ з метою отримання мінімального покриття. Ця процедура проводиться шляхом почергового видалення надлишкових ФЗ з наступною перевіркою одержуваного на кожному кроці набору ФЗ на наявність хоча б однієї надлишкової ФЗ.

4. Використовувати ФЗ з мінімального покриття для декомпозиції універсального відношення в набір НФБК-відношень. При цьому застосовується загальний алгоритм декомпозиції.

5. Якщо може бути отримано більш ніж одне мінімальне покриття, здійснюється порівняння результатів, отриманих на основі різних мінімальних покриттів, з метою визначення варіанту, краще за інших відповідає вимогам семантики області.

6. Після завершення процесу проектування, отриманий набір необхідно проконтролювати на предмет наявності не виявлених проблем:

- одна і та ж ФЗ не повинна з'явитися більш ніж в одному відношенні;

- набір ФЗ в отриманих стосунках повинен в точності збігатися з мінімальним покриттям;

- не повинно бути надлишкових відношень.

Відношення надлишкове якщо:

- всі атрибути його можуть бути знайдені в одному іншому відношенні;

- всі атрибути можуть бути знайдені у відношенні, яке може бути отримане з інших відношень в результаті з'єднання.

7. Визначити чи будуть отримані відношення підтримувати тих типів запитів і операції оновлення, які передбачається використовувати.