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)           


 

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

81551. Полиморфные формы гемоглобинов человека. Гемоглобинопатии. Анемические гипоксии 135.14 KB
  Гемоглобинопатии. Анемические гипоксии Гемоглобины взрослого человека В эритроцитах взрослого человека гемоглобин составляет 90 от всех белков данной клетки. Гемоглобин А основной гемоглобин взрослого организма составляет около 98 от общего количества гемоглобина тетрамер состоит из 2 полипептидных цепей α и 2 β 2α2β.
81552. Биосинтез гема и его регуляция. Нарушения синтеза тема. Порфирии 175.5 KB
  Нарушения синтеза тема. В костном мозге гем необходим для синтеза гемоглобина в ретикулоцитах в гепатоцитах для образования цитохрома Р450. Первая реакция синтеза гема образование 5аминолевулиновой кислоты из глицина и сукцинилКоА идёт в матриксе митохондрий где в ЦТК образуется один из субстратов этой реакции сукцинилКоА. В цитоплазме проходят промежуточные этапы синтеза гема: соединение 2 молекул 5аминолевулиновой кислоты в молекулу порфобилиногена дезаминирование порфобилиногена с образованием гидроксиметилбилана...
81553. Распад гема. Обезвреживание билирубина. Нарушения обмена билирубина—желтухи: гемолитическая, обтурационная, печеночно-клеточная. Желтуха новорожденных 167.22 KB
  Обезвреживание билирубина. Нарушения обмена билирубина желтухи: гемолитическая обтурационная печеночноклеточная. Биливердин восстанавливается до билирубина NDPHзависимым ферментом биливердинредуктазой. При распаде 1 г гемоглобина образуется 35 мг билирубина а в сутки у взрослого человека примерно 250350 мг билирубина.
81554. Диагностическое значение определения билирубина и других желчных пигментов в крови и моче 102.49 KB
  Так при выраженной гемолитической желтухе сопровождающейся повышением концентрации непрямого билирубина неизбежно страдают различные органы в том числе и печень что может вносить элементы паренхиматозной желтухи т. повышение в крови и моче прямого билирубина. При подпечёночной механической желтухе например при раке головки поджелудочной железы неизбежен повышенный гемолиз как следствие раковой интоксикации и как следствие повышение в крови как прямого так и непрямого билирубина.
81555. Обмен железа: всасывание, транспорт кровью, депонирование. Нарушение обмена железа: железодефицитная анемия, гемохроматоз 121.13 KB
  Нарушение обмена железа: железодефицитная анемия гемохроматоз. Освобождению железа из солей органических кислот способствует кислая среда желудочного сока. Наибольшее количество железа всасывается в двенадцатиперстной кишке.
81556. Основные белковые фракции плазмы крови и их функции. Значение их определения для диагностики заболеваний. Энзимодиагностика 115.07 KB
  Почти все белки плазмы, за исключением альбумина, являются гликопротеинами. Олигосахариды присоединяются к белкам, образуя гликозидные связи с гидроксильной группой серина или треонина, или взаимодействуя с карбоксильной группой аспарагина. Концевой остаток олигосахаридов в большинстве случаев представляет собой N-ацетилнейраминовую кислоту, соединённую с галактозой
81557. Свертывающая система крови. Этапы образования фибринового сгустка. Внутренний и внешний пути свертывания и их компоненты 234.47 KB
  При повреждении кровеносного сосуда инициируется каскад реакций, в результате которого образуется сгусток крови - тромб, предотвращающий кровотечение. Основную роль в свёртывании (коагуляции) крови играют тромбоциты и ряд белков плазмы крови. В остановке кровотечения различают 3 этапа. На первом этапе происходит сокращение кровеносного сосуда
81558. Принципы образования и последовательность фукционирования ферментных комплексов прокоагулянтного пути. Роль витамина К в свертывании крови 107.4 KB
  В циркулирующей крови содержатся проферменты протеолитических ферментов: фактор II протромбин фактор VII проконвертин фактор IX Кристмаса фактор X Стюарта. Находящиеся в крови факторы V акцелерин и VIII антигемофильный фактор а также мембранный белок тканевый фактор ТФ фактор III являются белкамиактиваторами этих ферментов. Комплекс XVСа2 протромбиназный комплекс активирует протромбин фактор II. В процессе реализации тромбогенного сигнала проферменты факторы VII IX X и II частичным протеолизом превращаются в...
81559. Основные механизмы фибринолиза. Активаторы плазминогена как тромболитические средства. Основаные антикоагулянты крови: антитромбин III, макроглобулин, антиконвертин. Гемофилии 154.37 KB
  Основаные антикоагулянты крови: антитромбин III макроглобулин антиконвертин. Такие ингибиторы ферментов свёртывания крови как α2макроглобулин α1антитрипсин и комплекс антитромбин IIIгепарин также обладают небольшой фибринолитической активностью. Снижение фибринолитической активности крови сопровождается тромбозами. Нарушение разрушения фибринового сгустка может быть вызвано наследственным дефицитом плазминогена или генетическим дефектом его структуры снижением поступления в кровь активаторов плазминогена повышением содержания в крови...