R (Cod_book, Name, Author, Cod_rozdil, Name_rozdil, Data_write, Publisher, Year_publish, Page, Cod_client, FIO, Address, Telephone, №_pasp, Culture, Profession)

Контрольні запитання.

1. Визначте принципи вибору інформаційних об'єктів.

2. Дайте визначення понять: домен, елемент домену, кортеж відношення.

3. У чому полягає різниця між ступенем відношення та його потужністю?

4. Що таке універсальне відношення?

5. Наведіть приклад роботи універсального відношення при створенні бази

даних.

10.3. НОРМАЛІЗАЦІЯ

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

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

Кожній нормальній формі відповідає деякий визначений набір обмежень. Відношення знаходиться в деякій нормальній формі, якщо задовольняється властивий їй набір обмежень.

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

Основні властивості нормальних форм:

1. кожна наступна нормальна форма в деякому змісті краще попередньої;

2. при переході до наступної нормальної форми властивості попередніх нормальних властивостей зберігаються.

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

Визначення 1. Функціональна залежність.

У відношенні R атрибут Y функціонально залежить від атрибута X (X і Y можуть бути складовими) у тому і тільки в тому випадку, якщо кожному значенню X відповідає в точності одне значення Y: X -> Y.

Визначення 2. Повна функціональна залежність.

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

Визначення 3. Транзитивна функціональна залежність.

Функціональна залежність називається транзитивною, якщо з функціональних залежностей X -> Y та Y -> Z випливає, що X -> Z.

Наприклад, Вінниця входить до Поділля, а Поділля - до України. Для даного прикладу має місце транзитивна залежність ВІННИЦЯ -> УКРАЇНА.

Визначення 4. Неключовий атрибут.

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

Визначення 5. Взаємно незалежні атрибути.

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

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

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

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

Нехай задано відношення

ФАКУЛЬТЕТ (НАЙМЕНУВАННЯ, ПІБ ДЕКАНА, ТЕЛЕФОН).

Відношення ФАКУЛЬТЕТ задано в другій нормальній формі, тому що: {? }

у відношенні ФАКУЛЬТЕТ атрибут ТЕЛЕФОН, який не є основним, повністю залежить від будь-якого можливого ключа: НАЙМЕНУВАННЯ, ПІБ ДЕКАНА.

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

Розглянемо відношення:

СТУДЕНТ - КУРС_ПРОЕКТ (НОМЕР_ЗАЛІКОВОЇ_КНИЖКИ, КОД_ПРЕДМЕТУ, ПРІЗВИЩЕ_СТУДЕНТА, НОМЕР_ГРУПИ, ВИКЛАДАЧ, ПРОЦЕНТ_ВИКОНАННЯ).

Припустимо, що в одній групі можуть навчаються однофамільці. Тоді для цього відношення можливий тільки один ключ: НОМЕР_ЗАЛІКОВОЇ_КНИЖКИ, КОД_ПРЕДМЕТУ. Виходячи з прийнятого припущення, атрибут ПРІЗВИЩЕ_СТУДЕНТА не входить у ключ. Тоді атрибут НОМЕР_ЗАЛІКОВОЇ_КНИЖКИ не визначається значенням атрибута ПРІЗВИЩЕ_СТУДЕНТА, тобто атрибути ПРІЗВИЩЕ_СТУДЕНТА і НОМЕР_ГРУПИ не є основними, але функціонально залежать від основного атрибута НОМЕР_ЗАЛІКОВОЇ_КНИЖКИ, що входить у складовий ключ. Функціональні залежності між атрибутами цього відношення показані на рис.4.7.

Рисунок 4.7 - Функціональна залежність

Розщепивши вихідне відношення на два нових у другій нормальній формі, можна усунути надлишковість (рис. 4.8). При виконанні цієї операції розбивки на два відношення враховано те, що атрибути, які функціонально залежать від одного основного атрибута разом із ним утворять одне відношення з єдиним ключем НОМЕР_ЗАЛІКОВОЇ_КНИЖКИ, а інші атрибути, які функціонально повно залежать від складового ключа, залишено у вихідній схемі.

