ЗАЛЕЖНО З’ЄДНАННЯ І П’ЯТА НОРМАЛЬНАЯ ФОРМА

До цих пір в цій главі і протягом всієї попередньої глави за замовчуванням передбачалося, що єдиною необхідною або допустимої операцією в процесі нормалізації є заміна змінної відносини за правилами декомпозиції без втрат точно двома її проекціями Таке припущення нас цілком влаштовувало, поки мова не йшла про 4НФ Однак, хоча це може здатися дивним, існують змінні відносини, для яких не можна виконати декомпозицію без втрат на дві проекції, але які можна піддати декомпозиції без втрат на три або більшу кількість проекцій Подібні змінні відносини позначимо не дуже вдалим, але досить зручним терміном n-декомпонуемая мінлива відносини, або відношення . Таку назву застосовується до змінної відносини, якщо можна виконати її декомпозицію без втрат нап проекцій, але не наш проекцій, де 1 < m і m < п.

Примітка Вперше можливість n-декомпонуемості для п> 2 була згадана в роботі Ахо (Aho), Бери (Beeri) і Ульмана (Ullman) [131], а окремий випадок для п = 3 був описаний Ніколасом (Nicolas) [1326]

Як приклад розглянемо змінну відносини SPJ з бази даних постачальників, деталей і проектів, представлену на рис 134 (в цілях спрощення атрибут QTY виключений) Зверніть увагу на те, що ця змінна відносини складається тільки з

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

1 Три бінарні проекції (SP, PJ і JS), відповідні значенням відносини

SPJ, показаному в верхній частині малюнка

2 Результат зєднання проекцій SP і PJ ПО атрибуту р #

3 Результат зєднання цього результату з проекцією JS по комбінації атрибутів

J # І S #

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

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

Вправа Пропонуємо читачеві перевірити це твердження

Далі відзначимо, що представлений на рис 134 приклад, безумовно, виражений в термінах відносин, а не змінних відносини Проте 3-декомпонуемость змінної відносини SPJ може бути більш фундаментальною і не залежним від часу властивістю (тобто властивістю, яке дотримується при всіх допустимих значеннях даної змінної відносини), якщо дана змінна відносини задовольняє визначеним, який не залежить від часу обмеження цілісності Для того щоб зрозуміти, яким саме має бути це обмеження, насамперед відзначимо, що затвердження змінна відносини SPJ дорівнює зєднанню трьох своїх проекцій SP, PJ

і JS , повністю еквівалентно наступного твердження:

■ якщо пара (s 1, p1) присутня в SP і пари (р1, j1) присутня в PJ, а пара (jl, s1) присутня в JS,

■ то трійка (s 1, p1, jl) присутня в SPJ

Це вірно, оскільки очевидно, що трійка (s1, p1, j1) обовязково присутній в зєднанні проекцій SP, PJ і JS (Слід зазначити, що зворотне твердження, тобто якщо трійка (s1, p1, jl) присутній у змінній відносини SPJ, то, наприклад, пара (s1, p1) присутня в проекції SP, є істинним для будь-якої змінної відносини SPJ ступеня три) Оскільки пара (s 1, p1) присутній у відношенні SP тоді і тільки тоді, коли трійка (s 1, p1, j 2) присутній у відношенні SPJ для

деякого значення j2 (аналогічно для (p1, jl) і (jl, s1)), наведене вище твердження можна переписати у вигляді наступного обмеження, що накладається на змінну відносини SPJ:

■ якщо кортежі (s1, p1, j 2), (s 2, p1, jl), (sl, p2, jl) присутні в SPJ,

■ то кортеж (s 1, pi, j 1) також присутній в SP J

Якщо це твердження виконується завжди, тобто для всіх допустимих значень змінної відносини SPJ, то буде отримано не залежне від часу (хоча й трохи дивне) обмеження для даної змінної відносини Зверніть увагу на циклічний характер цього обмеження (якщо значення s1 повязано з p1 і p1 повязано з j 1, a j 1 повязано знову cs l, то sl, pl і jl повинні знаходитися в одному кортежі ) Мінлива відносини буде п-декомпонуемой для п> 2 тоді і тільки тоді, коли вона задовольняє деякому подібного циклічного обмеженню (багатостороннім, з кількістю учасників п)

Рис 134 Приклад значення змінної відносини SPJ, яка може бути отримана тільки в результаті зєднання всіх трьох її бінарних проекцій, але не л юбих двох з них

