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

4 чел.

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

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)           


 

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

42517. Определение мощности переменного тока 130 KB
  Оборудование: ваттметр электродинамической системы амперметр переменного тока вольтметр на 150 В ламповый реостат с набором ламп лабораторный автотрансформатор ЛАТР соединительные провода. Краткие теоретические сведения Мощность тока определяется как произведение силы тока на напряжение. Поскольку в случае переменного тока сила тока и напряжение изменяются по гармоническому закону то целесообразно ввести понятие мгновенной мощности равной произведению мгновенных значений силы тока и напряжения Мгновенное значение мощности...
42518. Определение индуктивности катушки разборного трансформатора 79 KB
  Оборудование: разборной школьный трансформатор реостат вольтметры постоянного и переменного тока миллиамперметр источники постоянного и переменного тока. Краткие теоретические сведения Если в проводнике меняется сила тока то в нём возникает ЭДС самоиндукции препятствующая этому изменению пропорциональная скорости изменения силы тока...
42519. Изучение переходных процессов при замыкании и размыкании цепи с индуктивностью 136 KB
  Цель работы: изучить явление электромагнитной индукции и самоиндукции; приобрести навыки наблюдения на экране осциллографа зависимости токов замыкания и размыкания от времени при различных индуктивностях; определить индуктивность катушки графическим методом. Оборудование: осциллограф ИО-4, реле РСМ, катушка индуктивности с сердечником; два резистора, трансформатор 220/8 В, источник постоянного тока.
42520. Определение коэффициента взаимоиндукции двух катушек 67.5 KB
  Оборудование: мост переменного тока магазин индуктивности источник переменного тока. Краткие теоретические сведения Если в проводнике изменяется сила тока то в нём возникает ЭДС самоиндукции 22. Если подключить такую катушку в цепь переменного тока то вследствие периодического изменения силы тока возникает ЭДС самоиндукции препятствующая приложенному напряжению.
42521. Снятие кривой намагничения и петли гистерезиса с помощью осциллографа 142.5 KB
  Краткие теоретические сведения Ферромагнетикам свойственно явление гистерезиса. Замкнутая кривая bcdef называется петлёй гистерезиса рис. Можно получить семейство петель гистерезиса по способу описанному ранее не доводя намагничение образца до насыщения.
42522. Определение ёмкости конденсаторов 104 KB
  Оборудование: регулятор напряжения ЛАТР миллиамперметр переменного тока на 250 мА вольтметр на 150 В конденсаторы. Если конденсатор включить в цепь постоянного тока то спустя некоторое время он зарядится т. Если конденсатор включить в цепь переменного тока то он будет перезаряжаться с частотой переменного ток и в подводящих проводах всё время будут перемещаться электрические заряды т.
42523. Изучение процессов зарядки и разрядки конденсаторов 240.5 KB
  Цель работы: изучить процессы, происходящие в цепи при зарядке (разрядке) конденсаторов, освоить метод расчёта ёмкости конденсаторов по данным о временной зависимости тока зарядки (разрядки). Оборудование: конденсатор, набор резисторов, микроамперметр на 100 мкА, источник питания постоянного тока, выключатель, секундомер, соединительные провода.
42524. Определение горизонтальной составляющей индукции земного магнетизма с помощью тангенс-гальванометра 102 KB
  Южный полюс магнитного поля Земли находится вблизи северных берегов Америки около 750 северной широты и 1010 западной долготы а северный полюс − в Антарктиде около 670 южной широты и 1400 восточной долготы. Существование магнитного поля Земли непосредственно подтверждается отклонением лёгкой магнитной стрелки при её свободном подвесе. При этом последняя устанавливается в направлении касательной к линии индукции магнитного поля Земли.
42525. Изучение однофазного трансформатора 118 KB
  Принцип действия трансформатора основан на использовании явления электромагнитной индукции. Знак − указывает на то что ЭДС в первичной и вторичной обмотках трансформатора противоположены по фазе. Создаваемый этим током магнитный поток Ф0 концентрируется в магнитопроводе и пронизывает все обмотки трансформатора индуцируя в первичной обмотке ЭДС самоиндукции 27.