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)           


 

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

43882. Визначення та наукове обгрунтування психолого-педагогічних умов подолання особистісної тривожності у дітей молодшого шкільного віку та пятикласників 959.5 KB
  Підходи науковців до реалізації наступності зорієнтовані передусім на інтеграцію двох ланок освіти, усунення суперечок між запитами школи і амбіційним завищеними вимогами окремих батьків щодо підготовки їхніх дітей; між непідготовленістю окремих учнів, які не відвідували дошкільних установ, і необхідністю враховувати специфіку дошкільної освіти.
43883. Экономика и управление на предприятии АПК». Методические указания 605 KB
  В методических указаниях рассматриваются вопросы подготовки написания процедуры защиты дипломных работ раскрыты требования по оформлению работы. ПОДГОТОВКА КВАЛИФИКАЦИОННОЙ РАБОТЫ Выбор темы дипломной работы Назначение руководителя дипломной работы и выдача дипломного задания.
43884. Створення когнітивно-семантичного підґрунтя вибору варіантів перекладу одиниць на позначення концепту “Кількість” 249 KB
  Кількість як узагальнений когнітивний зміст – великий фрагмент кодованої засобами мови картини світу того чи іншого етносу. На першому етапі необхідно чітко визначити поняття “картина світу†“мовна картина світу†“концепт†для чого слід виконати критичний аналіз наукової літератури. Новизна одержаних результатів визначається тим що в ньому виявлено спільні і відмінні ознаки репрезентації концепту â€œКількість†в англійській та українській мовних картинах світу встановлені абсолютні і варіантні еквіваленти перекладу в...
43885. Проектування поліграфічного підприємства 3.18 MB
  Вибір напруги живлячої мережі. Вибір напруги розподільчої мережі. Характеристика джерела живлення Підприємство можна заживити від районних підстанцій що мають три рівні напруги.
43886. Изучение и систематизация теоретических аспектов организации финансов на ООО "Компания ОГАТ" 599 KB
  Финансы предприятий будучи частью общей системы финансовых отношений отражают процесс образования распределения и использования доходов на предприятиях различных отраслей народного хозяйства и тесно связаны с предпринимательством поскольку предприятие является формой предпринимательской деятельности. Целью данной дипломной работы является систематизация теоретических аспектов организации финансов на предприятиях различных форм собственности изучение аналитических сведений практической деятельности финансового состояния конкретного...
43887. Оценка уровня организации и планирования работы транспортного хозяйства на предприятии ТЧУП «Передовые технологии» на основе АВС-XYZ анализа 878 KB
  Структура и динамика грузов перевозимых предприятием и их характеристика Классификация грузов и грузовых перевозок предприятия на основе анализа АВС и XYZ Выбор рациональной структуры перевозимых грузов и видов грузовых перевозок на основе правила 80 20 и матрицы АВСXYZ анализа В третьей главе мы рассмотрим основные направления совершенствования транспортной деятельности предприятия за счет выбора рациональной структуры перевозимых грузов и видов грузовых перевозок на основе правила 80 20 и матрицы АВСXYZ анализа.
43888. Исследование взаимосвязей временных рядов курсов акций с помощью копула-функции и метода коинтеграции 5.8 MB
  Фондовый рынок - это составная часть финансового рынка на котором обращаются ценные бумаги. Для управления ценными бумагами важно знать их взаимосвязь между собой. В теоретической части подробно описываются сущность и содержание рынка ценных бумаг пакета акций методы определения взаимосвязи между временными рядами метод копулафункций и метод коинтеграции. Рынок ценных бумаг.
43889. РАЗРАБОТКА ПРОЕКТА АВТОМАТИЗАЦИИ КАДРОВОГО МЕНЕДЖМЕНТА НА ПРИМЕРЕ SRL 1.26 MB
  Основываясь на данных исследования проведенного агентством MR Reserch среди сотни быстро растущих компаний США можно утверждать что успешные и развивающиеся компании в текущем 2012 году не только не сократят а напротив увеличат свои расходы. Эксперты оценивают необходимость наличия данных качеств по семибалльной шкале которая количественно определяет не только степень необходимости но и недопустимости того или иного...
43890. ИС построения линейно-степенной регрессии 1.73 MB
  Алгоритм разделения данных на обучающую и проверочную. Проверка достоверности входных данных Проверка достоверности внутренней обработки данны. Шифрование данных.