yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Різні конспекти лекцій->Содержание->1.3.3 Нормальні форми відношень. Створення логічної моделі реляційної БД

Організація баз даних і знань

1.3.3 Нормальні форми відношень. Створення логічної моделі реляційної БД

Під реляційною БД прийнято розуміти сукупність екземплярів кінцевих відношень. Сукупність схем відношень утворює схему реляційної БД.

Схема реляційної БД є логічною моделлю реляційної БД. На основі інформаційної моделі у процесі проектування створюються логічна й фізична моделі даних. Інформаційна модель даних відбиває потреби системи в даних і зв'язку між даними з погляду їх споживачів - користувачів; логічна модель даних є незалежним логічним поданням даних; фізична модель даних містить визначення всіх реалізованих об'єктів у конкретній БД для конкретної СКБД.

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

·      первинні ключі відношень повинні бути мінімальними;

·      число відношень БД повинне по можливості давати найменшу надмірність даних – вимога надійності даних;

·      число відношень БД не повинне приводити до втрати продуктивності системи;

·      дані не повинні бути суперечливими, тобто при виконанні операцій включення, видалення й відновлення даних їх потенційна суперечливість повинна бути зведена до мінімуму;

·      схема відношень БД повинна бути стійкою, здатною адаптуватися до змін при її розширенні додатковими атрибутами – вимога гнучкості структури БД;

·      розкид часу реакції на різні запити до БД не повинен бути великим;

·      дані повинні правильно відбивати стан ПО БД у кожен конкретний момент часу – вимога актуальності даних;

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

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

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

У теорії реляційних БД звичайно виділяється така послідовність нормальних форм: перша нормальна форма (1NF); друга нормальна форма (2NF); третя нормальна форма (3NF); нормальна форма Бойса-Кодда (BCNF); четверта нормальна форма (4NF); п'ята нормальна форма, або нормальна форма проекції-з'єднання (5NF або PJ/NF).

Основні властивості нормальних форм полягають у такому: кожна наступна нормальна форма у деякому змісті краще попередньої нормальної форми; при переході до наступної нормальної форми властивості попередніх нормальних форм зберігаються.

Перша нормальна форма – відношення перебуває у 1NF, якщо всі атрибути відношення є простими (вимогу атомарності атрибутів), тобто не мають компонентів. Іншими словами, домен атрибута повинен складатися з неподільних значень і не може містити в собі безліч значень із більше елементарних доменів.

Нехай є змінне відношення: Employer_Project_Task {Em_Number, Em_Degrees, Em_Pay, Pr_Number, Em_Task}. Атрибути містять відповідно дані про номер справи, розряд та заробітну платню службовця, номер проекту й про завдання, що виконує службовець у даному проекті. Припустимо, що розряд службовця визначає розмір його заробітної плати й що кожен службовець може брати участь у декількох проектах за умови виконання тільки одного завдання. Тоді очевидно, що єдино можливим ключем відношення є складений атрибут {Em_Number, Pr_Number }. Діаграма мінімальної множини ER показана на рис. 1.19. У наведеному відношенні деякі функціональні залежності атрибутів від можливого ключа не є мінімальними. Це призводить  до так званих аномалій відновлення. Під аномаліями відновлення розуміються труднощі, з якими зустрічаються при виконанні операцій додавання кортежів у відношення (INSERT), видалення кортежів (DELETE) і модифікації кортежів (UPDATE).

 

Рисунок 1.19 – ER-діаграма відношення Employer_Project_Task

 

Стосовно нашого прикладу:

·      додавання кортежів – ми не можемо доповнити відношення Employer_Project_Task даними про службовця, який ще не бере участь у жодному проекті (Em_Number є частиною первинного ключа й не може містити невизначених значень). Тим часом часто буває, що спочатку службовця беруть на роботу, встановлюють його розряд і розмір заробітної плати, а лише потім призначають для нього проект;

·      видалення кортежів – ми не можемо зберегти у відношенні Employer_Project_Task дані про службовця, який завершив участь у своєму останньому проекті (з тієї причини, що значення атрибута Pr_Number для цього службовця стає невизначеним);

·      модифікація кортежів – щоб змінити розряд службовця, ми будемо змушені модифікувати всі кортежі з відповідним значенням атрибута Em_Number. У іншому випадку буде порушений природний зв'язок Em_Number → Em_Degrees (в одного службовця є тільки один розряд).

Для подолання цих труднощів можна зробити декомпозицію змінного відношення Employer_Project_Task на два змінні відношення – Employer {Em_Number, Em_Degrees, Em_Рау} і Employer_Project_Task {Em_Number, Pr_Number, Em_Task}. На рис. 1.20 показані діаграми ER цих відношень. Тепер ми можемо легко впоратися з операціями відновлення.

 

 

