18228

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

Реферат

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

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

Украинкский

2013-07-07

112.5 KB

13 чел.

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

Стосовно реляційного відношення 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)           


 

А также другие работы, которые могут Вас заинтересовать

23562. Проект Разработка программы распознавания русской речи Для процессора SuperH RISK (Hitachi) 196 KB
  Целью проекта является создание системы независимой от диктора системы распознавания речи. Использование этой системы предполагается в мобильных карманных устройствах поэтому наряду с требованием высокой достоверности распознавания к ней также предъявляются очень жесткие требования относительно компактности и быстродействия. Тестирование системы было проведено на словаре из 2500 слов произнесенных различными дикторами не принимавших участие в процессе настройки системы. Разработка системы состояла из следующих этапов: составление...
23563. Щерба Лев Владимирович 44 KB
  Щерба получил прежде всего как фонолог и фонетист. Щерба был виднейшим исследователем в области экспериментальной фонетики. Щерба признавал важность эксперимента. Щерба создал свою теорию фонемы.
23564. ОРГАНЫ РЕЧИ И ИХ РАБОТА 119.85 KB
  При произнесении глухих согласных голосовые связки не напряжены и раздвинуты. Когда голосовые связки напряжены и сближены а поток воздуха заставляет их вибрировать возникает голос который мы слышим при произнесении гласных сонантов или звонких согласных звуков. При произнесении глухих согласных слышится только шум при произнесении звонких шум и голос. При произнесении смычных сонантов проход для воздуха через ротовую полость закрыт так как мягкое нёбо опущено.
23565. Технология SDH 148.5 KB
  Синхронная цифровая иерархия (SDH) — технология широкополосных транспортных сетей, которые являются инфраструктурой для подключения пользователя к широкому спектру услуг. Сети SDH позволяют передавать информационные потоки на скоростях до 10 Гбит/сек
23566. Фонологические взгляды И. А. Бодуэна де Куртенэ 28.5 KB
  Бодуэна де Куртенэ И. Бодуэн де Куртенэ создавая теорию фонем трактовал фонологические единицы как некие сущности наличествующие в психологической системе человека пользующегося соответствующим языком.Пр54в Придерживаясь материалистической трактовки природы психическогоПр54н Бодуэн де Куртенэ только тогда считал возможным говорить о существовании тех или иных внутриязыковых закономерностей когда представлял себе их психофизический механизм и только тогда выдвигал то или иное понятие когда мог определить его хотя бы в самых...
23567. Фонология 23.5 KB
  лежит понятие фонемы как совокупности существенных признаков свойственных данному звуковому образованию определение Н. Главной функцией фонемы является смыслоразличительная или сигнификативная. Таким образом можно сказать что фонемы д и к отличаются друг от друга двумя дифференциальными признаками местом образования и звонкостьюглухостью. В русской фонологической системе 5 гласных фонем и 32 согласных гласность и согласность или как говорят вокализм и консонантизм это первый дифференциальный признак для фонемы: мы обычно сразу...
23568. ФОНЕМЫ И СИСТЕМЫ ФОНЕМ 93 KB
  Понятие фонемы Ключевым понятием функциональной фонетики или фонологии является понятие фонемы. Следовательно хотя фонемы как таковые единицами языка не являются поскольку сами по себе они лишены значения существование единиц языка морфем слов и их форм принципиально невозможно без фонем из которых строятся их означающие. О соотношении фонемы и звука Фонемы не могут быть непосредственно отождествлены со слышимыми и произносимыми людьми в процессе речевого общения звуками. Фонемы представляют собой единицы звукового строя языка тогда...
23569. 8 особенности артикуляционной базы английского языка 39.5 KB
  в англ языке большее напряжение конечных согл наличие аспирглухих взрывных соглперед ударотсутсвие палатализациинет нет попарного разделения на тверд и мяг есть фарингальная артикул.hпереднеязвчные согл характеризуются аппикальным укладомдорсальнымнапряж мышц губ при произношении более значительнаогубленостьлабоализациянапряжение в конце фразы силнее характерно наличие скользящих гласныхдифтонгов попарно распределение напряж и ненапряж фонемдолгих краткналичие гласных смеш уклада э:наличие межзубных 9 артикуляторный...
23570. сновные фонетические особенности канадского варианта английского языка 31 KB
  Class bath dance произносится в американском варианте с гласным номер 4. Дифтонг [ou] произносится в британском варианте т.которые в американском варианте произносятся с [ai] канадцы в основном произносят побритански с [i]. В канадском варианте английского языка в области грамматики не встречается существенных различий с британским вариантом.