18228

Накриття множин залежності

Реферат

Информатика, кибернетика и программирование

Накриття множин залежності. Стосовно реляційного відношення R ми можемо розглядати множину функціональних залежностей F які визначені на ньому. У.Армстронг досліджуючи властивості таких функціональних залежностей виділив дві групи: система R система Р. Пізніше бу

Украинкский

2013-07-07

112.5 KB

12 чел.

Накриття множин залежності.

Стосовно реляційного відношення R ми можемо розглядати множину функціональних залежностей F, які визначені на ньому. У.Армстронг, досліджуючи властивості таких функціональних залежностей, виділив дві  групи: система R, система Р. Пізніше була запропонована також система D.  Ці системи мають не тільки теоретичне значення, а також практично використовуються при проектуванні баз даних.

Система R - властивості:

1) проективність: якщо А В, то В А;

2) транзитивність: якщо A B і B С, то A С;

3) монотонність: якщо А В, то А U С В U С   для будь-якого атрибута С.

Ці властивості для множин атрибутів реляційного відношення  А, В, С цілком природні і очевидні .

Перед тим, як навести систему Р, необхідно на множинах атрибутів ввести частковий порядок (виконується рефлективність, транзитивність, антисиметричність):

(А, В)≥ (С, D) , якщо А С  і  D В

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

     А          С          D   В

Система Р - аксіоми:

1) рефлективність: A A

2) транзитивність: якщо A B і B С, то A С

3) якщо А В і  (А,В) ≥ (С, D), то  С D

4) композиція: якщо  А В   і  С D, то AUС ВUD

Нагадаємо, що елемент m частково впорядкованої множини M називається верхньою границею для підмножини N  M, якщо кожний елемент з N порівняний з m і не більший за m.

Частково впорядкована множина називається верхньою напіврешіткою, якщо кожна пара його елементів має верхню грань (найменшу верхню границю).

З того , що для реляційного відношення виконується система Р, випливає, що множина атрибутів реляційного відношення є верхньою напіврешіткою.

Структура – у Мальцева вживається решітки(структури)??????

Система D - система правил, які випливають з аксіом Армстронга:

1) об’єднання: якщо А В   і  A С, то A ВUС

2) псевдотранзитивність: якщо А В   і  DВ С, то AD С

3) декомпозиція: якщо А В   і  С В, то  A С

Системи R і Р еквівалентні, а D можна отримати з них. Доведемо це.

 R  Р:

1) рефлективність: A A отримуєм з проективності, бо А А.

2) транзитивність: якщо A B і B С, то A С – співпадає;

3) якщо А В  і  (А,В) ≥ (С, D), то  С D:

з визначення часткового порядку А С  і  D В;  С А (R1);  B D (R1);  тобто

С А, А В, B D   С D (R2)

4) композиція: якщо  А В   і  С D, то AUС ВUD: використаємо монотонність (R3)

А U С В U С          і  В U С В U D  AUС ВUD (R2).

 

 Р  R:

1) проективність: якщо А В, то В А – отримуєм з (Р3) і (Р1):

якщо А А і  (А,А) ≥ (В, А) (бо А В і А А), то  В А;

2) транзитивність: якщо A B  і  B С, то A С – співпадає;

3) монотонність: якщо А В, то А U С В U С   для будь-якого атрибута С;

використаємо композицію і рефлективність : якщо  А В   і  С С, то AUС ВUС.

 Р , R  D:

1) об’єднання: якщо А В   і  A С, то A ВUС є наслідком (Р4) (AUА ВUС);

2) псевдотранзитивність: якщо А В   і  DВ С, то AD С:

з А В за (R3) отримуєм АD ВD,  DВ С    AD С  за (R2)

3) декомпозиція: якщо А В   і  С В, то  A С:

з (R1) випливає, що, якщо С В, то В С; отже А В і  В С   A С  за (R2).

Визначення

Кажуть, що структура  F+ є замиканням структури залежності  F, якщо будь-який елемент з F+ можна отримати з F, користуючись системою аксіом Армстронга або її еквівалентами.

Дві структури F і G називаються еквівалентними, якщо їхні замикання рівні:

FG, якщо F+ = G+

G накриває F, якщо F+  G+.

 

Твердження

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

Для доведення розглянемо приклад:

               А ВСD

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

               А D тому, що D ВСD   ВСD D;  А ВСD, ВСD D А D;

               А В – аналогічно;

               А С – аналогічно.