Рисунок 1.20 – ER-діаграми у змінних відношеннях Employer і Employer_Project_Task

 

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

Будемо вважати атрибут відношення ключовим, якщо він є елементом якого-небудь ключа відношення. В іншому випадку атрибут буде вважатися неключовим. Відношення перебуває у 2NF, якщо воно перебуває у 1NF, і всі неключові атрибути відношення функціонально мінімально залежать від первинного ключа. Іншими словами, 2NF вимагає, щоб відношення не містило часткових функціональних залежностей.

Стосовно нашого прикладу: відношення Employer знаходиться у 2NF, а відношення Employer_Project_Task – ні, оскільки атрибут Em_Task функціонально залежить від двох ключових атрибутів: Em_Number та Pr_Number. Будь-яке змінне відношення, що перебуває у 1NF, але не перебуває у 2NF, може бути зведене до набору змінних відношень, що перебувають у 2NF. У результаті декомпозиції ми одержуємо набір проекцій вихідного змінного відношення, природне з'єднання значень яких відтворює значення вихідного змінного відношення (тобто це декомпозиція без втрат).

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

Відношення перебуває у 3NF, якщо воно перебуває в 2NF, і всі неключові атрибути відношення залежать тільки від первинного ключа. Іншими словами, 3NF вимагає, щоб відношення не містило транзитивних функціонального зв’язку неключових атрибутів від ключа.

