18228

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

Реферат

Информатика, кибернетика и программирование

Накриття множин залежності. Стосовно реляційного відношення R ми можемо розглядати множину функціональних залежностей F які визначені на ньому. У.Армстронг досліджуючи властивості таких функціональних залежностей виділив дві групи: система R система Р. Пізніше бу

Украинкский

2013-07-07

112.5 KB

13 чел.

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

Стосовно реляційного відношення R ми можемо розглядати множину функціональних залежностей F, які визначені на ньому. У.Армстронг, досліджуючи властивості таких функціональних залежностей, виділив дві  групи: система R, система Р. Пізніше була запропонована також система D.  Ці системи мають не тільки теоретичне значення, а також практично використовуються при проектуванні баз даних.

Система R - властивості:

1) проективність: якщо А В, то В А;

2) транзитивність: якщо A B і B С, то A С;

3) монотонність: якщо А В, то А U С В U С   для будь-якого атрибута С.

Ці властивості для множин атрибутів реляційного відношення  А, В, С цілком природні і очевидні .

Перед тим, як навести систему Р, необхідно на множинах атрибутів ввести частковий порядок (виконується рефлективність, транзитивність, антисиметричність):

(А, В)≥ (С, D) , якщо А С  і  D В

Графічно це можна проілюструвати за допомогою точок на числовій прямій:

     А          С          D   В

Система Р - аксіоми:

1) рефлективність: A A

2) транзитивність: якщо A B і B С, то A С

3) якщо А В і  (А,В) ≥ (С, D), то  С D

4) композиція: якщо  А В   і  С D, то AUС ВUD

Нагадаємо, що елемент m частково впорядкованої множини M називається верхньою границею для підмножини N  M, якщо кожний елемент з N порівняний з m і не більший за m.

Частково впорядкована множина називається верхньою напіврешіткою, якщо кожна пара його елементів має верхню грань (найменшу верхню границю).

З того , що для реляційного відношення виконується система Р, випливає, що множина атрибутів реляційного відношення є верхньою напіврешіткою.

Структура – у Мальцева вживається решітки(структури)??????

Система D - система правил, які випливають з аксіом Армстронга:

1) об’єднання: якщо А В   і  A С, то A ВUС

2) псевдотранзитивність: якщо А В   і  DВ С, то AD С

3) декомпозиція: якщо А В   і  С В, то  A С

Системи R і Р еквівалентні, а D можна отримати з них. Доведемо це.

 R  Р:

1) рефлективність: A A отримуєм з проективності, бо А А.

2) транзитивність: якщо A B і B С, то A С – співпадає;

3) якщо А В  і  (А,В) ≥ (С, D), то  С D:

з визначення часткового порядку А С  і  D В;  С А (R1);  B D (R1);  тобто

С А, А В, B D   С D (R2)

4) композиція: якщо  А В   і  С D, то AUС ВUD: використаємо монотонність (R3)

А U С В U С          і  В U С В U D  AUС ВUD (R2).

 

 Р  R:

1) проективність: якщо А В, то В А – отримуєм з (Р3) і (Р1):

якщо А А і  (А,А) ≥ (В, А) (бо А В і А А), то  В А;

2) транзитивність: якщо A B  і  B С, то A С – співпадає;

3) монотонність: якщо А В, то А U С В U С   для будь-якого атрибута С;

використаємо композицію і рефлективність : якщо  А В   і  С С, то AUС ВUС.

 Р , R  D:

1) об’єднання: якщо А В   і  A С, то A ВUС є наслідком (Р4) (AUА ВUС);

2) псевдотранзитивність: якщо А В   і  DВ С, то AD С:

з А В за (R3) отримуєм АD ВD,  DВ С    AD С  за (R2)

3) декомпозиція: якщо А В   і  С В, то  A С:

з (R1) випливає, що, якщо С В, то В С; отже А В і  В С   A С  за (R2).

Визначення

Кажуть, що структура  F+ є замиканням структури залежності  F, якщо будь-який елемент з F+ можна отримати з F, користуючись системою аксіом Армстронга або її еквівалентами.

Дві структури F і G називаються еквівалентними, якщо їхні замикання рівні:

FG, якщо F+ = G+

G накриває F, якщо F+  G+.

 

Твердження

Кожна множина функціональних залежностей F накривається деякою множиною G,  де кожна права частина має не більше одного атрибута.

Для доведення розглянемо приклад:

               А ВСD

і продемонструємо, як можна привести функціональну залежність до функціональних залежностей  з одноатрибутною правою частиною.

               А D тому, що D ВСD   ВСD D;  А ВСD, ВСD D А D;

               А В – аналогічно;

               А С – аналогічно.

