Подальша нормалізація: нормальні форми більш високого порядку

Багатозначна залежність І ЧЕТВЕРТА НОРМАЛЬНАЯ ФОРМА

Нехай дана змінна відносини нстх (де н скорочено позначає ієрархічний – hierarchic), що містить інформацію про курси навчання, викладачів і підручниках У цієї змінної відносини атрибути, що описують викладачів і підручники, приймають як значний відносини (Приклад значення НСТХ наведено на рис 131) Кожен кортеж змінної відносини НСТХ складається з атрибуту з назвами курсів (COURSE), a також атрибута-відносини з іменами викладачів (TEACHERS) і атрибута-відносини з назвами підручників (TEXTS) (на рис 131 показані два таких кортежу) Сенс кожного кортежу полягає в тому, що відповідний курс може читати будь-який з зазначених викладачів з використанням всіх зазначених підручників Припустимо, що для заданого курсу с може бути визначено довільну кількість відповідних викладачів m і підручників п (m> 0n п> 0) Більш того, припустимо, хоча цієї не зовсім реально, що викладачі і рекомендовані підручники абсолютно не повязані один з одним Це означає, що незалежно від того, хто викладає даний курс, завжди використовується один і той же набір підручників Нарешті, припустимо, що певний викладач або певний підручник може бути повязаний з будь-якою кількістю курсів

Нехай необхідно (як в розділі 126 глави 12) виключити атрибути, які беруть відносини в якості значень Один із способів виконання цього (але, можливо, не найкращий до цієї теми ми повернемося в Наприкінці даного розділу) полягає в простій заміні змінної відносини НСТХ змінної відносини СТХ з трьома скалярними атрибутами, COURSE, TEACHER і TEXT, як показано на рис 132 Як видно з цього малюнка, кожен кортеж початкової змінної відносини нстх породжує т * п кортежів у змінній відносини СТХ, де т і п є значеннями кардинальності для відносин TEACHERS і TEXTS в даному кортежі змінної відносини НСТХ Зверніть увагу на те, що всі атрибути результуючої змінної відносини СТХ входять до складу її ключа (на відміну від змінної відносини нстх, потенційний ключ якої {COURSE} складався з єдиного атрибута)

Вправа Складіть реляционное вираз, за ​​допомогою якого можна отримати змінну відносини СТХ з НСТХ

Рис 132 Набір значень даних у змінній відносини СТХ, еквівалентний

Рис 131 Приклад значень даних у змінній відносини НСТХ

наведеним на рис 131 наприклад значень даних у змінній відносини НСТХ

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

ЯКЩО кортежі (c, tl, xl) і (c, t 2, x 2) присутні одночасно,

ТО кортежі (с, t1, х2) і (с, t2, xl) також присутні одночасно

Очевидно, що змінна відносини СТХ характеризується значною надмірністю, а це, як зазвичай, призводить до деяких аномалій оновлення Наприклад, для додавання інформації про те, що курс фізики може читатися новим викладачем, необхідно вставити два окремих кортежу, по одному для кожного використовуваного підручника Як можна уникнути появи таких проблем Цілком очевидно, що зазначені проблеми викликані тим фактом, що дані про викладачів і підручниках повністю незалежні один від одного Крім того, легко виявити, що стан справ може бути покращено шляхом декомпозиції змінної відносини СТХ на дві її проекції (наприклад, з іменами ст і сх), відповідно, за атрибутами {COURSE, TEACHER} і

{COURSE, TEXT} (рис 133)

Рис 133 Значення даних змінних відносини СТ і СГ, які відповідають змісту змінної відносини СТХ, показаному на рис 132

Якщо база даних має проект, показаний на рис 133, то для додавання нової інформації про те, що курс фізики читатиметься новим викладачем, досить вставити єдиний кортеж в змінну відносини ст (Відзначимо також, що змінна відносини СТХ може бути відновлена ​​за рахунок зворотного зєднання проекцій ст і сх, і тому дана декомпозиція виконана без втрат) Таким чином, цілком розумно було б припустити, що для змінних відносини, подібних CTX, існує якийсь спосіб подальшої нормалізації.

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

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

“Проблеми, які повязані з змінними відносини в НФБК, подібними змінної відносини СТХ, були помічені досить давно, і способи їх дозволу

1 Мінлива відносини НСТХ також знаходиться в НФБК, а фактично вона додатково знаходиться і в 4НФ, і в 5НФ

(определенияэтихнормальныхформприведенынижевданнойглаве)

також були незабаром після цього визначено, принаймні, на інтуїтивному рівні Однак ці ідеї були сформульовані Фейгіна (Fagin) в строгому теоретичному вигляді з використанням поняття багатозначної залежності, абоМЗЗ, тільки в 1977 році [1314] Багатозначну залежність можна вважати узагальненням поняття функціональної залежності в тому сенсі, що кожна функціональна залежність є також багатозначною залежністю, але зворотне твердження невірно (оскільки існують багатозначні залежності, які не є функціональними) У разі змінної відносини СТХ мають місце дві наступні багатозначні залежності

COURSE →→  TEACHER COURSE  →→  TEXT

Зверніть увагу на подвійну стрілку, яка в багатозначною залежності А → → B означає, що в багатозначне залежить від А або А багатозначно визначає в Спочатку розглянемо першу з цих залежностей, COURSE → → TEACHER На інтуїтивному рівні вона означає, що, хоча для кожного курсу не існує одного відповідного тільки йому викладача, тобто НЕ виконується функціональна залежність COURSE → TEACHER, кожен курс має цілком певне безліч відповідних викладачів Якщо говорити точніше, під поняттям цілком певне безліч в нашому випадку мається на увазі, що для даного курсу с і даного підручника х безліч викладачів t, відповідне парі (з, х) змінної відносини СТХ, залежить тільки від значення с, оскільки не має значення, який саме підручник х буде обраний Друга багатозначна залежність, COURSE → → TEXT, має аналогічну інтерпретацію

