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)           


 

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

34064. Государственный земельный контроль: понятие, функции органов 33 KB
  Государственное регулирование земельных отношений является частью государственного управления в целом. Государственное регулирование земельных отношений это целенаправленная деятельность государственных органов по организации рационального использования земель и их охраны путем принятия экономикоправовых мер. Тем более что в настоящее время центр тяжести должен быть перемещен от командноадминистративного управления землей к заново разработанной системе экономического регулирования земельных отношений в России когда субъектами этих...
34065. Сравнение физических свойств и химического состава морской воды 834.27 KB
  Изучение литературных и интернет-источников по данной теме. Освоение методик ведения физических и химических исследований по изучению свойств и химического состава морской воды. Определение физических свойств морской воды: плотности, мутности, электропроводности. Определение химических компонентов воды: гидрокарбонат -ионов, сульфат- ионов, нитрат- ионов, хлорид ионов, бромид-ионов, уровень рН.
34066. Переоформление прав на земельные участки: основания, порядок 101 KB
  Любое из перечисленных прав подлежит государственной регистрации осуществляемой уполномоченным государственным органом в соответствии с Федеральным законом от 21 июля 1997 г. N 122ФЗ О государственной регистрации прав на недвижимое имущество и сделок с ним . Именно с момента государственной регистрации прав на земельный участок можно считать данные права возникшими. 8 ГК РФ права на имущество подлежащие государственной регистрации возникают с момента регистрации соответствующих прав на него если иное не установлено законом.
34067. Оборотоспособность земельных участков 41 KB
  Земельные участки изъятые из оборота не могут предоставляться в частную собственность а также быть объектами сделок предусмотренных гражданским законодательством. К ним относятся земельные участки занятые находящимися в федеральной собственности следующими объектами:1 государственными природными заповедниками и национальными парками;2 зданиями строениями и сооружениями в которых размещены для постоянной деятельности Вооруженные Силы Российской Федерации другие войска воинские формирования и органы;3 зданиями строениями и...
34068. Классификация, основания возникновения и прекращения земельных правоотношений 30 KB
  Классификация основания возникновения и прекращения земельных правоотношений. КЛАССИФИКАЦИЯ ЗЕМЕЛЬНЫХ ПРАВООТНОШЕНИЙ Существенные различия природных свойств земли и неодинаковость хозяйственного ее использования могут обусловливать самые разнообразные земельные отношения. Это позволяет говорить о классификации земельных отношений по основному хозяйственному назначению земель. Классификацию земельных правоотношений можно строить и по другим признакам в зависимости от того какую особенность земельных правоотношений мы намерены выделить...
34069. Управление в сфере использования и охраны земель 39 KB
  Управление в сфере использования и охраны земель. В основе государственного управления лежит право территориального верховенства государства которое позволяет с одной стороны осуществлять защиту земельных прав и оказывать содействие физическим и юридическим лицам в реализации земельных прав напр. любое лицо может получить выписку из земельного кадастра с другой стороны это право позволяет привлекать виновных лиц к ответственности и выявлять в целом нарушения земельного законодательства и предпринимать соответствующие меры....
34070. Система и полномочия органов управления земельными ресурсами 24 KB
  Система и полномочия органов управления земельными ресурсами. Каждый вышестоящий уровень координирует действия нижестоящих а каждый иерархический уровень управления содержит все функции организации субъекта управления. Субъект управления на вышестоящем уровне осуществляет координирование организации субъектов управления на нижестоящих уровнях исходя из принятых для конкретного административнотерриториального образования критериев эффективности рационального использования земель. Система органов государственного управления земельными...
34071. Государственный земельный кадастр: понятие, структура, порядок ведения 38 KB
  Государственный кадастр недвижимости. âО государственном кадастре недвижимостиâ вступил в силу с 01. Государственный кадастровый учёт это действия уполномоченного органа по внесению в Государственный кадастр недвижимости сведений о недвижимом имуществе которые подтверждают существование такой недвижимости как индивидуальноопределённой вещи подтверждают прекращение существования такой недвижимости а также иные сведения предусмотренные ФЗ âОâ государственном кадастре недвижимостиâ. Государственный кадастр недвижимости ...
34072. Землеустройство: назначение, содержание, организация и порядок ведения 39 KB
  Землеустройство это мероприятие по изучению состояния земель планированию и организации рационального использования земель и их охраны по описанию местоположения и или установлению на местности границ объектов землеустройства организации рационального использования земельных участков для сельскохозяйственного производства; организации территорий используемых общинами коренных малочисленных народов Севера Сибири и Дальнего Востока и лицами относящимся к коренным малочисленным народам для обеспечения их традиционного образа жизни....