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)           


 

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

15902. ГАРМОНИЯ ТЕОРЕТИЧЕСКИЙ КУРС 15.27 MB
  Настоящая книга, являясь теоретическим курсом, одновременно представляет собой научное исследование фундаментальных проблем гармонии. Автор рассматривает многие коренные вопросы гармонии в виде целостной структуры, в контексте музыкальной формы. Главная задача данного исследования - дать на современном научном уровне по возможности исчерпывающее изложение основополагающих теоретических проблем гармонии, вводящее музыку XX века в общий музыкально-гармонический контекст так же естественно, как и само искусство прошлого перешло к нашему времени.
15903. Теоретические основы современной гармонии 15.56 MB
  Сегодняшний курс гармонии в средних и высших музыкальных учебных заведениях нуждается в постоянном расширении своей тематики, ее активном приближении к новым художественным явлениям музыкального искусства XX столетия. Необходимость в этом продиктована все более нарастающим интересом будущих музыкантов к произведениям нашего времени, к тайнам творческих лабораторий композиторов разных школ и направлений.
15904. Физическое воспитание начинающего боксёра 639.5 KB
  В.А.Чудинов Физическое воспитание начинающего боксёра Предисловие Физическое воспитание способствует укреплению здоровья и гармоническому развитию организма. В его задачу входит развитие быстроты силы ловкости гибкости выносливости воспитание волев
15905. Расчет цифровых тропосферных радиорелейных линий 5.87 MB
  Курсовой проект по теме Расчет цифровых тропосферных радиорелейных линий Введение Эффект дальнего тропосферного распространения радиоволн дециметрового и сантиметрового диапазонов волн был открыт в начале 50х годов. Его практическое применение дало возможность
15906. Практика в школе №12 г. Самара 286 KB
  Дневник педагогической практики Название и № школы: МОУ Школа №12 го Самара Адрес и телефон: г. Самара ул.Красноармейская д. № 93 а тел: 332 – 45 46 . ФИО директора: Горячева Е.В. ФИО зам директора по учебной работе: Хабецкая Н.И ФИО зам директора...
15907. Педагогическая психология 160.61 KB
  История становления педагогической психологии Педагогическая психология развивающаяся наука Педагогическая мысль впервые изложенная в труде Яна Амоса Коменского Великая дидактика в 1657 г. положила начало развитию педагогической теории и целенаправленно...
15908. ЗАПАДНОЕВРОПЕЙСКАЯ КУЛЬТУРА ВОЗРОЖДЕНИЯ 151 KB
  ТЕМА 10. ЗАПАДНОЕВРОПЕЙСКАЯ КУЛЬТУРА ВОЗРОЖДЕНИЯ План: Культура Возрождения: особенности. Новое мировоззрение. Итальянское Возрождение. Периодизация. Северное Возрождение. 4.1. Возрождение в Нидерландах. 4.2. Французский Ренессанс....
15909. Адвокатура и власть 828.5 KB
  И.С. Яртых АДВОКАТУРА и ВЛАСТЬ Под редакцией Заслуженного деятеля науки РСФСР доктора юридических наук профессора Бойкова А.Д. Москва Издательство Юрлитинформ 2003 УДК 347.965 ББК 67.75 Я77 ЯртыхИ.С. Я77 Адвокатура и власть. М.: Издательство Юрл...
15910. Державне будівництво та місцеве самоврядування в Україні 3.28 MB
  МВС України Національний університет внутрішніх справ О.Н. Ярмиш В.О. Серьогін ДЕРЖАВНЕ БУДІВНИЦТВО ТА МІСЦЕВЕ САМОВРЯДУВАННЯ В УКРАЇНІ Допущено МВС України в якості навчального посібника для вищих навчальних закладів ...