До кінця цього розділу керуватимемося припущенням, що змінна відносини SPJ дійсно задовольняє цій котра не залежить від часу обмеження (представлений на рис 134 приклад даних відповідає такої гіпотези) Таке обмеження будемо коротко називати обмеженням 3-Д (Скорочення від 3-декомпонуемості) Що означає обмеження 3-Д з практичної точки зору Для отримання відповіді на це питання розглянемо приклад, в якому під такими обмеженнями мається на увазі, що якщо в реальному світі для змінної відносини SP J вірні такі твердження:

а)якщо Сміт поставляє гайкові ключі

б) гайкові ключі використовуються в Манхеттенському проекті в) Сміт є постачальником для Манхеттенського проекту то

г) Сміт поставляє гайкові ключі для Манхеттенського проекту

Зверніть увагу на те, що (як уже згадувалося в розділі 1, розділ 13) з узятих в сукупності тверджень а, б і в зазвичай НЕ випливає твердження м Дійсно, точно такий же приклад був розглянутий у розділі 1 для демонстрації дефекту зєднання. Проте в даному окремому випадку слід зазначити, що ніякого дефекту тут не виникає, оскільки існує додаткове практичне обмеження 3-Д, що має місце в реальному світі, завдяки чому висновок затвердження г на основі тверджень а, бів є цілком правомочним

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

■&nbsp&nbsp Залежність зєднання Нехай R-змінна відносини, а А, B, .., Z – довільні підмножини безлічі її атрибутів Мінлива відносини R задовольняє наступній Залежно зєднання

* {А, В, .., Z}

(Читається зірочка А, в, .., Z) тоді і тільки тоді, коли будь-яке допустиме значення змінної відносини R еквівалентно зєднанню її проекцій по підмножини А, в, .., z безлічі атрибутів

Наприклад, якщо використовувати скорочену символьну запис SP для підмножини

{S #, Р #} безлічі атрибутів змінної відносини SPJ і аналогічно використовувати скорочення PJ і JS для двох інших підмножин, то змінна відносини SPJ задовольнятиме залежності зєднання * {SP, Р J, JS}, якщо дотримується обмеження 3-Д

В якості ще одного прикладу розглянемо звичайну змінну відносини S

Якщо прийнято угоду про використання скорочення SN для позначення підмножини {S #, SNAME} безлічі атрибутів S і аналогічну угоду для ST і SC, то можна сказати, що змінна відносини S задовольняє Залежно зєднання * {SN, ST, SC}

Звідси ясно, що змінна відносини SPJ із залежністю зєднання

* {SP, PJ, JS} може бути 3-декомпонуемой Однак виникає питання,чи слід виконувати таку декомпозицію По всій видимості, слід, так як у звязку з наявністю залежності зєднання мінлива відносини SPJ характеризується численними аномаліями оновлення, які можна усунути лише за допомогою її 3декомпозіціі Деякі приклади подібних аномалій показані на рис 135 Пропонуємо читачам як вправа самостійно відповісти на питання, що станеться після виконання 3-декомпозиції

Рис 135 Приклади аномалій оновлення в змінної відносини SPJ

Теорема Фейгіна (яка розглядалася в розділі 132) говорить, що змінна відношення R {A, в, С} може бути декомпонована без втрат на проекції по атрибутах {А, В} і {А, с} тоді і тільки тоді, коли для змінної відносини R виконуються багатозначні залежності А → → В і А → → С

Тепер теорема Фейгіна може бути сформульована інакше, як показано нижче

■ Мінлива відносини R {A, в, С} задовольняє залежності зєднання

* {АВ, АС} тоді і тільки тоді, коли вона задовольняє багатозначної залежності А → → B | C

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

Формально отримаємо наступний результат

А → → У | З≡   * {АВ, АС}

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

Повертаючись до розглянутого прикладу, можна відзначити, що проблема, повязана з використанням змінної відносини SPJ, полягає в тому, що вона підпорядковується залежності зєднання, яка не є багатозначною залежністю, і тому також не є функціональною {Вправа Поясніть, чому така ситуація розглядається як проблема) Можна також зауважити, що можливо (і навіть бажано) декомпоновать таку змінну відносини на менші компоненти, а саме – на проекції, що визначаються залежністю зєднання Даний процес декомпозиції

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

знаходитися в пятій нормальній формі Дамо визначення цієї нормальної форми

■&nbsp Пята нормальна форма Мінлива відносини R знаходиться в пятої нормально »формі (5НФ), яку іноді інакше називають проекційно-сполучної нормальною формою (ПСНФ), тоді і тільки тоді, коли кожна нетривіальна залежність зєднання в змінної відносини R визначається потенційним ключем (ключами) R, якщо дотримуються наведені нижче умови

а) Залежність зєднання * {А, в, .., z} у змінній відносини R яв ляется тривіальної тоді і тільки тоді, коли принаймні одне з під множин А, в, .., z безлічі атрибутів є множиною всіх атрі бутов R

б) Залежність зєднання * {А, в, .., Z} у змінній відносини R оп ределяется потенційним ключем (ключами) R тоді і тільки тоді, коли каж