Розглянемо приклад схеми відношення:

СПІВРОБІТНИКИ - ВІДДІЛИ - ПРОЕКТИ

(СПІВРОБ_НОМЕР, СПІВРОБ_ЗАРП, ВІДДІЛ_НОМЕР, ПРО_НОМЕР, СПІВРОБ_ЗАВДАННЯ)

У відношенні використані скорочення: СПІВРОБ - співробітник, ЗАРП - зарплата, ПРО - проект.

Первинний ключ:

СПІВРОБ_НОМЕР, ПРО_НОМЕР.

Функціональні залежності:

СПІВРОБ_НОМЕР -> СПІВРОБ_ЗАРП

СПІВРОБ_НОМЕР -> ВІДДІЛ_НОМЕР

ВІДДІЛ_НОМЕР -> СПІВРОБ_ЗАРП

СПІВРОБ_НОМЕР, ПРО_НОМЕР -> СПІВРОБ_ЗАВДАННЯ.

Хоча первинним ключем є складовий атрибут СПІВРОБ_НОМЕР, ПРО_НОМЕР, атрибути СПІВРОБ_ЗАРП і ВІДДІЛ_НОМЕР функціонально залежать від частини первинного ключа, тобто атрибута СПІВРОБ_НОМЕР.

В результаті, неможливо вставити у відношення СПІВРОБІТНИКИ - ВІДДІЛИ - ПРОЕКТИ кортеж, що описує співробітника, який ще не виконує ніякого проекту (первинний ключ не може містити невизначене значення). При видаленні кортежу не тільки руйнується зв'язок даного співробітника з даним проектом, але втрачається інформація про те, в якому відділі він працює. При переводі співробітника в інший відділ необхідно модифікувати всі кортежі, які описують цього співробітника, або одержимо неузгоджений результат. Такі неприємні явища називаються аномаліями схеми відношення. Вони усуваються шляхом нормалізації.

Виконаємо декомпозицію відношення СПІВРОБІТНИКИ - ВІДДІЛИ в два відношення СПІВРОБІТНИКИ - ВІДДІЛИ і СПІВРОБІТНИКИ - ПРОЕКТИ:

СПІВРОБІТНИКИ - ВІДДІЛИ (СПІВРОБ_НОМЕР, СПІВРОБ_ЗАРП, ВІДДІЛ_НОМЕР)

Первинний ключ:

СПІВРОБ_НОМЕР

Функціональні залежності:

СПІВРОБ_НОМЕР -> СПІВРОБ_ЗАРП

СПІВРОБ_НОМЕР -> ВІДДІЛ_НОМЕР

ВІДДІЛ_НОМЕР -> СПІВРОБ_ЗАРП

СПІВРОБІТНИКИ - ПРОЕКТИ (СПІВРОБ_НОМЕР, ПРО_НОМЕР, СПІВРОБ_ЗАВДАННЯ)

Первинний ключ:

СПІВРОБ_НОМЕР, ПРО_НОМЕР

Функціональна залежність: СПІВРОБ_НОМЕР, ПРО_НОМЕР -> СПІВРОБ_ЗАВДАННЯ

Кожне з цих двох відношень знаходиться в 2НФ і в них усунуті відзначені вище аномалії.

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

Наприклад, відношення:

ГУРТОЖИТОК (ПІБ_СТУДЕНТА, НОМЕР_ГРУПИ, НОМЕР_КІМНАТИ, СТАРОСТА_КІМНАТИ)

знаходиться у другій нормальній формі, але не в третій, тому що атрибут СТАРОСТА_КІМНАТИ залежить від атрибута НОМЕР_КІМНАТИ, який у свою чергу залежить від атрибута ПІБ_СТУДЕНТА і, отже, СТАРОСТА_КІМНАТИ транзитивно залежить від ПІБ_СТУДЕНТА. Це відношення можна привести до необхідної форми шляхом його розщеплення на два:

