Відношення Проекти-Співробітники

(Проект_номер, Таб_номер)

Проект_номер (A)	Таб_номер (B)
П1	C1
П1	С2
П2	C1
П2	C3

Відношення Проекти-Завдання

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

Проект_номер (A)	Проект_завдання (C)
П1
П1
П2
П2
П2
П2

Обидва ці відношення знаходяться в 4NF і вільні від відзначених аномалій. З'єднання відношень Проекти-Співробітники і Проекти-Завдання дає відношення Проекти.

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

3. Залежності за з'єднанням (сполученням, асоціацією). П'ята нормальна форма (5НФ)

Дотепер ми припускали, що єдиною операцією, необхідною для усунення надлишковості у відношенні, була декомпозиція його на двох проекцій. В усіх розглянутих до цього моменту нормалізаціях провадилася декомпозиція одного відношення в два. Однак, існують відношення, для яких не можна виконати декомпозицію без утрат на дві проекцій, але які можна піддати декомпозиції без утрат на три (чи більш) проекції. Тобто можлива декомпозиція не в два (це неможливо), а в більше число відношень, кожне з який має кращі властивості. Цей факт одержав назву залежності по з'єднанню, а такі відношення називають 3-декомпоновані відносини (ясно, що будь-яке відношення можна назвати "n-декомпонованим", де n >= 2).

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

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

Розглянемо наступне відношення:

X	Y	Z

Відношення R

Усілякі проекції відношення, які включають по два атрибути, мають вигляд:

X	Y

Проекція R1=R[X,Y]

X	Z

Проекція R2=R[X,Z]

Y	Z

Проекція R3=R[Y,Z]

Як легко помітити, відношення R не відновлюється по жодному з попарних з'єднань R₁JOINR₂, R₁JOINR₃ чи R₂JOINR₃. Дійсно, з'єднання R₁JOINR₂має вигляд:

X	Y	Z

R1 JOIN R2

Сірим кольором виділений зайвий кортеж, відсутній у відношенні R. Аналогічно (у силу міркувань симетрії) і інші попарні з'єднання не відновлюють відношення R.

Однак відношення R відновлюється з'єднанням усіх трьох проекцій:

R₁JOINR₂JOINR₃ = R

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

Визначення 5. Нехай R є відношенням, а A, B, …, Z довільними (можливо такими, що перетинаються) підмножинами множини атрибутів відношення R. Тоді відношення R задовольняє залежності з'єднання *(A, B, …, Z) тоді і тільки тоді, коли воно рівносильно з'єднанню усіх своїх проекцій з підмножинами атрибутів A, B, …, Z, тобто:

R = R[A]JOINR[B]…...JOIN R[ Z ].

Іншими словами, відношення R(X, Y,...,Z) задовольняє залежності з'єднання *(X,Y,...,Z) у тому і тільки в тому випадку, коли R відновлюється без утрат шляхом з'єднання своїх проекцій на X, Y,..., Z.

Можна припустити, що відношення R у прикладі 3 задовольняє наступній залежності з'єднання:

*(XY, XZ, YZ).

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

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

Відповідно до визначення залежності з'єднання, теорема Фейджина може бути переформульована в такий спосіб:

Теорема Фейджина (інше формулювання). Відношення R (X,Y,Z) задовольняє залежності з'єднання *(XY, XZ) тоді і тільки тоді, коли є багатозначна залежність X ®® Y | Z.

Оскільки теорема Фейджина є взаємно зворотною, те її можна взяти як визначення багатозначної залежності. Таким чином, багатозначна залежність є частковим случаємо залежності з'єднання, тобто, якщо у відношенні є багатозначна залежність, то є і залежність з'єднання. Зворотне, звичайно, невірно.

Визначення 6. Залежність з'єднання *(A, B, …, Z) називається нетривіальною залежністю з'єднання, якщо виконуються дві умови:

· Одна з множин атрибутів A, B, …, Z не містить потенційного ключа відношення R.

· Жодна з множин атрибутів не збігається з усією множиною атрибутів відношення R.

Для зручності роботи сформулюємо це визначення так само й у негативній формі:

Визначення 7. Залежність з'єднання *(A, B, …, Z) називається тривіальною залежністю з'єднання, якщо виконується одна з умов:

· Або всі множини атрибутів A, B, …, Z містять потенційний ключ відношення R.

· Або одна з множин атрибутів збігається з усією множиною атрибутів відношення R.

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

Іншими словами, відношення знаходиться в нормальній формі проекції-з'єднання PJ/NF у тому і тільки в тому випадку, коли в кожній його повній декомпозиції всі проекції містять можливий ключ. (тобто. коли будь-яка залежність з'єднання в R випливає з існування деякого можливого ключа в R). Тобто відношення знаходиться в 5НФ тоді і тільки тоді, коли будь-яка залежність за з'єднанням в ньому визначається тільки його можливими ключами. Кожна проекція такого відношення містить не менш одного можливого ключа і не менш одного неключового атрибута

Визначення 5НФ може стати більш зрозумілим, якщо сформулювати його в негативній формі:

Визначення 9. Відношення R не знаходиться в 5НФ, якщо у відношенні знайдеться нетривіальна залежність з'єднання.

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

(i) Відношення R є цілком ключовим (тобто потенційним ключем відношення є вся множина атрибутів).

(ii) Є наступна залежність (досить дивна, із практичної точки зору): якщо у відношенні R містяться кортежі r₁=(x,y,z₁), r₂=(x,y₁,z) і r₃=(x₁,y,z), то звідси випливає, що у відношенні R міститься також і кортеж r=(x,y,z).

Твердження. Доведемо, що при наявності обмежень (і) і (ii), відношення знаходиться в 4НФ, але не в 5НФ.

Доведення. Покажемо, що відношення R знаходиться в 4НФ. Відповідно до визначення 4НФ, необхідно показати, що відношення знаходиться в НФБК і не містить нетривіальних багатозначних залежностей. Оскільки відношення є повністю ключовим, то воно автоматично знаходиться в НФБК.. Якби у відношенні була багатозначна залежність (необов'язково нетривіальна), то, відповідно до теореми Фейджина, відношення можна було б декомпонувати без утрат на дві проекції. Але приклад 3 показує, що таких декомпозицій немає (тут ми скористалися тим, що для доведення можливості декомпозиції необхідно довести її для всіх можливих станів відносини, а для доведення неможливості досить навести один контрприклад). Тому у відношенні немає ніяких багатозначних залежностей.

Покажемо, що відношення не знаходиться в 5НФ. Для цього потрібно навести приклад нетривіальної залежності з'єднання. Природним кандидатом на неї є *(XY, XZ, YZ). Якщо це дійсно залежність з'єднання, то вона нетривіальна. Дійсно, жодна з множин атрибутів XY, XZ і YZ не збігається з множиною всіх атрибутів відношення R і не містить потенційного ключа.

Але чи є така декомпозиція саме залежністю з'єднання? Для цього потрібно показати, що декомпозиція на три проекції R ₁=[ X,Y ], R ₂=[ X,Y ] і R ₃=[ X,Y ] є декомпозицією без утрат для будь-якого стану відношення R. Саме тут міститься ключова тонкість,, що пропускається звичайно при аналізі конкретного стану відношення R у прикладі 3, і саме тут нам знадобляться знання про предметну область, виражені у твердженні (ii)).

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

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

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

Ще один приклад. Приклад. Як приклад розглянемо відношення

Співробітники-Відділи-Проекти (Таб_номер, Від_номер, Проект_номер)

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

Тому відношення знаходиться в 4NF. Однак у ньому можуть існувати аномалії, які можна усунути шляхом декомпозиції в три відношення.

Уведемо наступні імена складених атрибутів:

СВ = {Таб_номер, Від_номер};

СП = {Таб_номер, Проект_номер};

ВП = {Від_номер, Проект_номер}.

Припустимо, що у відношенні Співробітники-Відділи-Проекти існує залежність з'єднання:

· (СВ, СП, ВП)

На прикладах легко показати, що при вставках і видаленнях кортежів можуть виникнути проблеми. Можливі аномалії при роботі з відношенням Співробітники-Відділи-Проекти можна усунути шляхом декомпозиції вихідного відношення в три нових відношення:

Співробітники-Відділи (Таб_номер, Від_номер);

Співробітники- Проекти (Таб_номер, Проект_номер);

Відділи-Проекти (Від_номер, Проект_номер).

Ці три відношення знаходитимуться у п'ятій нормальній формі. П'ята нормальна форма - це остання нормальна форма, яку можна одержати шляхом декомпозиції. Її умови досить нетривіальні, і на практиці 5NF використовується досить рідко (приклад – база даних ефектів, відношення Ефккти-Функції-Приклади).

Помітимо, що залежність з'єднання є узагальненням як багатозначної, так і функціональної залежностей.

4. Продовження алгоритму нормалізації (приведення до 5НФ)

У попередній лекції був описаний алгоритм нормалізації як алгоритм приведення відносин до 3НФ. Тепер ми можемо продовжити цей алгоритм, довівши його до алгоритму приведення до 5НФ.

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

Крок 5 (Приведення до 4НФ). Якщо у відношеннях виявлені нетривіальні багатозначні залежності, то необхідно провести декомпозицію для виключення таких залежностей.

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

Висновки

Узагальненням 3НФ на випадок, коли відношення має більш одного потенційного ключа, є нормальна форма Бойса-Кодда.

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

Нормалізація відношень аж до нормальної форми Бойса-Кодда ґрунтувалася на понятті функціональної залежності і теоремі Хеза, що гарантувала, що декомпозиція буде відбуватися без втрат інформації.

Подальша нормалізація зв'язана вже з узагальненням поняття функціональної залежності.

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

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

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

Багатозначна залежність X ®® Y | Z називається нетривіальною багатозначною залежністю, якщо не існує функціональних залежностей X ® Y і X ® Z.

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

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

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

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

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

⇐ Предыдущая 1 23

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