Нормальні форми реляційного відношення

Реляційне відношення перебуває в тій чи іншій нормальній формі, якщо задані на ньому функціональні залежності задовольняють певні умови. Відношення, які не перебувають у відповідній нормальній формі, мають певні небажані властивості, або аномалії. Відтак виникає потреба в нормалізації, орієнтованій на те, щоб позбавити реляційні відношення цих властивостей. Аномалії виникають унаслідок того, що реляційні відношення можуть містити надлишкові функціональні залежності, тобто кількість атрибутів відношення може бути завеликою, і тоді постає питання про коректність його схеми. Коректною вважається схема, що не містить небажаних функціональних залежностей. Виправлення некоректних схем здійснюється за допомогою процедури декомпозиції (розкладання) реляційного відношення на множину інших відношень. Мета цієї процедури — побудова множини таблиць без небажаних функціональних залежностей та аномалій. Це і є суттю процесу нормалізації. Іншими словами, нормалізація — це зворотний процес заміни даної схеми реляційних відношень іншою схемою, в якій відношення мають просту й коректну форму. Зворотність нормалізації означає, що після її здійснення зберігається можливість повернення відношення до початкового стану.

Е. Кодд спочатку визначив три рівні нормалізації, які він назвав першою, другою і третьою нормальними формами (1НФ, 2НФ і ЗНФ). Згодом Р. Фейджин визначив четверту нормальну форму, в якій перебувають деякі відношення, що мають ЗНФ. Нарешті, була визначена ще одна форма, п'ята. Ці форми та відповідні залежності будуть розглянуті в підрозділах.

Складені домени і перша нормальна форма

Реляційна модель не допускає використання складених (неатомарних) доменів, тобто на перетині рядка і стовпця у таблиці має стояти атомарне значення, неподільне з точки зору всіх його можливих застосувань. Реляційне відношення перебуває в першій нормальній формі (1HФ), якщо всі його атрибути мають атомарні (прості) домени, відтак значення елементів таблиці є простими. Реляційне відношення називається нормалізованим, якщо воно перебуває в 1НФ.

На рис. 1 зображено структуру відношення СЛУЖБОВЕЦЬ, побудованого на атомарних доменах НС (номер службовця) і Прізвище та складеному домені Діти. Ця структура є деревоподібною і тому відношення не перебуває в 1НФ.

Розглянемо екземпляр відношення СЛУЖБОВЕЦЬ

Табл. 2 – Екземпляр відношення СЛУЖБОВЦЬ

У 1НФ цей екземпляр відношення зображатиметься у вигляді двох таблиць:

Службовці Діти

Реляційна модель даних означена лише для тих відношень, що перебувають у першій нормальній формі.

Неповні функціональні залежності та друга нормальна форма

Нехай на реляційному відношенні R задано набори атрибутів А і В. Функціональна залежність називається повною, якщо В не залежить функціонально від жодного піднабору , що не містить В.

На рис. 2 атрибут Аудиторія неповно залежить від набору атрибутів Викладач, Група, Предмет, оскільки він залежить і від одного атрибуту Предмет, що входить до складу цього набору.

Реляційному відношенню ЛЕКЦІЇ властиві аномалії, що пов'язані з операціями маніпулювання даними. Пояснимо, чому ці аномалії виникають.

Якщо в предметній області є функціональна залежність , це свідчить про наявність множини сутностей, складених з атрибутів (А, В), причому група атрибутів А є унікальним ідентифікатором сутностей цієї множини (ключем), а В – їхньою властивістю. Оскільки атрибут Аудиторія функціонально залежить від атрибута Предмет, то в нашій предметній області на цій парі атрибутів визначена окрема множина сутностей. Проте ми не зможемо незалежно маніпулювати сутностями даної множини, оскільки це призведе до таких аномалій.

Аномалія додавання

Ми не зможемо відобразити той факт, що в конкретній аудиторії читаються лекції з конкретного предмета доти, доки не будуть визначені викладач і група.

Аномалія видалення

Видаляючи рядок з таблиці ЛЕКЦІЇ, ми можемо видалити унікальну (таку, якої більше ніде не міститься) інформацію про те, що певний предмет читається в певній аудиторії.

Аномалія оновлення

Одне й те саме значення атрибута Аудиторія для даного предмета повторюється багато разів. Тому, якщо предмет став читатися в іншій аудиторії, необхідно буде замінити номер аудиторії в усіх рядках таблиці ЛЕКЦІЇ.

З поняттям повної функціональної залежності пов'язане поняття другої нор­мальної форми.

Реляційне відношення перебуває в другій нормальній формі (2НФ), якщо воно перебуває в першій нормальній формі й усі його не первинні атрибути функціонально повно залежать від певного можливого ключа.

