НОРМАЛЬНАЯ ФОРМА Бойса-Кодда

У цьому розділі ми скасуємо применявшееся вище допущення про те, що кожна змінна відносини має тільки один потенційний ключ (а саме-первинний ключ), і розглянемо більш загальний випадок Справа в тому, що первинне визначення, дане Коддом для ЗНФ [116], не у всіх випадках виявляється задовільним Зокрема, воно неадекватно при виконанні наступних умов, що стосуються певної змінної відносини:

4 змінна відносини має два (або більше) потенційних ключа, таких, що

5 ці потенційні ключі є складовими і

6 два або більше потенційних ключів перекриваються (тобто мають принаймні один спільний атрибут)

Тому згодом вихідне визначення ЗНФ було замінено більш строгим визначенням Бойса-Кодда (Воусе-Codd) [122] А оскільки це нове визначення фактично задає нормальну форму, яка під усіх відношеннях сильніший у порівнянні зі старою ЗНФ, для неї було встановлено власне названіе10 – нормальна форма Бойса-Кодда (Або НФБК)

Примітка Комбінація умов 1-3 на практиці зустрічається не часто Для будь-якої змінної відносини, в якій не виконуються всі ці три умови, ЗНФ і НФБК повністю еквівалентні

Для пояснення концепції НФБК необхідно знову скористатися поняттям детермінанта, введенням в главі 11 для позначення лівій частині деякої функціональної залежності, а також поняттямтривіальної функціональної залежності,

яке позначає таку ФЗ, ліва частина якої є надбезліччю правій частині Дамо визначення НФБК

10 Насправді суворе визначення третьої нормальної форми, еквівалентну визначенням нормальної форми Бойса-Кодда, вперше було дано Хітом (Heath) в 1971 році [114], тому дану форму слід було б називати нормальною формою Хіта.

■&nbsp&nbsp&nbsp&nbsp&nbsp Нормальна форма Бойса-Кодца Мінлива відносини знаходиться в нормальній формі Бойса-Кодда тоді і тільки тоді, коли кожна її нетривіальна і Непріводімие зліва функціональна залежність має в якості свого детермінанта деякий потенційний ключ

Можна дати й інший, менш формальний варіант цього визначення

■&nbsp Нормальна форма Бойса-Кодда {Неформальне визначення) Мінлива відносини знаходиться в нормальній формі Бойса-Кодда тоді і тільки тоді, коли детермінанти всіх її ФЗ є потенційними ключами

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

Примітка Різниця між двома наведеними визначеннями НФБК полягає в тому, що в менш формальному з них неявно мається на увазі, що детермінанти не надто великі і все ФЗ нетривіальні Для простоти викладу далі в цьому розділі будуть використані такі ж допущення, за винятком особливо обумовлених випадків

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

Перш ніж розглядати приклади змінних відносини з декількома потенційними ключами, покажемо, що змінні відносини FIRST і SECOND, які не перебувають у ЗНФ, не перебувають також у НФБК Крім того, покажемо, що змінні відносини SP, SC і CS, які знаходяться в ЗНФ, знаходяться також у НФБК Мінлива відносини FIRST містить три детермінанта, а саме – S #, CITY і {S #, Р #}, з яких тільки {S #, P #} є її потенційним ключем Тому змінна

відносини FIRST чи не знаходиться в НФБК Аналогічне твердження вірне для змінної відносини SECOND, оскільки детермінант CITY не є її потенційним ключем З іншого боку, змінні відносини SP, SC і CS знаходяться в НФБК, оскільки в кожному випадку єдиний потенційний ключ є єдиним детерминантом для даної змінної відносини

Тепер розглянемо приклад, що містить два окремих (тобто неперекривающіхся)

