Нормалізація відносин. Шість нормальних форм

У даній темі я торкну 6 нормальних форм і методи приведення таблиць в ці форми.

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

Вбудовані терміни

Атрибут - це властивість певної сутності. Часто називається полем таблиці.

Домен атрибута - безліч допустимих значень, які може приймати атрибут.

Кортеж є кінцевою кількістю пов'язаних допустимих значень атрибутів, які разом описують деяку сутність (рядок таблиці).

Відношення - кінцеве безліч кортежів (таблиця).

Схема стосунку - це кінцева кількість атрибутів, які визначають певну сутність. Іншими словами, це структура таблиці, що складається з конкретного набору полів.

Проекція - відношення, отримане з вказаного шляхом видалення і (або) перестановки деяких атрибутів.

Функціональна залежність між атрибутами (безліччю атрибутів) X і Y означає, що для будь-якого допустимого набору кортежів в даному відношенні: якщо два кортежі збігаються за значенням X, то вони збігаються за значенням Y. Наприклад, якщо значення атрибуту «Назва компанії» - Canonical Ltd, то значенням атрибуту «Штаб-квартира» в такому кортежі завжди буде Millbank Tower, London, United Kingdom. Позначення: {X} -> {Y}.

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

Метод нормальних форм (НФ) полягає в зборі інформації про об'єкти вирішення завдання в рамках одного ставлення і подальшої декомпозиції цього відношення на кілька взаємопов'язаних відносин на основі процедур нормалізації відносин.

Мета нормалізації: виключити надлишкове дублювання даних, яке є причиною аномалій, що виникли при додаванні, редагуванні та видаленні кортежів (рядків таблиці).

Аномалією називається така ситуація в таблиці БД, яка призводить до протиріччя в БД або суттєво ускладнює обробку БД. Причиною є зайве дублювання даних у таблиці, яке викликається наявністю функціональних залежностей від не ключових атрибутів.

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

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

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

Перша нормальна форма

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

Наприклад, є таблиця «Автомобілі»:

Фірма	Моделі
BMW	M5, X5M, M1
Nissan	GT-R

Порушення нормалізації 1НФ відбувається в моделях BMW, оскільки в одній комірці міститься список з 3 елементів: M5, X5M, M1, тобто він не є атомарним. Перетворюємо таблицю на 1НФ:

Фірма	Моделі
BMW	M5
BMW	X5M
BMW	M1
Nissan	GT-R

Друга нормальна форма

Ставлення знаходиться у 2НФ, якщо воно знаходиться в 1НФ і кожен не ключовий атрибут недоторканно залежить від Первинного Ключа (ПК).

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

Наприклад, дана таблиця:

Модель	Фірма	Ціна	Знижка
M5	BMW	5500000	5%
X5M	BMW	6000000	5%
M1	BMW	2500000	5%
GT-R	Nissan	5000000	10%

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

Модель	Фірма		Ціна
M5	BMW		5500000
X5M	BMW		6000000
M1	BMW		2500000
GT-R	Nissan		5000000
Фірма		Знижка
BMW		5%
Nissan		10%

Третя нормальна форма

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

Розглянемо таблицю:

Модель	Магазин	Телефон
BMW	Ріал-авто	87-33-98
Audi	Ріал-авто	87-33-98
Nissan	Некст-Авто	94-54-12

Таблиця знаходиться у 2НФ, але не в 3НФ.

Атрибут «Модель» є первинним ключем. Особистих телефонів у автомобілів немає, і телефон залежить виключно від магазину.

Таким чином, у відношенні існують такі функціональні залежності: Модель - Магазин, Магазин - Телефон, Модель - Телефон.

Залежність Модель  Телефон є транзитивною, отже, ставлення не знаходиться в .

У результаті поділу вихідного ставлення отримуються два відносини, що знаходяться в 3НФ:

Магазин	Телефон
Ріал-авто	87-33-98
Некст-Авто	94-54-12
Модель	Магазин
BMW	Ріал-авто
Audi	Ріал-авто
Nissan	Некст-Авто

Нормальна форма Бойса-Кодда (НФБК) (приватна форма третьої нормальної форми)

Визначення 3НФ не зовсім підходить для наступних відносин:

1) відношення має два або більше потенційних ключа;

2) два і більше потенційних ключі є складовими;

3) вони перетинаються, тобто мають хоча б один загальний атрибут.

Для відносин, що мають один потенційний ключ (первинний), НФБК є 3НФ.

Ставлення знаходиться в НФБК, коли кожна нетривіальна і неприводима ліворуч функціональна залежність володіє потенційним ключем в якості детермінанта.

Припустимо, розглядається ставлення, що представляє дані про бронювання стоянки на день:

Номер стоянки	Час початку	Час закінчення	Тариф
1	09:30	10:30	Ощадливий
1	11:00	12:00	Ощадливий
1	14:00	15:30	Стандарт
2	10:00	12:00	Преміум-В
2	12:00	14:00	Преміум-В
2	15:00	18:00	Преміум-А

Тариф має унікальну назву і залежить від обраної стоянки і наявності пільг, зокрема:

• «Ощадливий»: стоянка 1 для пільговиків
• «Стандарт»: стоянка 1 для не пільговиків
• «Преміум-А»: стоянка 2 для пільговиків
• «Преміум-B»: стоянка 2 для не пільговиків.

Таким чином, можливі такі складові первинні ключі: {Номер стоянки, Час початку}, {Номер стоянки, Час закінчення}, {Тариф, Час початку}, {Тариф, Час закінчення}.

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

Недоліком даної структури є те, що, наприклад, помилково можна приписати тариф «Ощадливий» до бронювання другої стоянки, хоча він може відноситися тільки до першої стоянки.

