Багатозначні залежності та четверта нормальна форма. Теорема Фейджина

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

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

Розглянемо наступний приклад. Нехай потрібно обліковувати дані про абітурієнтів, що поступають у ВНЗ. При аналізі предметної області були виділені наступні вимоги:

· Кожен абітурієнт має право здавати іспити на кілька факультетів одночасно.

· Кожен факультет має свій список предметів, що здаються.

· Той самий предмет може здаватися на декількох факультетах.

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

Припустимо, що нам потрібно зберігати дані про те, які предмети повинен здавати кожний абітурієнт. Спробуємо зберігати дані в одному відношенні "Абітурієнти-Факультети-Предмети":

Абитуриент	Факультет	Предмет
Іванов	Математичний	Математика
Іванов	Математичний	Інформатика
Іванов	Фізичний	Математика
Іванов	Фізичний	Фізика
Петров	Математичний	Математика
Петров	Математичний	Інформатика

Відношення "Абітурієнти-Факультети-Предмети"

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

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

Номер Абітурієнта	Номер Факультету	Номер Предмета

Модифіковане відношення "Абітурієнти-Факультети-Предмети"

Номер Абітурієнта	Абітурієнт
	Іванов
	Петров

Відношення "Абітурієнти"

Номер Факультету	Факультет
	Математичний
	Фізичний

Відношення "Факультети"

Номер Предмета	Предмет
	Математика
	Інформатика
	Фізика

Відношення "Предмети"

Тепер кожне найменування зустрічається тільки в одному місці.

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

Аномалія вставки. При спробі додати у відношення "Абітурієнти-Факультети-Предмети" новий кортеж, наприклад (Ситник, Математичний, Математика), ми зобов'язані додати також і кортеж (Ситник, Математичний, Інформатика), тому що всі абітурієнти математичного факультету зобов'язані мати той самий список предметів, що здаються. Відповідно, при спробі вставити в модифіковане відношення кортеж (3, 1, 1), ми зобов'язані вставити в нього також і кортеж (3, 1, 2).

Аномалія видалення. При спробі видалити кортеж (Іванов, Математичний, Математика), ми зобов'язані видалити також і кортеж (Іванов, Математичний, Інформатика) з тої ж самої причини.

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

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

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

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

Тоді атрибути (множини атрибутів) Y і Z багатозначно залежать від X (позначається X ->-> Y | Z), тоді і тільки тоді, коли з того, що у відношенні R містяться кортежі r₁=(x,y,z₁) і r₂=(x,y₁,z) випливає, що у відношенні R міститься також і кортеж r₃=(x,y,z).

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

Зауваження. Змінюючи місцями кортежі r₁ і r₂ у визначенні багатозначної залежності, отримаємо, що у відношенні R повинен міститися також і кортеж r₄=(x,y₁,z₁). Таким чином,атрибути X і Z, багатозначно залежні від X, поводяться "симетрично" стосовно атрибута X. В отношении "Абитуриенты-Факультеты-Предметы" имеется многозначная зависимость Факультет->->Абитуриенты|Предмет.

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

Оскільки багатозначні залежності завжди утворюють зв'язані пари, їх часто позначають

R.A ->->R.B | R.С

Теорема Фейджина (скорочене формулювання). Відношення R (A, B, C) можна спроектувати без втрат у відношення R1(A,B) і R2(A,C) у тому і тільки в тому випадку, коли багатозначні залежності A->B і A->С можуть бути рознесені у відношення R1 і R2.

 

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

Зауваження. Якщо у відношенні R є не менш трьох атрибутів X, Y, Z і є функціональна залежність X -> Y, то є і багатозначна залежність X ->-> Y | Z.

 

Дійсно, діючи формально відповідно до визначення багатозначної залежності, припустимо, що у відношенні R містяться кортежі r₁=(x,y,z₁) і r₂=(x,y₁,z). У силу функціональної залежності X ® Y звідси випливає, що y = y₁. Але тоді кортеж r₃=(x,y,z) у точності збігається з кортежем r₂=(x,y₁,z) і, отже, міститься у відношенні R. Таким чином, є багатозначна залежність X ®® Y | Z.

 

Таким чином, поняття багатозначної залежності є узагальненням поняття функціональної залежності.

Визначення 3. Багатозначна залежність X ->-> Y |Z називається нетривіальною багатозначною залежністю, якщо не існує функціональних залежностей X -> Y і X -> Z. У відношенні "Абітурієнти-Факультети-Предмети" є саме нетривіальна багатозначна залежність Факультет->->Абітурієнти|Предмет. У силу нетривіальності цієї залежності ми не можемо скористатися теоремою Хеза для декомпозиції відношення. Однак Р. Фейджином [52] доведена наступна теорема:

Теорема (Фейджина). Нехай X, Y, Z - множини атрибутів відношення R (X,Y,Z), що не перетинаються. Декомпозиція відношення R на проекції R ₁=[ X,Y ] і R ₂=[ X,Z ] буде декомпозицією без утрат тоді і тільки тоді, коли є багатозначна залежність X ®® Y | Z. Іншими словами, відношення R (X,Y,Z) можна спроектувати без втрат у відносини R ₁=[ X,Y ] і R ₂=[ X,Z ] у тому і тільки в тому випадку, коли багатозначні залежності X ->-> Y та X ®® Z можуть бути рознесені у відношення R₁ і R₂.

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