дое з підмножин А, B, .., Z безлічі атрибутів є суперключом

для R

Мінлива відносини SPJ чи не знаходиться в 5НФ Вона задовольняє деякій залежності зєднання, а саме – обмеження 3-Д, яке, безумовно, не визначається її єдиним потенційним ключем (цей ключ є комбінацією всіх її атрибутів) Інакше кажучи, змінна відносини SPJ чи не знаходиться в 5НФ, оскільки вона може бути 3-декомпонована і можливість такої декомпозиції НЕ обумовлена ​​тим фактом, що комбінація атрибутів {s #, P #, J #} є її потенційним ключем Навпаки, після 3-декомпозиції три проекції SP, PJ і JS знаходяться в 5НФ, оскільки в них взагалі немає нетривіальних залежностей зєднання

Зверніть увагу на той факт, що будь-яка змінна відносини в 5НФ безумовно знаходиться також в 4НФ, оскільки багатозначна залежність є окремим випадком

Залежно зєднання Дійсно, Фейгін в [1315] показав, що будь-яка багатозначна залежність, обумовлена ​​потенційним ключем, насправді повинна бути функціональною залежністю, в якій потенційний ключ є детермінантою У тій же роботі Фейгін показав, що будь-яка змінна відносини може бути піддана декомпозиції без втрат на еквівалентний набір змінних відносини в 5НФ, тобто 5НФ завжди досяжна

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

*{    {   S#,    SNAME,    STATUS   },    {   S#,    CITY   }    }

Це означає, що змінна відносини S еквівалентна зєднанню її проекцій за атрибутами {S #, SNAME, STATUS} і {S #, CITY} Тому вона може бути піддана декомпозиції без втрат на зазначені проекції (Цей факт означає не те, що вона повинна піддаватися подібної декомпозиції, а тільки те, що може бути їй піддана) Існування даної залежності зєднання передбачається на підставі того факту, що атрибут {S #} є потенційним ключем даної змінної відносини (насправді, це випливає з теореми Хіта [124])

Тепер припустимо (як було зроблено в розділі 125 глави 12), що змінна відносини S має другий потенційний ключ, {SNAME} У такому випадку існує ще одна залежність зєднання, яка задовольняється цієї змінної відносини, як показано нижче

*{ { S#, SNAME }, { S#, STATUS }, { SNAME, CITY } }

Існування цієї залежності зєднання обумовлено тим фактом, що обидва атрибута, {S #} і {SNAME}, є потенційними ключами

Як випливає з наведених вище прикладів, задана залежність зєднання * {А, В, .., Z} визначається потенційними ключами тоді і тільки тоді, коли кожна підмножина А, B, .., Z безлічі атрибутів фактично є суперключом для даної змінної відносиниТаким чином, щодо заданої змінної відносини R можна стверджувати, що вона знаходиться в 5НФ, тільки за умови, що відомі всі її потенційні ключі і всі залежності зєднання, існуючі в ній Але сама по собі завдання визначення всіх подібних залежностей зєднання може виявитися дуже складною Це означає, що можна відносно легко визначити функціональні та багатозначні залежності (оскільки вони мають досить просту інтерпретацію в реальному світі), але цього не можна стверджувати стосовно залежностям зєднання (тобто до таких залежностям зєднання, які не є багатозначними і тому функціональними залежностями), оскільки інтуїтивний сенс залежностей зєднання не завжди буває очевидним Отже, процедура визначення того, що деяка змінна відносини все ще перебуває в 4НФ, а не в 5НФ, і, таким чином, існує можливість її подальшої вигідною декомпозиції, все ще залишається не цілком ясною Проте, як випливає з досвіду, подібні змінні відносини досить рідко зустрічаються на практиці

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

Джерело: Дейт К Дж, Введення в системи баз даних, 8-е видання: Пер з англ – М: Видавничий дім «Вільямс», 2005 – 1328 с: Ил – Парал тит англ

Схожі статті:


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

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*