Багатозначні залежності. Четверта нормальна форма
Хоча в більшості випадків проектування РБД закінчується 3НФ або НФБК, теорія розглядає нормальні форми вищих порядків. Їх слід мати на увазі, оскільки вони пов'язані з аномаліями, що важко піддаються діагностиці, але, проте, зустрічаються на практиці. Ми обмежимося лише введенням 4НФ. Вона пов'язана з поняттям багатозначної залежності, яка, будучи залежністю між атрибутами, не є функціональною.
DEF. У відношенні R=<A,B,C> існує багатозначна залежність R.A ->>R.B у тому і тільки в тому випадку, якщо множина значень В, що відповідають парі А і С, залежить тільки від А і не залежить від С.
Коли ми розглядали ФЗ, то кожному значенню детермінанта відповідало лише одне значення залежного від нього атрибуту. При розгляді багатозначних залежностей виділяють випадки, коли одному значенню деякого атрибуту відповідає стійка постійна множин значень іншого атрибуту. Причому, якщо якому-небудь значенню пари <А,С> = <а1,с1> відповідає набір значень атрибуту B=<b1,b2,…,bN>, то цей же набір значень відповідає всім можливим парам виду <a1,c2>, <a1,c3>,…, <a1,cM>.
Розглянемо відношення, що моделюють майбутню здачу сесії студентами:
УЧБОВИЙ_ПЛАН = <№Зал.Кн., Група, Дисципліна>.
Перелік дисциплін, які повинен здавати студент, однозначно визначаються не його №Зач.Кн., а номером групи, в якій студент вчиться, з іншого боку, список студентів, що входять до групи, однозначно визначається її номером. Таким чином, відносно УЧБОВИЙ_ПЛАН є дві багатозначні залежності:
Група ->>Дисципліна;
Група ->> №Зал.Кн.
Якщо ми працюватимемо з вихідним відношенням, то не зможемо зберігати інформацію про нову групу і її учбовий план, поки туди не зарахований хоч би один студент. При зміні переліку дисциплін для групи, необхідно внести зміни до всього кортежу, що відноситься до цієї групи. При відрахуванні студента, ми повинні будемо видалити всі записи, що до нього відносяться і так далі. Таким чином, хоча наше відношення не містить аномальних ФЗ, аномалії модифікації присутні, вони обумовлені наявністю багатозначних відношень.
В теорії РБД доказано, що у відношенні R=<A,B,C> існує багатозначна залежність R.A ->>R.B тоді і лише тоді, коли існує багатозначна залежність R.A ->>R.С. Позбавлення від багатозначних залежностей спирається на теорему Фейджина.
Теорема Фейджина. Відношення R=<A,B,C> можна спроектувати без втрат у відношення R1=<A,B> та R2=<A,C> у тому, і лише в тому випадку, коли існує багатозначна залежність R.A ->>R.B (що рівнозначно існуванню двох багатозначних залежностей R.A ->>R.B і R.A ->>R.С).
DEF. Відношення R знаходиться в 4НФ тоді і тільки тоді, коли у випадку існування бігітозначної залежності R.A ->>R.B всі інші атрибути R функціонально залежать від А.
В нашому прикладі можно провести декомпозицію відношення УЧБОВИЙ_ПЛАН наступним чином:
ГРУПА = <№Зал.Кн., Група>
УЧБОВИЙ_ПЛАН = <Група, Дисципліна>
Надлишкові фз. Мінімальне покриття
Розглянутий алгоритм проектування БД не вільний від проблеми присутності надлишкових залежностей.
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
Мінімальне покриття не завжди є унікальним, оскільки порядок, в якому здійснюється процедура видалення надлишкових ФЗ, може вплинути на отримане мінімальне покриття. Надлишкові ФЗ слід видаляти по одній, кожен раз заново аналізуючи новий набір ФЗ на предмет присутності в ньому надлишкових. Ця процедура завершується, як тільки не залишиться жодної надлишкової ФЗ. Набір, що залишився, і є мінімальним покриттям.
Алгоритм проектування
Побудувати універсальне відношення для БД.
Визначити всі ФЗ, існуючі між атрибутами універсального відношення.
Видалити всі надлишкові ФЗ з вихідного набору ФЗ з метою отримання мінімального покриття. Ця процедура проводиться шляхом почергового видалення надлишкових ФЗ з наступною перевіркою одержуваного на кожному кроці набору ФЗ на наявність хоча б однієї надлишкової ФЗ.
Використовувати ФЗ з мінімального покриття для декомпозиції універсального відношення в набір НФБК-відношень. При цьому застосовується загальний алгоритм декомпозиції.
Якщо може бути отримано більш ніж одне мінімальне покриття, здійснюється порівняння результатів, отриманих на основі різних мінімальних покриттів, з метою визначення варіанту, краще за інших відповідає вимогам семантики області.
Після завершення процесу проектування, отриманий набір необхідно проконтролювати на предмет наявності не виявлених проблем:
одна і та ж ФЗ не повинна з'явитися більш ніж в одному відношенні;
набір ФЗ в отриманих стосунках повинен в точності збігатися з мінімальним покриттям;
не повинно бути надлишкових відношень.
Відношення надлишкове якщо:
всі атрибути його можуть бути знайдені в одному іншому відношенні;
всі атрибути можуть бути знайдені у відношенні, яке може бути отримане з інших відношень в результаті з'єднання.
Визначити чи будуть отримані відношення підтримувати тих типів запитів і операції оновлення, які передбачається використовувати.