Зауваження. Якщо залежність X ->-> Y | Z є тривіальною, тобто існує одна з функціональних залежностей X -> Y чи X -> Z, то одержуємо теорему Хеза.

Доведення теореми.

Необхідність. Нехай декомпозиція відношення R на проекції R ₁=[ X,Y ] і R ₂=[ X,Y ] є

декомпозицією без утрат. Доведемо, що X ->-> Y | Z.

Припустимо, що відношення містить кортежі r₁=(x,y,z₁) і r₂=(x,y₁,z). Необхідно довести, що кортеж r₃=(x,y,z) також міститься в R. За визначенням проекцій, кортеж r’₁=(x,y) міститься в R ₁=[ X,Y ], а кортеж r’₂=(x,z) міститься в R ₂=[ X,Z ]. Тоді кортеж r₃=(x,y,z) міститься в природному з'єднанні R₁JOINR₂, а в силу того, що декомпозиція є декомпозицією без утрат, цей кортеж міститься й у R.

Необхідність доведена.

Достатність. Нехай є багатозначна залежність X ®® Y | Z. Доведемо, що декомпозиція відношення R на проекції R ₁=[ X,Y ] і R ₂=[ X,Z ] є декомпозицією без утрат.

Як і в доказі теореми Хеза, потрібно довести, що R₁JOINR₂ = R для будь-якого стану відношення R.

Включення R₁JOINR₂ Ê R доводиться як у теоремі Хеза. Таке включення виконується завжди для будь-якої декомпозиції відношення R.

Доведемо включення R₁JOINR₂ Í R. Нехай кортеж r=(x,y,z) ÎR₁JOINR_2. Це означає, що в проекції R ₁=[ X,Y ] міститься кортеж r’₁=(x,y), а в проекції R ₂=[ X,Z ] міститься кортеж r’₂=(x,z). За визначенням проекції, знайдеться таке значення z₁ атрибута Z, що відношення R містить кортеж r₁=(x,y,z₁). Аналогічно, знайдеться таке значення y₁ атрибута Y, що відношення R містить кортеж r₂=(x,y₁,z). Тоді за визначенням багатозначної залежності кортеж r=(x,y,z) ÎR. Включення доведене. Достатність доведена. Теорема доведена.

 

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

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

Тобто. відношення знаходиться в 4NF якщо воно знаходиться в BCNF і в ньому відсутні багатозначні залежності, що не є функціональними залежностями

Відношення "Абітурієнти-Факультети-Предмети" знаходиться в НФБК, але не в 4НФ. Відповідно до теореми Фейджина, це відношення можна без утрат декомпонувати на відношення:

 

Факультет	Абітурієнт
Математичний	Іванов
Фізичний	Іванов
Математичний	Петров

Відношення "Факультети-Абітурієнти"

Факультет	Предмет
Математичний	Математика
Математичний	Інформатика
Фізичний	Математика
Фізичний	Фізика

Відношення "Факультети-Предмети"

В отриманих відношеннях усунуті аномалії вставки і видалення, характерні для відношення "Абітурієнти-Факультети-Предмети".

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

Відношення з нетривіальними багатозначними залежностями виникають, як правило, у результаті природного з'єднання двох відношень по спільному полю, що не є ключовим у жодному з відношень. Фактично цее призводить до спробии зберігатити в одному відношенні інформаціюю про дві незалежні сутності. У якості ще одного приклада можна навести ситуацію, коли співробітник може мати багато робіт і багато дітей. Збереження інформації про роботи і дітей в одному відношенні призводить до виникнення нетривіальної багатозначної залежності Працівник->->Робота|діти.

 

Приклад 2. Розглянемо ще один приклад - приклад наступної схеми відношення:

Проекти (Проект_номер, Таб_номер, Проект_завдання)

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

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

Проект_номер (A)	Таб_номер (B)	Проект_завдання (C)
П1	C1
П1	C1
П1	С2
П1	С2
П2	C1
П2	C1
П2	C1
П2	С3
П2	С3
П2	С3

Внаслідок сформульованих вище умов єдиним можливим ключем відношення є складений атрибут Проект_Номер, Таб_номер, Проект_завдання і немає ніяких інших детермінантів. Отже, відношення Проекти знаходиться в BCNF. Але при цьому воно має недоліки: якщо, наприклад, деякий співробітник приєднується до даного проекту, необхідно вставити у відношення Проекти стільки кортежів, скільки завдань у ньому співробітник буде виконувати. Аналогічна ситуація виникає з появою нового проекту.

У відношенні Проекти існують наступні дві багатозначні залежності:

Проект_номер->->Таб_номер;

Проект_номер ->-> Проект_завдання

У нашому прикладі можна зробити декомпозицію відношення Проекти в два відношення Проекти-Співробітники і Проекти-Завдання:

---

Дата добавления: 2016-01-05; просмотров: 13; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!