Друга нормальна форма нейтралізує аномалії, пов'язані з неповними функціональними залежностями. Звести відношення до другої нормальної форми можна лише шляхом його поділу (декомпозиції) принаймні на два інших. Але цей поділ має відповідати таким умовам:

• відношення, які отримуємо в результаті, є проекціями початкового;

• початкове реляційне відношення можна відновити з кінцевих за допомогою операції природного з'єднання без втрат даних;

• під час декомпозиції не втрачаються функціональні залежності (тобто множини залежностей початкового й кінцевого відношень є еквівалентними).

Шлях до вирішення цієї проблеми дає теорема, доведена І. Хітом.

Теорема Хіта

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

Алгоритм зведення схеми відношення до 2НФ є таким. Нехай задано реляційне відношення R із множиною атрибутів М. Якщо в R є неповна функціональна залежність непервинного атрибута В від можливого ключа А, то R декомпонується на дві проекції: і ( – це теоретико-множинна різниця). Якщо отримані в результаті таблиці все ще не перебувають у другій нормальній формі, до них знову застосовується це правило, доки всі відношення не досягнуть 2НФ.

Наприклад, для наведеного вище реляційного відношення ЛЕКЦІЇ алгоритм нормалізації приведе до таких двох таблиць: ЛЕКЦІЇ (Викладач. Група. Предмет. Пара, День) і ЩО-ДЕ (Предмет. Аудиторія). Декомпозиція виконана на основі теореми Хіта за функціональною залежністю Предмет -> Аудиторія.

Початкову таблицю можна відновити без втрат з отриманих проекцій шляхом природного з'єднання за атрибутом Предмет. Це твердження обґрунтовується тим, що таблиця ЛЕКЦІЇ містить у повному складі той самий ключ, що й початкове реляційне відношення, тому під час проектування зберігаються всі кортежі. Значення атрибута Аудиторія можна однозначно відновити з іншої таблиці, оскільки має місце функціональна залежність Предмет -> Аудиторія.

Процес зведення реляційного відношення до другої нормальної форми у певних випадках не є однозначним. У зв'язку з цим вводиться таке поняття.

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

Транзитивні залежності й третя нормальна форма

Поняття функціональної транзитивної залежності добре відоме в класичній теорії множин та теорії відношень. У реляційному підході використовується більш вузьке тлумачення цього терміна.

Набір атрибутів С транзитивно залежить від набору атрибутів А, якщо існує такий набір атрибутів В, що Останньою умовою реляційний варіант означення відрізняється від класичного.

Наявність у реляційному відношенні транзитивної залежності призводить до тих самих аномалій, що й наявність неповної функціональної залежності. Якщо в R (А,В,С) є функціональні залежності А -> В та В -> С, то таке відношення містить інформацію про дві множини сутностей: (А,В) та (В,С), що призводить до аномалій додавання, видалення й оновлення.

З поняттям функціональної транзитивної залежності пов'язане поняття третьої нормальної форми.

Реляційне відношення перебуває в третій нормальній формі (3НФ), якщо воно перебуває в другій нормальній формі й не містить транзитивних функціональних залежностей непервинних атрибутів від можливих ключів.

Декомпозиція реляційного відношення на кілька відношень у третій нормальній формі має задовольняти ті самі властивості, що й декомпозиція до другої нормальної форми. Алгоритм зведення до 3НФ базується на теоремі Хіта. Розглянемо його детальніше.

Нехай задано відношення R з атрибутами (або наборами атрибутів) А,В,С, де А — можливий ключ, і є функціональні залежності . Тоді таблиця R декомпонується на дві проекції:. Якщо отримані відношення все ще не перебувають у третій нормальній формі, до них знову застосовується зазначене правило.

Третя нормальна форма вимагає відсутності транзитивної залежності саме непервинних, а не всіх атрибутів відношення. Тому відношення НАВЧАННЯ, функціональні залежності якого зображені на рис. 3, перебуває в 3НФ.

Відношенню в 3НФ також властиві аномалії додавання, видалення й оновлення. У зв'язку з цим вводиться поняття посиленої 3НФ і нормальної форми Бойса-Кодда.

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

Реляційне відношення перебуває в нормальній формі Бойса-Кодда (НФБК), коли воно має таку властивість: якщо довільний атрибут відношення, що не належить набору атрибутів А, залежить функціонально від А, то й усі атрибути відношення функціонально залежать від А.

Поняття посиленої ЗНФ і НФБК еквівалентні, й тому їх часто вживають як синоніми.

Алгоритм зведення до посиленої третьої нормальної форми такий самий, як і до ЗНФ. Наприклад, у результаті нормалізації зображеного на рис. 3 відно­шення (воно не перебуває у посиленій 3НФ) буде отримано два такі відношення: ВИКЛАДАННЯ(Студент, Викладач) і ДИСЦИПЛІНА(Викладач, Предмет).