Нехай задано множину функціональних залежностей F. Говорять, що множина  функціональних залежностей G утворює базис залежності F або, те ж саме, утворює мінімальне покриття F, якщо G є такою мінімальною підмножиною F, що   G+ = F+

Визначення

Кажуть, що множина функціональних залежностей F мінімальна, якщо виконуються 3 властивості:

  •  Кожна права частина має один атрибут.
  •  Для кожної функціональної залежності буде виконуватись:

 (XА)  F

               F \ {XA}    F

       -  антинадлишковість залежності.

  •   Антинадлишковість лівої частини

      Для кожної функціональної залежності з F буде виконуватись

 (XА)  F  і   Z A

 F \{XA}     {Z  A}     F 

Теорема

Для кожної функціональної залежності F  F -мінімальна   F  F    

Доведення:

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

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

  1.  На прикладі покажемо, як позбутися  надлишкових залежностей.

Нехай задана множина функціональних залежностей:

1. АВ;

2. АС;

3. ВА;

4. ВС;

5. СА літера – один атрибут

Спробуємо викинути АВ, але отримати цю залежність з інших не можемо вона не є надлишковою.

Спробуємо викинути АС :  АВ   і   ВС  ( 2(1,4) )    АС – надлишкова.

Спробуємо викинути ВА :  ВС   і   СА  ( 3(4,5) )    ВА – надлишкова.

Спробуємо викинути ВС :   ВА  і   АС  ( 4(3,2) )    ВС – надлишкова.

СА  не є надлишковою.

Щоб отримати мінімальну структуру залежностей треба викинути одну чи більше   надлишкових залежностей. У нашому випадку можна викинути 2 і 3 або 4. При цьому користуються наступними міркуваннями: перш за все, семантичне навантаження, мінімізація кількості залежностей.

  1.  Також на прикладі покажемо перевірку на антинадлишковість лівої частини функціональних залежностей.

АВС; АВ; ВА – структура F

Треба перевірити  тільки залежності, ліва частина яких містить більше одного атрибута, в нашому випадку -  АВС. Для цього викреслимо А і отримаємо

ВС; АВ; ВА – структуру G.

Доведемо, що FG, тобто F+ = G+. Для цього потрібно показати, що ВСF+ і  АВС G+.

ВС F+, бо ВА ВАВ (монотонність), АВС ВС

АВС  G+, виконується завжди, бо АВВ (проективність),  ВС АВС, тобто ми можемо, починаючи з В, в межах стратегії G отримати залежність АВС.

А можна викреслити.

Тепер перевіримо, чи можна викреслити В (аналогічно). Відповідь – так.

  А або В можна викреслити.

Визначимо  замикання множини атрибутів відносно множини функціональних залежностей. Нехай F – множина функціональних залежностей на множині атрибутів U, а  Х – деяка підмножина U. Тоді Х+, замикання Х  відносно F, є множина атрибутів А, таких, що залежність ХА може бути виведена з F за допомогою аксіом Армстронга.

Головна властивість замикання множини атрибутів полягає в тому, що дозволяє зразу визначити, чи можна отримати залежність ХY з F за допомогою аксіом Армстронга

Обчислення  F +   для множини функціональних залежностей F є трудомісткою задачею (степенева складність). На противагу цьому, обчислення Х+ набагато простіше (пропорційне довжині всіх виписаних повністю залежностей у F).  

Питання ХУ  F еквівалентне питанню У ХF+ .

Замикання ХF+  будуємо поетапно:

Х0 = Х

Х1 = Х0  {один крок }… … …

Так як множина атрибутів скінченна, то процес завершиться.

Ознака завершення: Хкк+1.

Нехай задано множину атрибутів Х деякої реляції. Побудуємо її замикання.

Х0 = Х

Х1 = Х0 {атрибути, які можуть бути отримані з Х0 за один крок}

...

Хi+1 = Хi  { атрибути, які можуть бути отримані з Х0 за і+1 крок}

Якщо Хк = Хк+1 = Х+ , то процес обривається достроково, якщо на деякому кроці Хк 

зрівнюється з усією множиною атрибутів.

Нехай маємо структуру  функціональних залежностей F:

ABC

CA

BCD

ACDB

DEG

BEC

CGBD

CEAG 

Побудуємо замикання 2-х атрибутів: BD+ 

BD+ = {B, D, E, G} = X1

X2 = {B, D, E, G, C}

X3 = {B, D, E, G, C, A} – всі атрибути побудовані, BD може бути квазіключем.

В+ = {B}  B не може бути квазіключем.

