Непріводімие МНОЖИНИ ЗАЛЕЖНОСТЕЙ

Нехай S1 і S2 – два безлічі функціональних залежностей Якщо будь-яка функціональна залежність, яка випливає з безлічі залежностей si, слід також з безлічі залежностей S2 (тобто якщо замикання S1 + є підмножиною замикання S2 +,

то безліч S2 називається покритіем4 для безлічі si Це означає, що якщо СУБД забезпечить дотримання обмежень, представлених залежностями безлічі S2, то автоматично будуть дотримані і всі обмеження, що встановлюються залежностями безлічі S1

Далі, якщо безліч S2 є покриттям для безлічі S1, а безліч S1 одночасно є покриттям для безлічі S2 (тобто якщо S1 + = S2 +), то безлічі S1 і S2 еквівалентні Ясно, що якщо безлічі S1 і S2 еквівалентні, то дотримання СУБД обмежень, представлених залежностями безлічі S2, автоматично забезпечить дотримання обмежень, представлених залежностями безлічі S1, і навпаки

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

16 Права (залежна) частина кожної функціональної залежності з безлічі S

містить тільки один атрибут (тобто є одноелементна безліччю)

17 Ліва частина (детермінант) кожної функціональної залежності з безлічі S, в свою чергу, є не приводиться, тобто жоден атрибут з детермінанта не може бути опущений без зміни замикання S + (без перетворення безлічі S в якесь інше безліч, що не еквівалентне безлічі S) У цьому випадку функціональна залежність називається приводиться зліва

18 Жодна функціональна залежність з безлічі S не може бути видалена з безлічі s без зміни його замикання S + (тобто без перетворення безлічі s в деякий інше безліч, не еквівалентні безлічі S)

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

Р # → PNAME

Р # → COLOR

Р # → WEIGHT

Р # → CITY

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

1 Р # → {PNAME, COLOR}

Р # → WEIGHT

Р # → CITY

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

(Це поняття також буде скоро визначено в даній книзі)

5 У літературі подібне безліч часто називається мінімальним

(Права частина першої ФЗ не є одноелементна безліччю)

2 {Р #, PNAME} → COLOR

Р # → PNAME

Р # → WEIGHT

Р # → CITY

(Першу ФЗ можна спростити, виключивши атрибут PNAME У лівій частині без зміни замикання, тобто вона не є приводиться зліва)

3 р # → р # Р # → PNAME Р # → COLOR Р # → WEIGHT Р # → CITY

(Тут першу ФЗ можна виключити без зміни замикання)

Тепер можна сформулювати твердження, що для будь-якого безлічі функціональних залежностей існує принаймні одне еквівалентне безліч, яке є непріводімим Це можна довести досить легко Нехай дано вихідна безліч залежностей s Тоді в силу того, що існує правило декомпозиції, можна без втрати спільності припустити, що кожна функціональна залежність в цій множині s має одноелементна праву частину Далі для кожної залежності f з цієї множини S слід перевірити кожен атрибут А в лівій частині залежності f Якщо видалення атрибута А з лівої частини залежності f не призводить до зміни замикання S +, то цей атрибут слід видалити Потім для кожної залежності f, що залишилася в безлічі s, необхідно перевірити, чи призводить її видалення з безлічі S до зміни замикання S + у разі негативної відповіді слід видалити залежність f з безлічі S вийшло в результаті таких дій безліч S є непріводімим і еквівалентним вихідному безлічі S

Приклад Нехай дана змінна відношення R з атрибутами А, в, с, D і наступними функціональними залежностями

А →   НД У→  З

А→   У АВ→  З АС→   D

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

еквівалентну даній безлічі

1 Насамперед, слід переписати задані ФЗ таким чином, щоб кожна з них мала одноелементна праву частину

А→    У

А→     З

У →    З

А→     У АВ→   З АС→    D

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

2 Потім у лівій частині залежності АС → D може бути виключений атрибут с, по скільки дана залежність А → С, з якої за правилом доповнення можна по лучити залежність А → АС Крім того, дана залежність АС → D, з якої

за правилом транзитивності можна отримати залежність А → D Таким чином,

атрибут з в лівій частині вихідної залежності АС → D є надлишковим

3 Також зауважимо, що може бути виключена залежність АВ → С, оскільки дана залежність А → C, з якої за правилом доповнення можна отримати залежність тість АВ → CB, а потім за правилом декомпозиції-залежність АВ → С

4 Нарешті, залежність А → с випливає з залежностей А → B і B → C, так що вона також може бути відкинута В результаті отримано таке неприводим моє безліч залежностей

А →   У

У →  З

А→  D

Безліч функціональних залежностей I, яке неприводимого і еквівалентно іншому безлічі функціональних залежностей s, називається непріводімим еквівалентом безлічі S Таким чином, в системі замість вихідного безлічі функціональних залежностей S з тим же успіхом може використовуватися його непріводімий еквівалент I (тут слід повторити, що для обчислення неприводимого еквівалента I не обовязково обчислювати замикання s +) Однак необхідно відзначити, що для будь-якого заданого безлічі функціональних залежностей не завжди існує унікальний непріводімий еквівалент (див упр 1112)

112 РЕЗЮМЕ

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

З одних функціональних залежностей ідуть інші залежності Для даної множини залежностей S замиканням S + називається безліч всіх функціональних залежностей, які слідують з залежностей безлічі S Безліч S обовязково є підмножиною власного замикання S +Правила логічного висновку Армстронга забезпечують несуперечливу і повну основу для обчислення замикання S +

для заданої множини s (але насправді зазвичай проведення цих обчислень не потрібно) На підставі правил Армстронга можна легко отримати кілька додаткових зручних правил

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

Два безлічі функціональних залежностей s1 і S2 еквівалентні тоді і тільки

тоді, коли вони є покриттями один для одного, тобто S1 + = S2 + Кожне безліч функціональних залежностей еквівалентно принаймні одномуНепріводімие множині Безліч функціональних залежностей є непріводімим, якщо, по-перше, кожна функціональна залежність цієї множини має одноелементна праву частину по-друге, якщо жодна функціональна залежність множини не може бути видалена без зміни замикання цієї множини по-третє, якщо жоден атрибут не може бути видалений з лівої частини будь-якої функціональної залежності даного безлічі без зміни замикання множини Якщо I є непріводімим безліччю, яке еквівалентно безлічі S, то перевірка виконання функціональних залежностей з безлічі I автоматично забезпечить виконання всіх функціональних залежностей з безлічі S

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

■ Деякі обмеження цілісності є тривіальними

■ З одних обмежень цілісності ідуть інші обмеження

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

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

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

Завдяки наявності несуперечливого і повного безлічі правил виведення різних функціональних залежностей, працювати з ними зручніше, ніж з обмеженнями цілісності як такими У списках рекомендованої літератури наприкінці цієї глави і глави 13 дані посилання на роботи, в яких описуються кілька інших типів обмежень (MVD, JD і IND) для них також існують подібні набори правил виводу Однак в

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

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

*

*