22608

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

Лекция

Математика и математический анализ

Х0 = Х Х1 = Х0 {атрибути які можуть бути отримані з Х0 за один крок} . Хi1 = Хi  { атрибути які можуть бути отримані з Х0 за і кроків} Якщо Хк = Хк1 = Х то процес обривається достроково якщо на деякому кроці Хк зрівнюється з усією множиною атрибутів. Приклад: ABC CA BCD ACDB DEG BEC CGBD CEAG Побудуємо замикання 2х атрибутів: BD BD = {B D E G} = X1 X2 = {B D E G C} X3 = {B D E G C A} – всі атрибути побудовані В = {B}  B не може бути квазіключем D = {DEG} Мінімізуємо дану структуру: Перевірка кожної...

Украинкский

2013-08-04

65.5 KB

3 чел.

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

FG, якщо F+ = G+

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

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

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

Твердження:

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

Приклад:

               А ВСД

               А ВС

               А Д

               А В

               А С

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

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

 (XА)  F

               P \ {XA}    F

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

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

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

 (XА)  F  Z A

 F \ {XA}  {Z  A}    F

Теорема:

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

Доведення:

  1.  попереднє твердження
  2.  АВ; АС;

     ВА; ВС;          СА літера – один атрибут

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

      АС: АВ & ВС АС – надлишкова

    Щоб отримати мінімальну структуру залежностей треба викинути одну з   

    надлишкових залежностей.

  1.  антинадлишковість лівої частини

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

   Треба перевірити АВС. Для цього викреслимо А і отримаємо структуру G :

   ВС; АВ; ВА

Чи можемо ми починаючи з В в межах стратегії G отримати залежність АВС

ВА

ВАВС                 АВВС

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

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

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

Конструктор алгоритму: пройтись по всім залежностям структури і перевірити, чи  

не є анти надлишковою побудована система.

Нехай задана множина атрибутів Х та СФЗ F. Для цієї множини Х по структурі F і  

аксіомам Арметронга можна побудувати замикання Х+ - множину атрибутів, які або належать множині Х, або є залежними від Х по структурі F і аксіомам Арметронга.

Питання ХУ  F еквівалентне питанню У ХF+ (степенева складність)

Х0 = Х

Хi+1 = Хi  {крок 1}

Т. я. множина атрибутів скінчена процес завершиться. Ознака завершення: Хк = Хк+1.

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

Х0 = Х

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

...

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

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

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

Приклад:

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} – всі атрибути побудовані

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

D+ = {DEG}

Мінімізуємо дану структуру:

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

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

AB+ = {AB}

C+ = {C}

BC+ = {BCA}

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

D+ = {D, C}

D+ = {D, E}

BD+ = {B, E}

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

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

CE+ = {C, E, A, …} - надлишкова

CE+ = {C, E, A}

Використаємо 10 і 8.

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

Беремо ВС

Чи ВС  F?

Чи АВС  G?

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

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

   AD+ = {ADEG}     AC+ = {AC}

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

Побудова стратегії в 3 НФ.

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

ABC

CA

BCD

CDB

DEG

BEC

CGD

CEG

Теорема Хіза ...

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

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

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

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

     A  B

 C E

D

 G

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

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

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

                               AB – квазіключ

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

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

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

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

А В С                             F E

 D

H

K

L

G

 Піддерева

Користуючись теоремою Хіза: R1 (D, K, L)            R̃1 (ABCFEHG)

                                                     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)           


 

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

73325. Дискусія: «Дон Кіхот: «за» і «проти» 136.58 KB
  Маршака та інших присвячених Дон Кіхоту. Мозковий штурм Хто такий Дон Кіхот: благородний лицар чи божевільний написати свої ідеї Оголошення теми та мети уроку. Три погляди на образ Дон Кіхота.
73326. Правописание приставок на з-, с 195.2 KB
  Правописание какой части слова мы сейчас изучаем В самом слове приставка тоже есть приставка как объяснить ее написание присоединение. В раздаточном: Какие приставки живут в этих домах Что общего
73328. Додавання і віднімання дробів з різними знаменниками 1.06 MB
  Познайомитися з правилом додавання і віднімання звичайних дробів з різними знаменниками, формувати навички застосування правила при вирішенні типових вправ ; удосконалювати вміння приводити дроби до НСЗ, скорочувати їх, виділяти цілу частину з неправильного дробу;
73330. Урок з математики з елементами українознавства. Розв’язування рівнянь 75.5 KB
  Тема уроку: Розв’язування рівнянь. Мета уроку: Навчальна: узагальнити і закріпити знання учнів про рівняння; Вдосконалювати вміння і навики розв’язувати рівняння на основі залежностей між компонентами арифметичних дій; Розвивальна: Розвивати обчислювальні навики; Розвивати логічне мислення уважність та спостережливість пізнавальний інтерес; Виховна: виховувати почуття любові до України до рідної мови;виховувати інтерес до предмета; Виховувати працелюбність наполегливість...
73331. Повторення складу чисел 5 і 6. Складання рівностей за малюнками. Обчислення значень виразів, що містять додавання, за допомогою предметних малюнків 279.77 KB
  Мета: повторити всі варіанти складу чисел 5 і 6; вправляти у складанні прикладів за малюнками, у розпізнаванні геометричних фігур; вдосконалювати обчислювальні навички; розвивати мислення, навички каліграфічного письма; виховувати старанність.
73333. Створення нумерованих та маркованих списків. Настроювання параметрів сторінок. Створення колонтитулів 860.57 KB
  Мета уроку: сформувати поняття: нумерований і маркований списки; колонтитули; розглянути: способи створення нумерованих маркованих та багаторівневих списків; особливості настроювання параметрів сторінок; формувати вміння: створювати нумеровані й марковані списки; створювати колонтитули; застосовувати набуті знання на практиці; розвивати: творчі здібності; критичне та аналітичне мислення; навчити: застосовувати вміння створювати списки при оформленні тексту; настроювати параметри сторінки. Очікувані...