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)           


 

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

48545. ГЕОГРАФИЧЕСКИЕ ИНФОРМАЦИОННЫЕ СИСТЕМЫ И БД 2.06 MB
  Сергей Щербина Общие сведения о ГИС Большинство используемых данных с которыми работают информационные системы имеют пространственную привязку географические координаты т. Сервисы Google Mps и Google Erths фактически представляющие собой базовую инфраструктуру геоданных продемонстрировали потенциал уже завоевавших популярность географических информационных систем ГИС. Простота ввода и агрегации данных с помощью сервиса Google Erth позволяет видеть в нем прообраз ГИС будущего простых в использовании открытых сред.
48546. БАЗЫ ДАННЫХ КАК ОСНОВА ДЛЯ ПОДДЕРЖКИ РЕШЕНИЙ 524.21 KB
  Сферы Воздух Вода Земля Био Количественные сведения о состоянии природной среды Наблюдения Диагноз Прогноз Климат После явления Сведения об объекте Перечень воздействий ЛПР Качественные сведения о ситуации время года климатический район тип объекта уровень принятия решений ЭММ Перечень рекомендаций Объект Оперативные Тактические Стратегические XII. БАЗЫ ДАННЫХ КАК ОСНОВА ДЛЯ ПОДДЕРЖКИ РЕШЕНИЙ Проблемы поддержки решений в современных условиях Роль информации при принятии решений Принципы создания СППР Выявление знаний Примеры...
48547. Перспективы развития БД 3.17 MB
  Перспективы развития БД Развитие компьютерной техники Развитие ядра СУБД Развитие внешнего окружения Развитие средств работы с БД Развитие моделей данных Сенсорные сети Технологии обслуживания нового поколения Развитие компьютерной техники За последние 25 лет тактовая частота процессоров возросла с МГц до ГГц оперативная память с нескольких сотен Кбайт до Гигабайт а память на дисках со 100 Мбайт до Тбайт и более. Рабочая нагрузка типового компьютера будущего потребует обработки Тбайт данных и производительности на терафлопном уровне....
48548. Базы данных. Модели данных 1.19 MB
  В настоящее время, а тем более в будущем, в условиях широкой информатизации общества все большее распространение будут получать справочные системы, системы информационной поддержки деятельности учреждений, системы поддержки принятия решений, системы автоматизированного учета и контроля, системы автоматизированного проектирования и множество других систем на базе средств информационных и коммуникационных технологий.
48549. Старажытныя цывілізацыі 650 KB
  Крыніцы вывучэння гісторыі Беларусі. Гісторыя Беларусі вывучаецца на аснове разнастайных гістарычных крыніц. Першымі на тэрыторыю Беларусі прыйшлі фінаугорскія плямены якія раней жылі за Уралам. Больш глыбокія вынінікі для Беларусі і Еўропы мела перасяленне індаеўрапейцаў.
48550. Автоматизация подготовки документов средствами СПС 178.5 KB
  Папки в СПС КонсультантПлюс 4. История запросов СПС КонсультантПлюс Основные сведения о системе Справочная правовая система КонсультантПлюс разработчик в РБ ООО ЮрСпектр http: urspectr.info компания КонсультантПлюс г.
48551. Психодиагностика. Конспект лекций 1.01 MB
  пришел к выводу что положительная корреляция между тестами на различные способности например математические и литературные выявляет некоторый общий генеральный фактор. Позднее распространилась точка зрения согласно которой структуру свойств составляет ряд достаточно широких групповых факторов каждый из которых может в разных тестах иметь различный вес. Тесты достижений Наряду с тестами интеллекта специальных и комплексных способностей возник и еще один тип тестов широко применяемых в учебных заведениях тесты достижений. В данном...
48552. Философия. Мировозренческая картина мира 147.76 KB
  Возникает в глубокой древности и характеризуется следующими свойствами: образность (образное освоение реальности) и синкретизм (слитность и нерасчленённость мифологии, знаний, ценностей). В мифе человек неразрывно сливается с природой. Мифологическое представление – это не столько знания, а реальность, в которой живёт человек.
48553. СОВОКУПНЫЙ СПРОС И СОВОКУПНОЕ ПРЕДЛОЖЕНИЕ 893 KB
  Совокупный спрос модель представленная в виде кривой которая показывает различные объемы товаров и услуг то есть реальный объем национального производства который потребители производители и правительство готовы купить при любом возможном уровне цен. На оси абсцисс указываются значения реального объема производства реального ВНП. Характер этой кривой говорит о том что при повышении уровня цен объем реального объема производства будет меньше и соответственно при снижении уровня цен объем реального ВНП будет больше. Подобная...