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)           


 

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

26123. Учет расчетов с персоналом по оплате труда 55.5 KB
  Для учета личного состава для учета расчетов по начислению и выплате зарплаты используются следующие унифицированные формы первичных документов: приказ распоряжение о приеме работника на работу личная карточка работника приказ распоряжение о предоставлении отпуска приказ распоряжение о прекращении действия трудового договора табель учета рабочего времени документы по учету выработки – наряды на сдельную работу маршрутные листы и ведомости учета выполненных работ. При косвенносдельной размер зарплаты работника ставиться в...
26124. Учет ОС 39.5 KB
  Период в течении которого организация планирует получать экономические выгоды от использования актива называется срок полезного использования. При наличии у 1 объекта нескольких частей сроки использования которых существенно отличаются то каждая такая часть учитывается как самостоятельный инвентарный объект. Амортизация начисляется исходя из срока полезности который определяет предприятие исходя из: ожидаемого срока использования ожидаемого физического износа зависящего от режима эксплуатации и среды нормативноправовых и других сроков...
26125. Сущность и порядок учета МПЗ 41 KB
  Методы списания материалов на затраты предприятия. Документальное оформление и учет материалов на складе и в бухгалтерии. Аналитический и синтетический учет материалов. МПЗ активы используемые в качестве сырья материалов при производстве продукции выполнении работ оказании услуг активы предназначенные для продажи товары готовая продукция а так же другие активы используемые для управленческих нужд организации.
26126. Учет затрат на производство и реализацию продукции 46 KB
  Учет затрат на производство и реализацию продукции. Себестоимость продукции работ услуг представляют собой стоимостную оценку использованных в процессе производства природных ресурсов сырья материалов топлива энергии основных средств трудовых ресурсов а так же других затрат на ее производство и реализацию. По способу включения в себестоимость отдельных видов продукции затраты делятся на прямые и косвенные. Прямые связаны с производством отдельных видов продукции и могут быть прямо включены в себестоимость отдельного вида продукции.
26127. Учет готовой продукции, ее реализации и финансовых результатов 33 KB
  Учет готовой продукции ее реализации и финансовых результатов. Структура ответа: Понятие готовой продукции. Виды оценки готовой продукции. Документальное оформление и отражение на счетах БУ реализации готовой продукции.
26128. Управленческий учет как элемент системы БУ 33.5 KB
  Одна из важнейших задач руководителя предприятия с максимальной отдачей использовать имеющиеся в распоряжении предприятия ресурсы. Это означает что деятельность по учету не разрывно связана с управление предприятия. При таком подходе УУ организуется исходя из потребностей управления и УУ это система сбора анализа информации об издержках предприятия система бюджетирования и система оценки деятельности как всего предприятия в целом так и его отдельных структурных подразделений. Это расширенная система организации учета для целей контроля...
26129. Сравнительная характеристика Финансового и управленческого учета 24.5 KB
  Предъявляются единые требования к первичным документам которые являются источником информации для Ф и У учета.пользователи информации Внешние пользователи Внутренние пользователи 4.базисная структура Балансовое управление: активы=капиталобязательства Структура информации зависит от запросов пользователей 5. бухгалтерские проводки делаются в учете после совершения операции Кроме исторической информации включаются оценки и планы на будущее 7.