Нехай задано множину функціональних залежностей F. Говорять, що множина  функціональних залежностей G утворює базис залежності F або, те ж саме, утворює мінімальне покриття F, якщо G є такою мінімальною підмножиною F, що   G+ = F+

Визначення

Кажуть, що множина функціональних залежностей F мінімальна, якщо виконуються 3 властивості:

  •  Кожна права частина має один атрибут.
  •  Для кожної функціональної залежності буде виконуватись:

 (XА)  F

               F \ {XA}    F

       -  антинадлишковість залежності.

  •   Антинадлишковість лівої частини

      Для кожної функціональної залежності з F буде виконуватись

 (XА)  F  і   Z A

 F \{XA}     {Z  A}     F 

Теорема

Для кожної функціональної залежності F  F -мінімальна   F  F    

Доведення:

Згідно з визначенням мінімальної множини функціональних залежностей , потрібно показати виконання трьох властивостей.

  1.  В приведеному вище твердженні говориться, що кожна множина функціональних залежностей F накривається деякою множиною G,  де кожна права частина має не більше одного атрибута.

  1.  На прикладі покажемо, як позбутися  надлишкових залежностей.

Нехай задана множина функціональних залежностей:

1. АВ;

2. АС;

3. ВА;

4. ВС;

5. СА літера – один атрибут

Спробуємо викинути АВ, але отримати цю залежність з інших не можемо вона не є надлишковою.

Спробуємо викинути АС :  АВ   і   ВС  ( 2(1,4) )    АС – надлишкова.

Спробуємо викинути ВА :  ВС   і   СА  ( 3(4,5) )    ВА – надлишкова.

Спробуємо викинути ВС :   ВА  і   АС  ( 4(3,2) )    ВС – надлишкова.

СА  не є надлишковою.

Щоб отримати мінімальну структуру залежностей треба викинути одну чи більше   надлишкових залежностей. У нашому випадку можна викинути 2 і 3 або 4. При цьому користуються наступними міркуваннями: перш за все, семантичне навантаження, мінімізація кількості залежностей.

  1.  Також на прикладі покажемо перевірку на антинадлишковість лівої частини функціональних залежностей.

АВС; АВ; ВА – структура F

Треба перевірити  тільки залежності, ліва частина яких містить більше одного атрибута, в нашому випадку -  АВС. Для цього викреслимо А і отримаємо

ВС; АВ; ВА – структуру G.

Доведемо, що FG, тобто F+ = G+. Для цього потрібно показати, що ВСF+ і  АВС G+.

ВС F+, бо ВА ВАВ (монотонність), АВС ВС

АВС  G+, виконується завжди, бо АВВ (проективність),  ВС АВС, тобто ми можемо, починаючи з В, в межах стратегії G отримати залежність АВС.

А можна викреслити.

Тепер перевіримо, чи можна викреслити В (аналогічно). Відповідь – так.

  А або В можна викреслити.

Визначимо  замикання множини атрибутів відносно множини функціональних залежностей. Нехай F – множина функціональних залежностей на множині атрибутів U, а  Х – деяка підмножина U. Тоді Х+, замикання Х  відносно F, є множина атрибутів А, таких, що залежність ХА може бути виведена з F за допомогою аксіом Армстронга.

Головна властивість замикання множини атрибутів полягає в тому, що дозволяє зразу визначити, чи можна отримати залежність ХY з F за допомогою аксіом Армстронга

Обчислення  F +   для множини функціональних залежностей F є трудомісткою задачею (степенева складність). На противагу цьому, обчислення Х+ набагато простіше (пропорційне довжині всіх виписаних повністю залежностей у F).  

Питання ХУ  F еквівалентне питанню У ХF+ .

Замикання ХF+  будуємо поетапно:

Х0 = Х

Х1 = Х0  {один крок }… … …

Так як множина атрибутів скінченна, то процес завершиться.

Ознака завершення: Хкк+1.

Нехай задано множину атрибутів Х деякої реляції. Побудуємо її замикання.

Х0 = Х

Х1 = Х0 {атрибути, які можуть бути отримані з Х0 за один крок}

...

Хi+1 = Хi  { атрибути, які можуть бути отримані з Х0 за і+1 крок}

Якщо Хк = Хк+1 = Х+ , то процес обривається достроково, якщо на деякому кроці Хк 

зрівнюється з усією множиною атрибутів.

Нехай маємо структуру  функціональних залежностей F:

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} – всі атрибути побудовані, BD може бути квазіключем.

В+ = {B}  B не може бути квазіключем.

D+ = {DEG}  D не може бути квазіключем.

Приклад мінімізації структури функціональних залежностей.

Мінімізуємо приведену вище структуру (забезпечивши виконання трьох властивостей мінімальної множини функціональних залежностей) :

