Теорія нормальних форм
4.2.Теорія нормальних форм.
4.2.1. Функціональні залежності.
Реляційна база даних містить як структурну, так і семантичну інформацію. Структура бази даних визначається числом і видом включених в неї відносин, і зв'язками типу "один до багатьох", що існують між кортежами цих відносин. Семантична частина описує безліч функціональних залежностей, існуючих між атрибутами цих відносин. Дамо визначення функціональної залежності.
Якщо дано два атрибута X і Y деякого відносини, то кажуть, що Y функціонально залежить від X. якщо в будь-який момент часу кожному значенню X відповідає рівно одне значення Y.
Функціональна залежність позначається X -> Y. Відзначимо, що X і Y можуть являти собою не тільки поодинокі атрибути, а й групи, складені з декількох атрибутів одного відносини.
Можна сказати, що функціональні залежності являють собою зв'язку типу "один до багатьох", що існують усередині відносини.
Деякі функціональні залежності можуть бути небажані.
Надлишкова функціональна залежність - залежність, що містить у собі таку інформацію, яка може бути отримана на основі інших залежностей, наявних в базі даних.
Коректної вважається така схема бази даних, в якій відсутні надлишкові функціональні залежності. В іншому випадку доводиться вдаватися до процедури декомпозиції (розкладання) наявного безлічі відносин. При цьому виникає такий безліч містить більше число відносин, які є проекціями відносин вихідного безлічі. (Операція проекції описана в розділі, присвяченому реляційної алгебри). Оборотний покроковий процес заміни даної сукупності відносин іншою схемою з усуненням надлишкових функціональних залежностей називається нормалізацією.
Умова оборотності вимагає, щоб декомпозиція зберігала еквівалентність схем при заміні однієї схеми на іншу, тобто в результуючих відносинах:- не повинні з'являтися раніше були відсутні кортежі;
- на відносинах нової схеми має виконуватися вихідне безліч функціональних залежностей.
4.2.2. 1NF - перша нормальна форма.
Для обговорення першої нормальної форми необхідно дати два визначення:
Простий атрибут - атрибут, значення якого атомарний (неподільні).
Складний атрибут - виходить з'єднанням декількох атомарних атрибутів, які можуть бути визначені на одному або різних доменах. (Його також називають вектор або агрегат даних).
Тепер можна дати
Визначення першої нормальної форми:
відношення знаходиться в 1NF якщо значення всіх його атрибутів атомарний.
Розглянемо приклад, запозичений з уже згадуваної статті Е.Ф.Кодда.
У базі даних відділу кадрів підприємства необхідно зберігати відомості про службовців, які можна спробувати уявити щодо службовець (НОМЕР_СЛУЖАЩЕГО, ІМ'Я, ДАТА_РОЖДЕНІЯ, ІСТОРІЯ_РАБОТИ, ДЕТИ).
З уважного розгляду цього відносини слід, що атрибути "історія_работи" і "діти" є складними, більш того, атрибут "історія_работи" включає ще один складний атрибут "історія_зарплати".Дані агрегати виглядають наступним чином:
Їх зв'язок представлена на рис. 4.3.
Рис.4.3. Початкове відношення.
Для приведення вихідного відносини службовець до першої нормальної формі необхідно декомпозировать його на чотири відносини, так як це показано на наступному малюнку:
Рис.4.4. Нормалізоване безліч відносин.
Тут первинний ключ кожного відносини виділено синьою рамкою, назви зовнішніх ключів набрані шрифтом синього кольору. Нагадаємо, що саме зовнішні ключі служать для подання функціональних залежностей, існуючих в вихідному відношенні. Ці функціональні залежності позначені лініями зі стрілками.
Алгоритм нормалізації описаний Е.Ф.Коддом наступним чином:- Починаючи з відносини, що знаходиться на верху дерева (рис. 4.3.), Береться його первинний ключ, і кожне безпосередньо підпорядковане відношення розширюється шляхом вставки домену або комбінації доменів цього первинного ключа.
- Первинний Ключ кожного розширеного таким чином відносини складається з Первинного Ключа, який був у цього відносини до розширення і доданого Первинного Ключа батьківського відносини.
- Після цього з батьківського відносини викреслюються всі непрості домени, віддаляється верхній вузол дерева, і ця ж процедура повторюється для кожного з решти піддерев.
4.2.3. 2NF - друга нормальна форма.
Дуже часто первинний ключ відносини включає кілька атрибутів (в такому випадку його називають складовим) - див. Наприклад, ставлення ДІТИ, показане на рис. 4.4. При цьому вводиться поняття повної функціональної залежності.
неключових атрибут функціонально повно залежить від складеного ключа якщо він функціонально залежить від усього ключа в цілому, але не знаходиться у функціональній залежності від будь-якого з вхідних в нього атрибутів.
Визначення другий нормальної форми:
Відношення знаходиться в 2НФ, якщо воно знаходиться в 1НФ і кожен неключових атрибут функціонально повно залежить від ключа.
4.2.4. 3NF - третя нормальна форма.
Перед обговоренням третьої нормальної форми необхідно ввести поняття транзитивної функціональної залежності.
Нехай X, Y, Z - три атрибута деякого відносини. При цьому X -> Y і Y -> Z, але зворотне
відповідність відсутня, тобто Z - / -> Y і Y - / -> X. Тоді Z транзитивній залежить від X.
Відношення знаходиться в 3НФ, якщо воно знаходиться у 2НФ і кожен неключових атрибут нетранзитивно залежить від первинного ключа.
4.2.5. BCNF - нормальна форма Бойса-Кодда.
Ця нормальна форма вводить додаткове обмеження в порівнянні з 3НФ.
Визначення нормальної форми Бойса-Кодда:
Відношення знаходиться в BCNF, якщо воно знаходиться у 3НФ і в ній відсутні залежності атрибутів первинного ключа від неключових атрибутів.
Ситуація, коли ставлення буде знаходиться в 3NF, але не в BCNF, виникає за умови, що відношення має два (або більше) можливих ключа, які є складовими і мають загальний атрибут. Зауважимо, що на практиці така ситуація зустрічається досить рідко, для всіх інших відносин 3NF і BCNF еквівалентні.
4.2.6. Багатозначні залежності і четверта нормальна форма (4NF).
Четверта нормальна форма стосується відносин, в яких є повторювані набори даних. Декомпозиція, заснована на функціональних залежностях, не приводить до виключення такої надмірності. У цьому випадку використовують декомпозицію, засновану на багатозначних залежностях.
Багатозначна залежність є узагальненням функціональної залежності і розглядає відповідності між множинами значень атрибутів.
Зауважимо, що зазначені аномалії зникають при заміні відносини ВИКЛАДАЧ його проекціями: Аномалія поновлення виникає в даному випадку тому, що по відношенню до ВИКЛАДАЧ є:- залежність безлічі значень атрибута КУРС від безлічі значень атрибута ІМ'Я
- залежність безлічі значень атрибута УЧЕБНОЕ_ПОСОБІЕ від безлічі значень атрибута ІМ'Я.
Такі залежності і називаються багатозначними і позначаються як Неважко показати, що багатозначні залежності завжди утворюють пов'язані пари, тому їх часто позначають Очевидно, що кожна функціональна залежність є багатозначною, але не кожна багатозначна залежність є функціональною.
Визначення четвертої нормальної форми:
Відношення знаходиться в 4NF якщо воно знаходиться в BCNF і в ньому отстутсвіі багатозначні залежності, які не є функціональними залежностями.
4.2.7. Залежності по з'єднанню і п'ята нормальна форма (5NF).
До цього часу ми припускали, що єдиною операцією, необхідною для усунення надмірності в відношенні, була декомпозиція його на дві проекції. Однак, існують відносини, для яких не можна виконати декомпозицію без втрат на дві проекції, але які можна піддати декомпозиції без втрат на три (або більше) проекцій. Цей факт отримав назву залежно по з'єднанню. а такі відносини називають 3-декомпозіруемие відносини (ясно, що будь-яке відношення можна назвати "n-декомпозіруемим", де n> = 2).
Детально це питання тут ми не обговорюємо (повний виклад см. В книзі К.Дейта), зауважимо лише, що залежність по з'єднанню є Обощение багатозначною залежності. Відносини, в яких є залежності по з'єднанню, які не є одночасно ні багатозначними, ні функціональними, також характеризуються аномаліями оновлення. Тому, вводиться поняття п'ятої нормальної форми.
Визначення п'ятої нормальної форми:
Відношення знаходиться в 5НФ тоді і тільки тоді, коли будь-яка залежність по з'єднанню в ньому визначається тільки його можливими ключами.