D+ = {DEG}  D не може бути квазіключем.

Приклад мінімізації структури функціональних залежностей.

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

1-й крок. Побудуємо еквівалентну  структуру функціональних залежностей з одноатрибутними правими частинами:

1.   ABC

2.   CA

3.   BCD

4.   ACDB

5.   DE

6.   DG

7.   BEC

8.   CGB

9.   CGD

10. CEA

11. CEG

2-й крок. Перевірка кожної залежності на надлишковість.

Беремо першу залежність і відкидаємо її, отримуємо структуру  функціональних залежностей G,  на G  будуємо АВ+. Якщо отримаємо С, тобто  ABC  G +, то ця залежність була надлишковою, якщо ні – не надлишковою.

1.   AB+ = {AB}

2.   C+ = {C}

3.   BC+ = {BCA}

4.   ACD+ = {ACDEGB} – залежність надлишкова, якщо присутні 6 і 8 залежності

5.   D+ = {D, G}

6.   D+ = {D, E}

7.   BD+ = {B, E}

8.   CG+ = {C, G, D, A, E, B} – надлишкова

9.   CG+ = {C, G, D, A, E, B} - надлишкова

10. CE+ = {C, E, A,G) - надлишкова

11. CE+ = {C, E, A}

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

4   (1, 3, 6, 8)

8   (9, 2, 4)

9   (8, 3)

10 (2)

Для мінімізації викинемо 10 і 8.

Друга фаза алгоритму мінімізації завершена.

3-й крок. Наступний крок стосується тих залежностей, де в лівій частині не один атрибут.

1.   ABC

2.   CA

3.   BCD

4.   ACDB

5.   DE

6.   DG

7.   BEC

8.   CGD

9.   CEG

Беремо АВС . Спробуємо викинути А.

Потрібно знайти відповіді на питання, чи ВС  F+ і  чи АВС  G+? Якщо відносно F потрібно будувати В+ , то (АВС)  G+ виконується завжди, навпаки не очевидно.

В+ = {B}, С не належить В+ ВС не належить F+. А не можна відкинути.

Чи АС  F+?

А+ = {А}, С не належить А+ АС не належить F+. В не можна відкинути.

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

  1.  В+ = {B}
  2.  A+ = {A}
  3.  C+ = {C, A}      В+ = {B}
  4.  CD+ = {C, D, E, G, A, B} – в залежності ACDB символ А надлишковий

   AD+ = {ADEG}     AC+ = {AC} -  символи С і  D не надлишкові.

Якби трапилася ситуація, що можна відкинути ще один символ, то треба перевірити, чи можна вилучити комбінацію.

Стратегія побудови 3 НФ.

Зробимо зворотній крок: перейдемо від одноатрибутних правих частин до багатоатрибутних.

ABC

CA

BCD

CDB

DEG

BEC

CGD

CEG

Нам потрібно перевірити, чи знаходиться реляція, яка має такі функціональні залежності, в 3 НФ, якщо ні – привести до 3 НФ.

Теорема Хіза стверджує: якщо список атрибутів А функціонально визначає список атрибутів В, то реляцію можна розкласти на дві реляції, з яких шляхом природного з’єднання можна отримати початкову реляцію без втрат.

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

Тепер, якщо ми викреслимо всі атрибути з правої частини, то всі атрибути викресляться.

Тобто ми не можемо виділити групу атрибутів, яка визначає іншу групу атрибутів.

Ми отримали непридатну процедуру.

Побудуємо графічне представлення структури.

     A  B

 C E

D

 G

BD, CD – квазіключі.

B, C, D первинні атрибути, які належать деякому квазіключу.

AB+ = {ABCD…} – комбінуємо BD чи CD, що дає можливість отримати всі

                               AB – квазіключ

BE+ = {BECA…} – теж квазіключ

CG+ - теж  квазіключ

всі атрибути первинні реляція знаходиться в 3 НФ.

Розглянемо схематичне зображення ще однієї реляції..

Для того щоб отримати 3 НФП,  треба відсікати ієрархічні компоненти.

А В С                             F E

 D

H

K

L

G

 Піддерева

Користуючись теоремою Хіза, поетапно розкладаємо нашу реляцію:

                                   R1 (D, K, L)            R̃1 (ABCDFEHG)

                                   R2 (H, G)            R̃2 (ABCDEFH)

                                   R3 (F, E, D, H)            R̃3 (ABCEF)  або

              R3 (A, B, C, D)            R4 (F, E, H)              R5 (A, B, C, E, F)