ЗАМИКАННЯ МНОЖИНИ АТРИБУТІВ

В принципі, замикання S + для заданої множини функціональних залежностей S можна обчислити за допомогою наступного алгоритму: Повторно застосовувати правила з попереднього розділу доти, поки залишається можливим створення нових функціональних залежностей . Але на практиці рідко потрібно обчислити замикання як таке, а тому і тільки що згаданий алгоритм навряд чи буде достатньо ефективним Однак з цього розділу ви дізнаєтеся, як можна обчислити деяку підмножину замикання, а саме те підмножина, яке складається з усіх функціональних залежностей з деяким (зазначеним) безліччю z атрибутів, розташованих у лівій частині виразу залежності Точніше кажучи, ми покажемо, що для заданої змінної відносини R, заданої множини атрибутів цієї змінної відносини z і заданої множини функціональних залежностей S, що виконуються для змінної

Глава 11 Функціональні залежності445 відносини R, можна знайти множество3 всіх атрибутів змінної відносини R, які функціонально залежні від Z, тобто так зване замикання Z + безлічі Z в межах S Простий алгоритм обчислення цього замикання показаний на рис 112 Вправа Доведіть правильність цього алгоритму

Рис 112 Обчислення замикання Z + безлічі Z в межах S

Приклад Припустимо, що дана змінна відношення R з атрибутами А, В, С, D, Е і

F і наступними функціональними залежностями

А → НД

Е → CF В → Е CD → EF

Обчислимо замикання {А, В} + безлічі атрибутів {А, В} виходячи із заданої множини функціональних залежностей

9 Привласнимо замикання CLOSURE [Z, S] початкове значення – безліч

{А, В}

10 Виконаємо внутрішній цикл чотири рази – по одному разу для кожної заданої функціональної залежності Після першої ітерації (для залежності А → НД) буде виявлено, що ліва частина дійсно є підмножиною замикання CLOSURE [Z, S] Таким чином, до результату можна додати атрибути B і C Тепер замикання CLOSURE

[Z, S] являє собою безліч {А, В, С}

11 Після другої ітерації (для залежності Е → CF) виявляється, що ліва частина НЕ є підмножиною отриманого до цього моменту результату, який, таким чином, залишається незмінним

12 Після третьої ітерації (для залежності В → Е) до замикання CLOSURE

[Z, S] буде додано безліч Е, тому замикання тепер матиме вигляд {А, B, С, Е}

13 Після четвертої ітерації (для залежності CD → EF) замикання CLOSURE [Z, S] залишиться незмінним

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

14 Далі внутрішній цикл виконується ще чотири рази Після першої ітерації ре зультат залишиться колишнім, після другої він буде розширений до {A, B, C, E, F}, a після третьої та четвертої – знову не зміниться

15 Нарешті, після ще одного чотириразового проходження циклу замикання

CLOSURE [Z, S] залишиться незмінним і весь процес завершиться з результатом

{А, В} + = {A, B, C, E, F}

Слід зазначити, що якщо Z (як було вказано вище) – безліч атрибутів змінної відносини R, a S – безліч функціональних залежностей, які дотримуються в R, то безліч функціональних залежностей, які дотримуються в R і містять z в лівій частині, являє собою безліч, що складається з усіх функціональних залежностей у формі Z → Z , де Z – деяка підмножина замикання Z + безлічі z, що належить до S У такому випадку замикання S + первісного безлічі функціональних залежностей S являє собою обєднання всіх подібних множин функціональних залежностей, узятих по всім множинам атрибутів Z

Зі сказаного вище можна зробити дуже важливий висновок: для заданої множини функціональних залежностей S легко можна вказати, чи буде задана функціональна залежність х → Y слідувати з S, оскільки це можливо тоді і тільки тоді, коли безліч Y є підмножиною замикання х + безлічі X для заданої множини s Інакше кажучи, таким чином може бути створений простий спосіб визначення того, чи буде дана функціональна залежність х → Y включена в замикання S + безлічі S, практично не повязаний з необхідністю обчислення самого цього замикання S +

Ще одне важливе висновок грунтується на наступному факті Насамперед, згадаємо визначення поняття суперключа з глави 9 Суперключ змінної відношення R – це безліч атрибутів змінної відношення R, яке у вигляді підмножини (але не обовязково суворого підмножини) містить принаймні один потенційний ключ З цього визначення безпосередньо випливає, що суперключі для даної змінної відношення R – це такі підмножини до безлічі атрибутів змінної відношення R, що функціональна залежність

К → А

дотримується для кожного атрибута А змінної відносини R Іншими словами, безліч до є суперключом тоді і тільки тоді, коли замикання до + для безлічі до в межах заданої множини функціональних залежностей є безліччю абсолютно всіх атрибутів змінної відносини R (Крім того, безліч до є потенційним ключем тоді і тільки тоді, коли воно є непріводімим суперключом)

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

*

*