1-й крок. Побудуємо еквівалентну  структуру функціональних залежностей з одноатрибутними правими частинами:

1.   ABC

2.   CA

3.   BCD

4.   ACDB

5.   DE

6.   DG

7.   BEC

8.   CGB

9.   CGD

10. CEA

11. CEG

2-й крок. Перевірка кожної залежності на надлишковість.

Беремо першу залежність і відкидаємо її, отримуємо структуру  функціональних залежностей G,  на G  будуємо АВ+. Якщо отримаємо С, тобто  ABC  G +, то ця залежність була надлишковою, якщо ні – не надлишковою.

1.   AB+ = {AB}

2.   C+ = {C}

3.   BC+ = {BCA}

4.   ACD+ = {ACDEGB} – залежність надлишкова, якщо присутні 6 і 8 залежності

5.   D+ = {D, G}

6.   D+ = {D, E}

7.   BD+ = {B, E}

8.   CG+ = {C, G, D, A, E, B} – надлишкова

9.   CG+ = {C, G, D, A, E, B} - надлишкова

10. CE+ = {C, E, A,G) - надлишкова

11. CE+ = {C, E, A}

Отже в структурі присутні 4 надлишкові залежності, скорочено запишемо,  за допомогою яких  залежностей  вони можуть бути отримані:

4   (1, 3, 6, 8)

8   (9, 2, 4)

9   (8, 3)

10 (2)

Для мінімізації викинемо 10 і 8.

Друга фаза алгоритму мінімізації завершена.

3-й крок. Наступний крок стосується тих залежностей, де в лівій частині не один атрибут.

1.   ABC

2.   CA

3.   BCD

4.   ACDB

5.   DE

6.   DG

7.   BEC

8.   CGD

9.   CEG

Беремо АВС . Спробуємо викинути А.

Потрібно знайти відповіді на питання, чи ВС  F+ і  чи АВС  G+? Якщо відносно F потрібно будувати В+ , то (АВС)  G+ виконується завжди, навпаки не очевидно.

В+ = {B}, С не належить В+ ВС не належить F+. А не можна відкинути.

Чи АС  F+?

А+ = {А}, С не належить А+ АС не належить F+. В не можна відкинути.

Аналогічна процедура виконується для інших залежностей, в лівій частині яких більше одного атрибута.

  1.  В+ = {B}
  2.  A+ = {A}
  3.  C+ = {C, A}      В+ = {B}
  4.  CD+ = {C, D, E, G, A, B} – в залежності ACDB символ А надлишковий

   AD+ = {ADEG}     AC+ = {AC} -  символи С і  D не надлишкові.

Якби трапилася ситуація, що можна відкинути ще один символ, то треба перевірити, чи можна вилучити комбінацію.

Стратегія побудови 3 НФ.

Зробимо зворотній крок: перейдемо від одноатрибутних правих частин до багатоатрибутних.

ABC

CA

BCD

CDB

DEG

BEC

CGD

CEG

Нам потрібно перевірити, чи знаходиться реляція, яка має такі функціональні залежності, в 3 НФ, якщо ні – привести до 3 НФ.

Теорема Хіза стверджує: якщо список атрибутів А функціонально визначає список атрибутів В, то реляцію можна розкласти на дві реляції, з яких шляхом природного з’єднання можна отримати початкову реляцію без втрат.

Випишемо всі атрибути, що входять до лівої частини, а потім з наведеного списка викреслимо ті, що зустрічаються в правій частині. В нашому випадку, це список ABCDEG.

Тепер, якщо ми викреслимо всі атрибути з правої частини, то всі атрибути викресляться.

Тобто ми не можемо виділити групу атрибутів, яка визначає іншу групу атрибутів.

Ми отримали непридатну процедуру.

Побудуємо графічне представлення структури.

     A  B

 C E

D

 G

BD, CD – квазіключі.

B, C, D первинні атрибути, які належать деякому квазіключу.

AB+ = {ABCD…} – комбінуємо BD чи CD, що дає можливість отримати всі

                               AB – квазіключ

BE+ = {BECA…} – теж квазіключ

CG+ - теж  квазіключ

всі атрибути первинні реляція знаходиться в 3 НФ.

Розглянемо схематичне зображення ще однієї реляції..

Для того щоб отримати 3 НФП,  треба відсікати ієрархічні компоненти.

А В С                             F E

 D

H

K

L

G

 Піддерева

Користуючись теоремою Хіза, поетапно розкладаємо нашу реляцію:

                                   R1 (D, K, L)            R̃1 (ABCDFEHG)

                                   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)           


 

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

