Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Минимальное покрытие множества функциональных зависимостей




 

Определение 6.7. Покрытие множества FD

Множество FD S2 называется покрытием множества FD S1, если любая FD, выводимая из S1, выводится также и из S2. Конец определения.

Легко заметить, что S2 является покрытием S1 тогда и только тогда, когда S1+ Í S2+. Два множества FD S1 и S2 называются эквивалентными, если каждое из них является покрытием другого, т.е. S1+ = S2+.

 

Определение 6.8. Минимальное множество FD

Множество FD S называется минимальным в том и только в том случае, когда удовлетворяет следующим свойствам:

a) правая часть любой FD из S является множеством из одного атрибута (простым атрибутом);

b) детерминант каждой FD из S обладает свойством минимальности; это означает, что удаление любого атрибута из детерминанта приводит к изменению замыкания S+, т.е. порождению множества FD, не эквивалентного S.*

c) удаление любой FD из S приводит к изменению S+, т.е. порождению множества FD, не эквивалентного S. Конец определения.

 

Чтобы продемонстрировать минимальные и не минимальные множества FD, вернемся к примеру отношения СЛУЖАЩИЕ_ПРОЕКТЫ {СЛУ_НОМ,СЛУ_ИМЯ,СЛУ_ЗАРП, ПРО_НОМ, ПРОЕКТ_РУК}с рис. 6.1. Если считать, что единственным возможным ключом этого отношения является атрибут СЛУ_НОМ, то множество FD {СЛУ_НОМ® СЛУ_ИМЯ, СЛУ_НОМ ® СЛУ_ЗАРП, СЛУ_НОМ ® ПРО_НОМ, СЛУ_НОМ ® ПРОЕКТ_РУК, ПРО_НОМ ® ПРОЕКТ_РУК} является минимальным. Действительно, в правых частях FD этого множества находятся множества, состоящие ровно из одного атрибута; каждый из детерминантов тоже является множеством из одного атрибута, удаление которого, очевидно, недопустимо; удаление каждой FD явно приводит к изменению замыкания множества FD, поскольку утрачиваемая информация не выводится с помощью аксиом Армстронга.

 

С другой стороны, множества FD

 

(*) {СЛУ_НОМ® {СЛУ_ИМЯ, СЛУ_ЗАРП},СЛУ_НОМ® ПРО_НОМ, СЛУ_НОМ ® ПРОЕКТ_РУК, ПРО_НОМ ® ПРОЕКТ_РУК},

 

(**) { СЛУ_НОМ® СЛУ_ИМЯ, { СЛУ_НОМ, СЛУ_ИМЯ} ® СЛУ_ЗАРП, СЛУ_НОМ ® ПРО_НОМ, СЛУ_НОМ ® ПРОЕКТ_РУК, ПРО_НОМ ® ПРОЕКТ_РУК} и

 

(***) { СЛУ_НОМ ® СЛУ_НОМ, СЛУ_НОМ ® СЛУ_ИМЯ, СЛУ_НОМ ® СЛУ_ЗАРП, СЛУ_НОМ ® ПРО_НОМ, СЛУ_НОМ ® ПРОЕКТ_РУК, ПРО_НОМ ® ПРОЕКТ_РУК}

 

не являются минимальными. Для множества (*) в правой части первой FD присутствует множество из двух элементов. Для множества (**) удаление атрибута СЛУ_ИМЯиз детерминанта второй FD не меняет замыкание множества FD. Для множества (***) удаление первой FD не приводит к изменению замыкания. Эти примеры показывают, что для определения минимальности множества FD не всегда требуется явное построение замыкания этого множества.

 

Интересным и важным является тот факт, что для любого множества FD S существует (и даже может быть построено) эквивалентное ему минимальное множество S-.

 

Приведем общую схему построения S- по заданному множеству FD S. Во-первых, используя правило (5) (декомпозиции), мы можем привести множество S к эквивалентному множеству FD S1, правые части FD которого содержат только одноэлементные множества (простые атрибуты). Далее, для каждой FD из S1, детерминант D { D1, D2, …, Dn } которой содержит более одного атрибута, будем пытаться удалять атрибуты Di, получая множество FD S2. Если после удаления атрибута Di S2 эквивалентно S1, то этот атрибут удаляется, и пробуется следующий атрибут. Назовем S3 множество FD, полученное путем допустимого удаления атрибутов из всех детерминантов FD множества S1. Наконец, для каждой FD f из множества S3 будем проверять эквивалентность множеств S3 и S3 MINUS { f }. Если эти множества эквивалентны, удалим f из множества S3, и в заключение получим множество S4, которое минимально и эквивалентно исходному множеству FD S.

 

Пусть, например, имеется отношение r { A, B, C, D }, и задано множество FD S = { A ® B, A ® BC, AB ® C, AC ® D, B ® C }. По правилу декомпозиции S эквивалентно множеству S1 { A ® B, A ® C, AB ® C, AC ® D, B ® C }. В детерминанте FD AC ® D можно удалить атрибут C, поскольку по правилу дополнения из FD A ® C следует A ® AC; по правилу транзитивности выводится FD A ® D, и поэтому атрибут C в детерминанте FD AC ® D является избыточным. FD AB ® C может быть удалена, поскольку может быть выведена из FD A ® C (по правилу пополнения из этой FD выводится AB ® BC, а по правилу декомпозиции далее выводится AB ® C). Наконец, FD A ® C тоже выводится по правилу транзитивности из FD A ® B и B ® C. Итого, мы получаем множество зависимостей { A ® B, A ® D, B ® C }, которое является минимальным и эквивалентно S по построению.

 

Определение 6.9. Минимальное покрытие множества FD

 

Минимальным покрытием множества FD S называется любое минимальное множество FD SI, эквивалентное S. Конец определения.

 

Поскольку для каждого множества FD существует эквивалентное минимальное множество FD, у каждого множества FD имеется хотя бы одно минимальное покрытие, причем для его нахождения не обязательно находить замыкание исходного множества.

 




Поделиться с друзьями:


Дата добавления: 2014-01-03; Просмотров: 475; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.01 сек.