СТУДЕНТ-ГУРТОЖИТОК (ПІБ_СТУДЕНТА, НОМЕР_ГРУПИ, НОМЕР_КІМНАТИ)

та

КІМНАТА -ГУРТОЖИТОК (НОМЕР_КІМНАТИ, СТАРОСТА_КІМНАТИ)

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

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

Нехай маємо відношення

(ФІРМА, СКЛАД, ОБ'ЄМ)

Для даного відношення характерні такі аномалії:

1. Якщо в даний момент відсутня фірма, яка отримує товар зі складу, то в базу даних неможливо ввести інформацію про об'єм складу.

2. Якщо фірма перестає отримувати товар зі складу, то данні про склад та його об'єм не можна зберігати в базі даних.

3. Якщо об'єм складу змінився, то необхідно переглянути всі рядки відношення і змінити кортежі для форм, пов'язаних зі складом.

Причиною аномалій для даного відношення є наявність транзитивного зв'язку між атрибутами.

Для усунення аномалій розіб'ємо вихідне відношення на два:

ЗБЕРІГАННЯ (ФІРМА, СКЛАД) та

ОБ'ЄМ (СКЛАД, ОБ'ЄМ).

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

Розглянемо наступний приклад схеми відношення:

СПІВРОБІТНИКИ - ПРОЕКТИ (СПІВРОБІТНИКА_НОМЕР, СПІВРОБІТНИКА_ПРИЗВІЩЕ, ПРОЕКТУ_НОМЕР, СПІВРОБІТНИКА_ЗАВДАННЯ)

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

СПІВРОБІТНИКА_НОМЕР, ПРОЕКТУ_НОМЕР

СПІВРОБІТНИКА_ПРИЗВІЩЕ, ПРОЕКТУ_НОМЕР.

Функціональні залежності:

СПІВРОБІТНИКА_НОМЕР -> СПІВРОБІТНИКА_ПРИЗВІЩЕ;

СПІВРОБІТНИКА_НОМЕР -> ПРОЕКТУ_НОМЕР;

СПІВРОБІТНИКА_ПРИЗВІЩЕ -> СПІВРОБІТНИКА_НОМЕР;

СПІВРОБІТНИКА_ПРИЗВІЩЕ -> ПРОЕКТУ_НОМЕР;

СПІВРОБІТНИКА_НОМЕР, ПРОЕКТУ_НОМЕР -> СПІВРОБІТНИКА_ЗАВДАННЯ;

СПІВРОБІТНИКА_ПРИЗВІЩЕ, ПРОЕКТУ_НОМЕР -> СПІВРОБІТНИКА_ЗАВДАННЯ.

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

10.4. ОСНОВНІ НОРМАЛЬНІ ФОРМИ ВІДНОШЕНЬ

Незалежно від того, який із можливих ключів обраний у якості первинного ключа, ця схема знаходиться в 3НФ. Однак той факт, що є функціональні залежності атрибутів відношення від атрибута, що є частиною первинного ключа, приводить до аномалій. Наприклад, для того, щоб змінити ПРИЗВІЩЕ співробітника з даним номером погодженим способом, буде потрібно модифікувати всі кортежі, які включають його номер. Введемо визначення.

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

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

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

Очевидно, що ця вимога не виконана для відношення СПІВРОБІТНИКИ - ПРОЕКТИ. Можна виконати його декомпозицію до відношень СПІВРОБІТНИКИ і СПІВРОБІТНИКИ - ПРОЕКТИ:

СПІВРОБІТНИКИ (СПІВРОБІТНИКА_НОМЕР, СПІВРОБІТНИКА_ПРИЗВІЩЕ).

Можливі ключі:

СПІВРОБІТНИКА_НОМЕР;

СПІВРОБІТНИКА_ПРИЗВІЩЕ.

Функціональні залежності:

СПІВРОБІТНИКА_НОМЕР -> СПІВРОБІТНИКА_ПРИЗВІЩЕ;

СПІВРОБІТНИКА_ПРИЗВІЩЕ -> СПІВРОБІТНИКА_НОМЕР.

СПІВРОБІТНИКИ-ПРОЕКТИ (СПІВРОБІТНИКА_НОМЕР, ПРОЕКТУ_НОМЕР, СПІВРОБІТНИКА_ЗАВДАННЯ).

Можливий ключ:

СПІВРОБІТНИКА_НОМЕР, ПРОЕКТУ_НОМЕР.

Функціональні залежності:

СПІВРОБІТНИКА_НОМЕР, ПРОЕКТУ_НОМЕР -> СПІВРОБІТНИКА_ЗАВДАННЯ.

Можлива альтернативна декомпозиція, якщо вибрати за основу СПІВРОБІТНИКА_ПРИЗВІЩЕ. В обох випадках отримані відношення СПІВРОБІТНИКИ і СПІВРОБІТНИКИ - ПРОЕКТИ знаходяться в БКНФ, і їм не властиві відзначені аномалії.

Розглянемо відношення

R (МІСТО, АДРЕСА, ІНДЕКС).

Атрибут ІНДЕКС визначає індекс відділення зв'язку, яке обслуговує адресатів деякої вулиці міста, АДРЕСА - назву вулиці і номеру будинку. При цьому будемо припускати, що кортеж (С, S, Z) належить деякому відношенню зі схемою відношення R, якщо тільки в місті С є будинок за адресою S і Z є відповідним поштовим індексом. У цьому випадку мають місце такі функціональні залежності:

МІСТО, АДРЕСА -> ІНДЕКС;

ІНДЕКС -> МІСТО.

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

МІСТО, АДРЕСА і AДРЕСА, ІНДЕКС.

Схема відношення R (МІСТО, АДРЕСА, ІНДЕКС) не знаходиться в нормальній формі Бойса-Кода, так як має місце залежність ІНДЕКС -> МІСТО. Декомпозицією відношення його можна привести до нормальної форми Бойса-Кода.

Розглянемо приклад схеми відношення:

ПРОЕКТИ (ПРОЕКТУ_НОМЕР, ПРОЕКТУ_СПІВРОБ, ПРОЕКТУ_ЗАВДАННЯ).

Відношення ПРОЕКТИ містить номера проектів, кожний проект - список співробітників, які можуть виконувати проект, і список завдань, які передбачаються проектом. Співробітники можуть брати участь у декількох проектах, і різні проекти можуть включати однакові завдання.

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

ПРОЕКТ_НОМЕР, ПРОЕКТ_СПІВРОБ, ПРОЕКТ_ЗАВДАННЯ

і немає ніяких інших детермінантів. Отже, відношення ПРОЕКТИ знаходиться в БКНФ. Але при цьому воно має аномалії: якщо, наприклад, деякий співробітник приєднується до даного проекту, необхідно вставити у відношення ПРОЕКТИ стільки кортежів, скільки завдань у ньому передбачено.

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

У відношенні ПРОЕКТИ існують наступні дві багатозначні залежності:

ПРОЕКТ_НОМЕР ->-> ПРОЕКТ_СПІВРОБ;

ПРОЕКТ_НОМЕР ->-> ПРОЕКТУ_ЗАВДАННЯ.

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

Відношення R знаходиться в четвертій нормальній формі (4НФ) у тому і тільки в тому випадку, якщо у випадку існування багатозначної залежності A ->-> B всі інші атрибути R функціонально залежать від A.

У нашому прикладі можна виконати декомпозицію відношення ПРОЕКТИ на два відношення ПРОЕКТИ-СПІВРОБІТ і ПРОЕКТИ-ЗАВДАННЯ:

ПРОЕКТИ-СПІВРОБІТ (ПРОЕКТ_НОМЕР, ПРОЕКТ_СПІВРОБІТ);