78485. Игра в обучении детей младшего дошкольного возраста 43.04 KB
  Игра в обучении детей младшего дошкольного возраста Отечественные учёные рассматривают игру как своеобразную форму деятельности детей дошкольного возраста. Игра занимает важное место в педагогическом процессе ДОУ и как одна из форм организации жизни детей может определять и развивать другие виды их деятельности обучение труд. Гипотеза исследования: дидактические игры и игровые упражнения повышают уровень эффективности процесса формирования словаря детей 34 лет. Совместные самостоятельные игры детей создают условия для...
78486. Педагогические условия организации сюжетно-ролевой игры в старшей возрастной группе ДОУ 42.49 KB
  Педагог учит их осуществлять игровые действия с предметами строить ролевые взаимоотношения развивать сюжетную линию игры. На современном этапе данная проблема широко рассматривается на страницах периодической печати где авторы раскрывают педагогические условия формирования сюжетноролевой игры у дошкольников. сама по себе игра и ребенок без...
78487. Ознакомление детей старшего дошкольного возраста с многозначным словом 60.56 KB
  Ознакомление детей старшего дошкольного возраста с многозначным словом В современной методике словарная работа рассматривается как целенаправленная педагогическая деятельность обеспечивающая эффективное освоение словарного состава родного языка. Объектом исследования является процесс развития словаря детей старшего дошкольного возраста. Предметом исследования ознакомление детей старшего дошкольного возраста с многозначным словом. Гипотеза исследования: Понимание и точное словоупотребление в речи смысловых оттенков слов в...
78488. Развитие речи как основа формирования культуры речевого общения старших дошкольников 44.25 KB
  Развитие речи как основа формирования культуры речевого общения старших дошкольников Культура речевого общения это такой отбор и организация языковых средств которые способствуют наиболее эффективному достижению поставленных задач в определенной сфере речевых коммуникаций с непременным учетом литературных норм. На современном этапе проблемой изучения разных направлений развития речи стало рассмотрение вопроса воспитания культуры речевого общения в дошкольном детстве М. Формирование...
78489. Специфика организации труда детей в старшей возрастной группе ДОУ 52.44 KB
  Специфика организации труда детей в старшей возрастной группе ДОУ Организация трудовой деятельности в старшей возрастной группе ДОУ одна из важных актуальных проблем на сегодняшний день в дошкольной педагогике и психологии. На современном этапе дошкольная педагогическая наука продолжает разрабатывать вопросы трудового воспитания детей дошкольного возраста. Цель исследования рассмотреть специфику организации труда детей старших дошкольников в ДОУ. Предмет исследования: изучение формирования трудовых навыков и умений у детей...
78490. Формирование культуры движений средствами аэробики у детей седьмого года жизни 39.56 KB
  Выполнение общеразвивающих движений: с высоким уровнем развития не выявлено ни в экспериментальной ни в контрольной группе. Со средним уровнем в экспериментальной группе 80 в контрольной группе 70 с низким уровнем в экспериментальной 20 контрольной 30. Развитие гибкости при подсчете общего среднего показателя выявлено в экспериментальной группе 2 25 см в контрольной группе 23 см. В экспериментальной группе он составил 22 балла в контрольной группе 2 балла.
78491. Сотрудничество ДОУ и семьи как основа формирования здоровья детей старшего дошкольного возраста 58.67 KB
  Сотрудничество ДОУ и семьи как основа формирования здоровья детей старшего дошкольного возраста Проблема воспитания и развития здорового ребенка в современных условиях является как никогда актуальной. На современном этапе проблемой физкультурно-оздоровительной работы в ДОУ с привлечением родителей занимаются В. Была сформулирована цель исследования создание теоретически обоснованной и экспериментально апробированной модели процесса сотрудничества педагогов ДОУ и родителей с целью формирования здоровья растущего ребенка на...
78492. Формирование морально-ценностного отношения к окружающей природе у детей старшего дошкольного возраста 42.34 KB
  Формирование морально-ценностного отношения к окружающей природе у детей старшего дошкольного возраста Формирование морально-ценностного отношения к природе у детей дошкольного возраста важная необходимая область теории воспитания и обучения актуальность которой диктуется современными условиями. Объект исследования: процесс экологического воспитания детей дошкольного возраста. В исследовании принимало участие 12 детей старшей группы...
78493. Влияние дидактических игр природосодержащего характера на формирование системы экологических знаний детей старшего дошкольного возраста 58.8 KB
  Влияние дидактических игр природосодержащего характера на формирование системы экологических знаний детей старшего дошкольного возраста Взаимосвязь игровой деятельности детей с формированием представлений о природе вопрос малоисследованный в науке. Между тем можно предположить что включение игровых элементов в процесс обучения позволит сформировать у дошкольников представление об окружающем мире станет эффективным средством экологического воспитания научит детей бережному отношению к природе что актуально на сегодняшний день....