Функціональні залежності відношення Employer як і раніше породжують деякі аномалії відновлення. Вони викликаються наявністю транзитивного зв’язку Em_Number → Em_Рау (через зв'язок Em_Number → Em_Degrees і Em_Degrees → Em_Рау). Ці аномалії пов'язані з надмірністю зберігання значення атрибута Em_Рау у кожному кортежі, що характеризує службовців із тим самим розрядом:

·      додавання кортежів – неможливо зберегти дані про новий розряд (і відповідному йому розміру зарплати), поки не з'явиться службовець із новим розрядом. Первинний ключ не може містити невизначені значення;

·      видалення кортежів – при звільненні останнього службовця з даним розрядом ми втратимо інформацію про наявність такого розряду й відповідному розміру зарплати;

·      модифікація кортежів – при зміні розміру зарплати, що відповідає деякому розряду, ми будемо змушені змінити значення атрибута Em_Рау у кортежах всіх службовців, яким призначений цей розряд (інакше не буде виконуватися зв'язок Em_Degrees → Em_Рау).

Можлива декомпозиція: для подолання цих труднощів зробимо декомпозицію змінного відношення Employer на два змінні відношення – Employer1 {Em_Number, Em_Degrees} й Degrees {Em_Degrees, Em_Рау}. На рис. 1.21 показані ER-діаграми цих змінних відношень.

 

Рисунок 1.21 – ER-діаграми у змінних відношеннях Employer1 і Degrees

 

Таким чином, процедура зведення відношення до 3NF складається у виконанні двох проекцій: по правій і по лівій частині транзитивного функціонального зв’язку.

Зрозуміло, що в процесі нормалізації декомпозиція відношення на незалежні проекції є кращою. Необхідні й достатні умови незалежності проекцій відношення забезпечує теорема Риссанена: проекції r1 і r2 відношення r є незалежними тоді й тільки тоді, коли кожний зв'язок у відношенні r логічно виходить зі зв'язку у r1 і r2; загальні атрибути r1 і r2 утворять можливий ключ хоча б для одного з цих відношень.

Проілюструємо вірність цієї теореми на прикладі декомпозиції відношення Employer. У декомпозиції на проекції Employer1 і Degrees загальний атрибут Em_Degrees є можливим (і первинним) ключем відношення Degrees, а єдиний додатковий зв’язок відношення Employer  (Em_Number→Em_Рау) логічно виходить зі зв'язку Em_Number→Em_Degrees і Em_Degrees→Em_Рау, які виконуються для відношення Employer1 й Degrees відповідно.

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

Нормальна форма Бойса-Кодда

Наприклад, нехай є змінне відношення Employer_Project_Task1 { Em_Number Em_Nаme, Pr_Number, Em_Task} з множиною зв'язків, зображених на рис. 1.22.

 

 

Рисунок 1.22 – Діаграма функціонального зв’язку відношення Employer_Project_Task1

 

У відношенні Employer_Project_Task1 службовці унікально ідентифікуються як за номерами справ, так і за іменами. Отже, існують зв’язки Em_Number→Em_Nаme й Em_Nаme→Em_Number. Але один службовець може брати участь у декількох проектах, тому можливими ключами є {Em_Number, Pr_Number} і {Em_Nаme, Pr_Number}.

Очевидно, що, хоча у відношенні Employer_Project_Task1 всі зв’язки неключових атрибутів від можливих ключів є мінімальними й транзитивні зв’язки відсутні, цьому відношенню властиві аномалії відновлення. Наприклад, у випадку зміни імені службовця необхідно обновити атрибут Em_Nаme у всіх кортежах відношення, що відповідають даному службовцеві. Інакше буде порушений зв'язок Em_Number→Em_Nаme, і БД виявиться у неузгодженому стані.

Причиною відзначених аномалій є те, що у вимогах 2NF і 3NF не була потрібна мінімальна функціональна залежність від первинного ключа атрибутів, що є компонентами інших можливих ключів. Проблему вирішує нормальна форма, що історично прийнята називати нормальною формою Бойса-Кодда і яка є уточненням 3NF у випадку наявності декількох можливих ключів, що перекриваються.

Змінна відношення перебуває в нормальній формі Бойса-Кодда (BCNF) у тому і тільки в тому випадку, коли будь-який виконуваний для цього змінного відношення нетривіальний і мінімальний функціональний зв'язок має як детермінант деякий можливий ключ даного відношення.

Відношення Employer_Project_Task1 може бути наведене до BCNF шляхом однієї з двох декомпозицій: Employer_Number_Nаme {Em_Number, Em_Nаme} і Employer_Number_Рroject_Task {Em_Number, Pr_Number, Pr_Task} з множиною зв’язків, показаними на рис. 7.5, і Employer_Number_Nаme {Em_Number, Em_Nаme} і Employer_Nаme_Project_Task {Em_Nаme, Pr_Number, Pr_Task} (зв’язки і значення результуючих змінних відношень виглядають аналогічно).

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

Розглянемо ще одну можливу інтерпретацію змінної відношення Employer_Project_Task. Припустимо, що кожен службовець може брати участь у декількох проектах, але в кожному проекті ним повинні виконуватися ті самі завдання. Можливе значення змінної відношення Employer_Project_Task показано на рис. 1.24.

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

 

 

Рисунок 1.23 – ER-діаграми відношень Employer_Number_Nаme і Employer_Number_Рroject_Task

 

 

Рисунок 1.24 – Можливе значення змінної відношення Employer_Project_Task

 

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

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

Труднощі, пов'язані з відновленням змінної відношення Employer_Project_Task, вирішуються шляхом його декомпозиції на два змінні відношення: Employer_Project_Number {Em_Number, Pr_Number} і Employer_Task {Em_Number, Em_Task}. Значення цих змінних відношень, що відповідають значенню змінної відношення Employer_Project_Task показані на рис. 1.25.

 

 

Рисунок 1.25 – Діаграми відношень Employer_Project_Number і Employer_Task

 

Зверніть увагу, що останній варіант змінної відношення Employer_Project_Task в BCNF, оскільки всі атрибути заголовка відношення входять до складу єдино можливого ключа. Раніше обговорені принципи нормалізації тут не застосовані, але ми одержали корисну декомпозицію. Справа в тому, що у випадку останнього варіанта відношення, ми маємо справу з новим видом залежності, уперше виявленим Роном Фейджином у 1971 р. Фейджин назвав залежності цього виду багатозначними (multi-valued dependency - MVD).

У відношенні Employer_Project_Task виконуються дві MVD: Em_Number→Pr_Number і Em_Number→Em_Task. Перша MVD означає, що кожному значенню атрибута Em_Number відповідає обумовлена тільки цим значенням множина значень атрибута Pr_Number. Аналогічно трактується друга MVD.

У змінній відношення r з атрибутами A, B, C (у загальному випадку складовими) є багатозначна залежність B від A (AB) у тому і тільки в тому випадку, коли множина значень атрибута B, що відповідає парі значень атрибутів A й C, залежить від значення A і не залежить від значення C. Багатозначні залежності мають цікаву властивість "подвійності", що демонструє така лема Фейджина:

У відношенні r {A, B, C} виконується MVD A→→B у тому і тільки в тому випадку, коли виконується MVD A→→C.

Функціональний зв'язок є частковим випадком MVD, коли множина значень залежного атрибута обов'язково складається з одного елемента. Таким чином, якщо виконується зв'язок A→B, то виконується й MVD A→→B.

Теорема Фейджина. Нехай є змінна відношення r з атрибутами A, B, C (у загальному випадку, складовими). Відношення r декомпозується без втрат на проекції {A, B} й {A, C} тоді й тільки тоді, коли для нього виконується MVD A→→B | C.

Відношення перебуває у 4NF, якщо воно перебуває в 3NF або BCNF і всі незалежні багатозначні функціональні зв’язки рознесені в окремі відношення з тим самим ключем. Іншими словами, 4NF застосовується при наявності у відношенні більш ніж однієї MVD і вимагає, щоб відношення не містило незалежних багатозначних MVD.

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

Приведення відношення до 4NF припускає його декомпозицію без втрат на дві проекції (як й у випадку 2NF, 3NF й BCNF). Однак бувають (хоча й нечасто) випадки, коли декомпозиція без втрат на дві проекції неможлива, але можна зробити декомпозицію без втрат на більше число проекцій. Будемо називати n-декомпозованими відношеннями відношення, що може бути декомпозовано без втрат на n проекцій.

У змінній відношення r з атрибутами (можливо, складовими) A й B MVD A→→B називається тривіальною, якщо або A€B, або A UNION B збігається із заголовком відношення r.

Тривіальна MVD завжди задовольняється. При A€B вона вироджується у тривіальний зв'язок. У випадку A UNION B = Hr вимоги багатозначної залежності дотримуються очевидним способом.

Для прикладу n-декомпозованого відношення при n > 2 розглянемо п'ятий варіант змінної відношення Employer_Project_Task, у якій є єдино можливий ключ {Em_Number, Pr_Number, Em_Task} і відсутні нетривіальні MVD (рис.1.26).

 

 

Рисунок 1.26 – Можливі значення змінної відношення Employer_Project_Task та результати проекцій

 

Залежність проекції/з'єднання. Твердження про те, що тіло відношення Employer_Project_Task відновлюється без втрат шляхом природного з'єднання його проекцій Employer_Project_Number, Project_Number_Task і Employer_Task еквівалентно наступному звичайному обмеженню реального світу, що для відношення Employer_Project_Task може бути сформульовано природною мовою в такий спосіб (BEPT, BEPN, BPNT і BET позначають тіла значень змінних відношення Employer_Project_Task, Employer_Project_Number, Project_Number_Task і Employer_Task відповідно): якщо службовець із номером en бере участь у проекті pn, і в проекті pn виконується завдання et, і службовець із номером en виконує завдання et, то службовець із номером en виконує завдання et у проекті pn.

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

Нехай задана змінна відношення r, і A, B, ..., Z є довільними підмножинами заголовка r (складовими, що перекриваються атрибутами). У змінної відношення r задовольняється залежність проекції/з'єднання (Project-Join Dependency - PJD) *( A, B, ..., Z) тоді й тільки тоді, коли будь-яке припустиме значення r можна одержати шляхом природного з'єднання проекцій цього значення на атрибути A, B, ..., Z.

У змінної відношення Employer_Project_Task виконується PJD* ({Em_Number, Pr_Number}, {Pr_Number, Em_Task}, {Em_Number, Em_Task}). Наявність такого PJD забезпечує можливість декомпозиції відношення на три для уникнення аномалії відновлення.

У змінної відношення r PJD *( A, B, ..., Z) називається можливими ключами, що маються на увазі, в тому і тільки в тому випадку, коли кожен складений атрибут A, B, ..., Z є суперключем r, тобто включає хоча б один можливий ключ r.

У змінної відношення r залежність проекції/з'єднання *(A, B, ..., Z) називається тривіальною, якщо хоча б один зі складених атрибутів A, B, ..., Z збігається із заголовком r.

Загальноприйняте визначення 5NF має такий вигляд: змінна відношення r перебуває в 5NF, або в нормальній формі проекції/з'єднання (5NF, або PJ/NF - Project-Join Normal Form) у тому і тільки в тому випадку, коли кожна нетривіальна PJD в r розуміється можливими ключами r.

Таким чином, щоб розпізнати, що дана змінна відношення r перебуває в 5NF, необхідно знати всі можливі ключі r і всі PJD цієї змінної відношення. Виявлення всіх залежностей з'єднання є нетривіальним завданням, і для його вирішення немає загальних методів. Тому на практиці проектування реляйціних БД методом нормалізації звичайно завершується після досягнення 4NF, і відношення, що перебувають в 4NF, як правило, перебувають і в 5NF. 5NF є "остаточною" нормальною формою, яку можна досягти в процесі нормалізації на основі проекцій.

Нормальні форми характеризуються такими властивостями:

1NF - всі атрибути відношення прості;

2NF - відношення перебуває в 1NF і не містить часткових залежностей;

3NF - відношення перебуває в 2NF і не містить транзитивних залежностей від ключа;

ВКNF - відношення перебуває в 3NF і не містить залежностей ключів від неключових атрибутів;

4NF - застосовується при наявності більш ніж одної багатозначної залежності - відношення перебуває в ВКNF або 3NF і не містить незалежних багатозначних функціональних залежностей;

5NF - відношення перебуває в 4NF і не містить залежностей по з'єднанню.

 

16