Можна поліпшити структуру за допомогою декомпозиції відношення на два і додавання атрибута Має пільги, отримавши стосунки, що задовольняють НФБК (підкреслені атрибути, що входять до первинного ключа.):

Тарифи

Тариф	Номер стоянки	Має пільги
Ощадливий	1	Так.
Стандарт	1	Немає
Преміум-А	2	Так.
Преміум-В	2	Немає

Бронювання

Тариф	Час початку	Час закінчення
Ощадливий	09:30	10:30
Ощадливий	11:00	12:00
Стандарт	14:00	15:30
Преміум-В	10:00	12:00
Преміум-В	12:00	14:00
Преміум-А	15:00	18:00

Четверта нормальна форма

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

Відносно R (A, B, C) існує багатозначна залежність RA - > - > R.B в тому і тільки в тому випадку, якщо безліч значень B, відповідне парі значень A і C, залежить тільки від A і не залежить від С.

Припустимо, що ресторани виробляють різні види піци, а служби доставки ресторанів працюють тільки в певних районах міста. Складений первинний ключ відповідної змінної відношення включає три атрибути: {Ресторан, Вид піци, Район доставки}.

Така змінна відносини не відповідає 4НФ, оскільки існує наступна багатозначна залежність:

{Ресторан} ^ {Вид піци}

{Ресторан} ^ {Район доставки}

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

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

Однак, якщо до вихідної змінної відношення додати атрибут, функціонально залежний від потенційного ключа, наприклад ціну з урахуванням вартості доставки ({Ресторан, Вид піци, Район доставки} ^ Ціна), то отримане відношення буде знаходитися в 4НФ і його вже не можна піддати декомпозиції без втрат.

П'ята нормальна форма

Відносини знаходяться в 5НФ, якщо воно знаходиться в 4НФ і відсутні складні залежні з'єднання між атрибутами.

Якщо «Атрибут _ 1» залежить від «Атрибута _ 2», а «Атрибут _ 2» залежить від «Атрибута _ 3», а «Атрибут _ 3» залежить від «Атрибута _ 1», всі три атрибути обов'язково входять в один кортеж.

Це дуже жорстка вимога, яку можна виконати лише за додаткових умов. На практиці важко знайти приклад реалізації цієї вимоги в чистому вигляді.

Наприклад, деяка таблиця містить три атрибути: «Постачальник», «Товар» і «Покупець». Покупець _ 1 купує декілька Товарів у Постачальника _ 1. Покупець _ 1 придбав новий Товар у Постачальника _ 2. Тоді через викладену вище вимогу Постачальник _ 1 зобов "язаний постачати Покупцю _ 1 той самий новий Товар, а Постачальник _ 2 має постачати Покупцю _ 1, крім нового Товару, всю номенклатуру Товарів Постачальника _ 1. Цього на практиці не буває. Покупець вільний у своєму виборі товарів. Тому для усунення зазначеної скрути всі три атрибути розносять по різних відносинах (таблицях). Після виділення трьох нових відносин (Постачальник, Товар і Покупець) необхідно пам'ятати, що при витяганні інформації (наприклад, про покупців і товари) необхідно в запиті з'єднати всі три відносини. Будь-яка комбінація з'єднання двох відносин з трьох неминуче призведе до вилучення неправильної (некоректної) інформації. Деякі СУБД забезпечені спеціальними механізмами, що усувають вилучення недостовірної інформації. Тим не менш, слід дотримуватися загальної рекомендації: структуру бази даних будувати таким чином, щоб уникнути застосування 4НФ і 5НФ.

П'ята нормальна форма орієнтована на роботу з залежними з'єднаннями. Вказані залежні з'єднання між трьома атрибутами зустрічаються дуже рідко. Залежні з'єднання між чотирма, п'ятьма і більше атрибутами вказати практично неможливо.

Доменно-ключова нормальна форма

Змінна відношення знаходиться в ДКНФ тоді і тільки тоді, коли кожне накладене на неї обмеження є логічним наслідком обмежень доменів і обмежень ключів, накладених на цю змінну відносини.

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

Обмеження ключа - обмеження, яке стверджує, що певний атрибут або комбінація атрибутів є потенційним ключем.

Будь-яка змінна відносини, що знаходиться в ДКНФ, обов'язково знаходиться в 5НФ. Однак не будь-яку змінну відношення можна привести до ДКНФ.

Шоста нормальна форма

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

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

Для хронологічних баз даних визначені U_операторы, які розпаковують відносини за вказаними атрибутами, виконують відповідну операцію і упаковують отриманий результат. У даному прикладі з'єднання проекцій відносини повинно проводитися за допомогою оператора U_JOIN.

Працівники

Таб.	Час	Посада	Домашня адреса
6575	01-01-2000:10-02-2003	слюсар	вул.Леніна, 10
6575	11-02-2003:15-06-2006	слюсар	вул. Радянська, 22
6575	16-06-2006:05-03-2009	бригадир	вул. Радянська, 22

Змінна відношення «Працівники» не перебуває в 6НФ і може бути піддана декомпозиції на змінні відносини «Посади працівників» і «Домашні адреси працівників».

Посади працівників

Таб.	Час	Посада
6575	01-01-2000:10-02-2003	слюсар
6575	16-06-2006:05-03-2009	бригадир

Домашні адреси працівників

Таб.	Час	Домашня адреса
6575	01-01-2000:10-02-2003	вул.Леніна, 10
6575	11-02-2003:15-06-2006	вул. Радянська, 22

Література

Для більш глибокого і ґрунтовного вивчення розглянутої теми, рекомендується книга «Введення в системи баз даних» Кріса Дж. Дейта, на основі матеріалів якої і була написана ця стаття.