потенційних ключа Припустимо, що у змінній відносини постачальників S {S #, SNAME, STATUS, CITY} безлічі атрибутів {S #} і {SNAME} є її потенційними ключами (тобто в цьому випадку кожен постачальник має унікальний номер і унікальне імя) Також припустимо (як, втім, і всюди в цій книзі), що атрибути STATUS і CITY є взаємно незалежними, тобто введена вище просто для розкриття теми розділу 123 функціональна залежність CITY → STATUS більше не дотримується Тоді діаграма функціональних залежностей буде мати вигляд, представлений на рис 1212

Рис 1212 Діаграма функціональних залежностей у змінній відносини S для випадку, ко: гда безліч атрибутів {SNAME} є її потенційним ключем (і залежність CITY-&gt STATUS не виконується)

Можна бачити, що змінна відносини S знаходиться в НФБК Хоча її діаграма ФЗ істотно складніше діаграми ФЗ для змінної відносини в ЗНФ, в цьому випадку всі детермінанти є потенційними ключами, оскільки всі стрілки починаються з потенційних ключів Таким чином, з даного прикладу можна зробити висновок, що наявність декількох потенційних ключів не обовязково має розглядатися як ознака поганого проекту

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

Примітка Відповідно з доводами, які наводилися в главі 9, в прикладах цієї глави з наявних потенційних ключів первинний ключ вибиратися не буде Тому в представлених нижче таблицях ніякі стовпці НЕ будуть позначатися за допомогою подвійної лінії

У першому прикладі знову приймемо припущення, що імена постачальників унікальні,

і розглянемо змінну відносини

SSP   {   S#,    SNAME,    P#,   QTY   }

Потенційними ключами в ній є безлічі атрибутів {S #, P #} і

{SNAME, P #} Однак ця змінна відношення не знаходиться в НФБК, так як вона містить два детермінанта, s # і SNAME, які не є її потенційними ключами (і {S #}, і {SNAME}-детермінанти, оскільки вони визначають один одного) Приклад значення змінної відносини SSP показаний на рис 1213

Рис 1213 Приклад значення змінної відносини SSP (показаний не повністю)

Згідно цього малюнку, змінної відносини SSP властива деяка частка надмірності, як і змінним відносини FIRST І SECOND (CM розділ 123), а також змінної відносини SCP (див розділ 121), тому при її використанні виникають такі ж проблеми, які були характерними для останніх Наприклад, для зміни імені постачальника, що має номер S1, зі Smith на Robinson необхідно знайти

всі відносяться до нього кортежі, оскільки в іншому випадку база даних перейде в суперечливий стан Проте, змінна відносини SSP знаходиться в ЗНФ, оскільки згідно зі старим визначенням не вимагається, щоб атрибут був неприводимого залежимо від кожного потенційного ключа, якщо він сам є компонентом деякого потенційного ключа даної змінної відносини В результаті той факт, що атрибут SNAME приводиться залежимо від атрибутів {S #, Р #}, даним визначенням ігнорується

Примітка Під терміном ЗНФ тут мається на увазі визначення, дане Коддом в [116], а не спрощене визначення, дане нами в розділі 123

Для вирішення зазначеної проблеми змінну відносини SSP слід розбити на дві проекції, як показано нижче

SS  {  S#,   SNAME

} SP   {   S#,    P#, QTY   }

Проте можна вибрати і альтернативний варіант розбиття

SS  {  S#,   SNAME  }

SP  {  SNAME,   P#,   QTY  }

Зверніть увагу, що в цьому прикладі показані два варіанти декомпозиції, і обидва вони в рівній мірі є допустимими, оскільки всі вхідні в них проекції знаходяться в НФБК

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

принципами повинен керуватися розробник, віддаючи перевагу варіанту з

змінними відносини SS і SP, а не варіанту з змінної відносини SSP

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

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

Розглянемо змінну відносини SJT з атрибутами s, J і т, які позначають, відповідно, студента, досліджуваний предмет і викладача Сенс кожного кортежу (s, j, t) змінної відносини SJT (в скороченою системі позначень) полягає в тому, що деякий студент s вивчає деякий предмет j на лекціях деякого викладача t При цьому на інформацію накладаються наступні два обмеження

■ Кожен студент вивчає певний предмет тільки у одного викладача

■ Кожен викладач веде тільки один предмет, але кожен предмет ведуть не скільки викладачів

На рис 1214 показаний приклад значення змінної відносини SJT

Рис 1214 Приклад значення змінної відносини SJT

Які функціональні залежності існують в цій змінній стосунки З першого обмеження слід функціональна залежність {S, J} → т, а з другого – функціональна залежність Т → J Нарешті, сам факт, що кожен предмет ведуть кілька викладачів, говорить про те, що функціональна залежність J → т не дотримується Отже, діаграма функціональних залежностей змінної відносини SJT буде мати вигляд, представлений на рис 1215

Рис 1215 Діаграма функціональних залежностей у змінній відносини SJT

І знову в розглянутому прикладі присутні два перекриваються потенційних ключа, а саме безліч атрибутів {S, J} і безліч атрибутів {S, Т} Як і в першому прикладі, вихідна змінна відносини SJT знаходиться в ЗНФ, але не в НФБК, у звязку з чим для неї будуть характерні деякі аномалії оновлення Наприклад, якщо буде потрібно видалити відомості про те, що студент Джонс (Jones) вивчає фізику, цього не можна буде зробити, не втративши одночасно інформацію про те, що професор Браун (Prof Brown) викладає цей предмет Подібні труднощі викликані тим, що атрибут т є детермінантою, але не є потенційним ключем І знову для вирішення зазначеної проблеми вихідну змінну відносини SJT слід розбити на дві проекції, кожна з яких буде знаходитися в НФБК

ST {S, Т}

TJ {Т, J}

Пропонуємо читачеві як вправа визначити значення цих двох змінних відносини (які відповідають даним, представленим на рис 1214), намалювати для перевірки відповідну діаграму ФЗ, довести, що ці дві новостворені проекції знаходяться в НФБК (поясніть, які атрибути є їх потенційними ключами), і перевірити, чи дійсно така декомпозиція дозволяє усунути всі аномалії оновлення

Однак слід зазначити, що все ще існує інша проблема Суть її в тому, що декомпозиція вихідного відносини на проекції ST і TJ дозволяє виключити одні аномалії, але призводить до появи інших Причиною є той факт, що проекції ST і TJ не є незалежними в тому сенсі, який був вказаний Ріссаненом (див розділ 124) Точніше кажучи, функціональна залежність

{S, J} → Т

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

Т → J

В результаті дві отримані проекції не можуть оновлюватися незалежно Наприклад, спроба вставити в змінну відносини ST кортеж для студента Сміта (Smith) і професора Брауна (Prof Brown) повинна бути відкинута системою, оскільки професор Браун викладає фізику, а Сміт вже навчається фізики у професора Гріна (Prof Green) Однак система не може виявити цей факт, не перевіривши вміст змінної відносини TJ Таким чином, ми прийшли до неприємного висновку про те, що спроба досягнення двох цілей (а саме декомпозиції початкової змінної відносини на змінні відносини, що знаходяться в НФБК, і декомпозиції початкової змінної відносини на незалежні компоненти) у деяких випадках може призвести до конфліктної ситуації Тому досягти обох цілей одночасно не завжди можливо

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

В якості третього і останнього прикладу змінної відносини з перекриваються потенційними ключами розглянемо змінну відносини EXAM з атрибутами S (студент), J (предмет) і Р (позиція) Кожен кортеж (S, j, р) змінної відносини EXAM відображає відомості про те, що деякий студент s екзаменує з певного предмету j і займає певну позицію р в екзаменаційній відомості Додатково домовимося, що в нашому прикладі має місце такі обмеження

■ Ніякі два студенти не можуть займати одну і ту ж позицію в екзаменаційній відомості, яка відноситься до одного й того ж предмету

У цьому випадку діаграма функціональних залежностей буде мати вигляд, представлений на рис 1216

Рис 1216 Діаграма функціональних залежностей у змінній відносини

EXAM

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

{S, J} H {J, P}, оскільки для кожного студента і предмета існує точно одна займана позиція у відповідному списку, а в кожному списку екзаменуються по деякому предмету кожну позицію займає тільки один відповідний студент

Однак така змінна відносини знаходиться в НФБК, оскільки зазначені потенційні ключі є її єдиними детермінантами Тому для даної змінної відношення не характерні будь аномалії оновлення, подібні згадуваним раніше в цій главі {ВправаПеревірте правильність цього твердження) Таким чином, наявність перекриваються потенційних ключів не завжди призводить до появи проблем подібного роду

На закінчення слід підкреслити, що концепція НФБК дозволяє позбутися

проблем, які притаманні формам, відповідним старому визначенню ЗНФ Більш того, нове визначення концептуально простіше старого, так як в ньому не використовуються поняття 1НФ, 2НФ, первинного ключа або транзитивної залежності Додатково поняття потенційного ключа може бути замінено посиланням на більш фундаментальне поняття функціональної залежності (у визначенні, даному в [122], має

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

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

бути піддана декомпозиції без втрат на безліч D проекцій НФБК (але при цьому не обовязково зберігаються всі залежності)

1 Ініціалізувати безліч D так, щоб у ньому містилася тільки змінна відносини R

2 Для кожної змінної відносини т з безлічі D, яка не знаходиться в НФБК,

виконати кроки 3 і 4

3 Нехай X –&gt Y є функціональною залежністю для т, яка порушує вимоги НФБК

4 Замінити змінну відносини т з безлічі D двома її проекціями: по ат рібутам X і Y і по всіх атрибутів, крім тих, що знаходяться BY

Джерело: Дейт К Дж, Введення в системи баз даних, 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>

*

*