Нижче наведено формальне визначення поняття багатозначної залежності

■&nbsp Багатозначна залежність Нехай R мінлива відносини, а А, в і з є довільними підмножинами безлічі атрибутів змінної відносини R Тоді підмножина в багатозначне залежить від підмножини А, що символічно виражається наступною записом

А → → У

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

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

А → → У | З

Для розглянутого прикладу подібний запис буде мати наступний вигляд

COURSE   →→ TEACHER   |   TEXT

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

залежність, в якій безліч залежних значень, відповідне заданому} значенню детермінанта, завжди є одноелементна безліччю Таким чином якщо А → в, то, безумовно, А → → В

Тепер, повертаючись до вихідної завданню із змінною відносини СТХ, можна відзначити наступне: описана раніше проблема з змінними відносини цього типу виникає через те, що вони містять багатозначні залежності, які не є функціональними (Слід зазначити зовсім неочевидний факт, що саме наявність таких МЗЗ вимагає вставки двох кортежів, коли необхідно додати відомості про новий викладача фізики Дані два кортежу необхідні для підтримки обмеження цілісності, представленого цієї МЗЗ) Проекції ст і сх не містять багатозначних залежностей, а тому вони дійсно представляють собою певне удосконалення вихідної структури Тому було б бажано замінити вихідну змінну відносини СТХ двома розглянутими проекціями Така дія буде правомочним відповідно до теореми Фейгіна [1314], яка наведена нижче

■&nbsp&nbsp&nbsp&nbsp Теорема Фейгіна Нехай А, В і С є множинами атрибутів змінної від носіння R {A, B, С} У такому випадку змінна відносини R дорівнюватиме соеди нению її проекцій за атрибутами {А, B} і {А, С} тоді і тільки тоді, коли для змінної відносини R виконується багатозначна залежність А → → B | C

(Зверніть увагу, що ця теорема є більш суворою версією теореми Хіта [124], яка описана в главі 12) Тепер, слідуючи роботі Фейгіна [1314], можна дати визначення четвертої нормальної форми (Ця нормальна форма отримала таку назву тому, що в момент її появи НФБК все ще вважалася третій нормальною формою, як зазначено в розділі 12)

■&nbsp&nbsp&nbsp&nbsp Четверта нормальна форма Мінлива відносини R знаходиться в четвертій нормальній формі (4НФ) тоді і тільки тоді, коли в разі існування таких підмножин А І В атрибутів цієї змінної відносини R, для яких справджується нетривіальна багатозначна залежність А → → в, всі атрибути змінної відносини R також функціонально залежать від атрибута А

Примітка Багатозначна залежність А → → в є тривіальною, якщо А є надбезліччю в або обєднання АВ атрибутів А І В становить весь заголовок

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

Мінлива відносини CTX чи не знаходиться в 4НФ, оскільки містить багатозначну залежність, яка взагалі не є функціональною, не кажучи вже про те, що остання повинна бути ще й функціональною залежністю від ключа Однак обидві її проекції, СТ і CX, знаходяться в 4НФ Отже, 4НФ забезпечує кращу структуру

даних у порівнянні з НФБК, оскільки дозволяє виключити деякі небажані залежності Крім того, в [1314] Фейгін показав, що 4НФ завжди є досяжною, тобто будь-яка змінна відносини може бути піддана декомпозиції без втрат в еквівалентний набір змінних відносини в 4НФ Однак, як показано в розділі 125 глави 12 на прикладі змінної відносини SJT, така декомпозиція (або навіть декомпозиція до НФБК) не завжди виявляється корисною і потрібною

Слід зазначити, що хоча ідеї Ріссанен (Rissanen), викладені в присвяченій незалежним проекціям роботі [126], сформульовані з використанням функціональних залежностей, вони також справедливі в відношенні багатозначних залежностей Нагадаємо, що відповідно до цими ідеями, змінну відносини

R {A, B, C}, що задовольняє функціональним залежностям А –&gt B і B –&gt C, Бажано розбивати на проекції по атрибутах {А, B} і {В, С}, а не на проекції по атрибутах {А, B} і {А, С} Це твердження також буде вірно, якщо замість функціональних залежностей А → B і B → з використовувати багатозначні залежності А → → В і В → → С

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

значеннями у вигляді відносин, або скорочено АТ (атрибутів-відносин) Суть в тому,

що якщо доводиться мати справу з змінної відносини зразок НСТХ, яка включає один або кілька незалежних АТ, то замість простої заміни цих АТ

скалярними атрибутами (як було зроблено на початку даного розділу), а потім виконання декомпозиції без втрат отриманого результату, краще спочатку розділити ці АТ Наприклад, у випадку змінної відносини НСТХ насамперед варто замінити вихідну змінну відносини двома її проекціями немає {COURSE, TEACHERS} і

НСХ {COURSE, TEXTS}, де атрибути TEACHERS і TEXTS все ще відносяться до типу АТ Далі ці АТ можна буде виключити з двох отриманих проекцій (з приведенням їх до НФБК, а фактично до 4НФ) звичайним способом, і тоді проблема, властива знаходиться в НФБК змінної відносини CTX, просто ніколи не виникне Як бачите, поняття багатозначних залежностей і 4НФ надають формальне обгрунтування тих способів удосконалення проекту, які в іншому випадку були б

засновані виключно на емпіричних правилах

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

*

*