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)           


 

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

27582. Грабеж и его признаки 35.5 KB
  Понятие насильственного грабежа его отличие от разбоя ст. Объект грабежа 161 отношения собственности при квалифицирующих признаках грабежа появляется дополнительный факультативный объект телесная неприкосновенность потерпевшего. Кроме того следует учитывать момент окончания этих преступлений материальный состав грабежа предполагает завладение чужим имуществом тогда как состав разбоя нет. При разграничении разбоя и грабежа важен и способ действия виновного применение ОРУЖИЯ или предметов используемых в качестве оружия всегда...
27583. Действие уголовного закона во времени. Обратная сила уголовного закона и её пределы. Действие уголовного закона в пространстве, его принципы (территориальный, гражданства, реальный, универсальный). Выдача лиц, совершивших преступление 42 KB
  Уголовный закон это нормативноправовой акт принимаемый высшими органами государственной власти и состоящий из взаимосвязанных норм определяющих основания и принципы уголовной ответственности а также какие деяния признаются преступлениями порядок назначения наказания за их совершение либо в определенных случаях указывающих условия для освобождения от уголовной ответственности и наказания. Законом усиливающем наказание является закон вводящий в санкцию статьи Особенной части более суровый вид наказания чем был предусмотрен. Усиление...
27585. Заведомо ложные показание, заключение эксперта или неправильный перевод (ст. 307 УК). Заведомо ложный донос (ст. 306 УК) и его отличие от клеветы (ст. 129 УК) 30.5 KB
  Объективная сторона данного преступления выражается в том что названные в ч. Комментируемое деяние становится квалифицированным если оно соединено с обвинением лица в совершении тяжкого или особо тяжкого преступления. Круг субъектов данного преступления определен в самой норме это свидетель потерпевший эксперт специалист и переводчик. Подозреваемый обвиняемый и подсудимый не могут быть привлечены к ответственности Субъективная сторона этого преступления характеризуется только прямым умыслом.
27587. Задачи и функции (охранительная и регулятивная) уголовного права. Принципы уголовного права 29 KB
  Задачи и функции охранительная и регулятивная уголовного права. Принципы уголовного права. Задачи уголовного права сформулированы в ст. Задачи уголовного права реализуются в процессе осуществления основных функций данной отрасли законодательства 1 Предупредительная регулятивная функция заключается в установлении наказания тем самым предупреждая граждан об ответственности в случае совершения преступления.
27589. Задержание лица, совершившего преступление. Основания для задержания и условия правомерности действий по его задержанию. Отличие причинения вреда при задержании преступника от необходимой обороны 29 KB
  Задержание лица совершившего преступление. В соответствии с законом не является преступлением причинение вреда лицу совершившему преступление при его задержании для доставления органам власти и пресечения возможности совершения им новых преступлений если иными средствами задержать такое лицо не представилось возможным и при этом причиненный вред не превысил пределов необходимости. 91 УПК РФ: 1 если лицо застигнуто при совершении преступления или непосредственно после его совершения; 2 потерпевшие или очевидцы укажут на данное лицо как...