Студопедия

КАТЕГОРИИ:


Архитектура-(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)

Оптимальное покрытие




Редуцированное покрытие

Минимальное покрытие

На этапе проектирования реляционных баз данных наибольший интерес представляют минимальные покрытия, поскольку именно на них чаще всего и осуществляется декомпозиция отношений. Так, из двух покрытий, эквивалентных F1={A®B, A®C} и F2={A®BC}, минимальным покрытием является множество, содержащее наименьшее количество функциональных зависимостей:F2={A®BC}.

Определение 25

Минимальное покрытие это неизбыточное покрытие, содержащее наименьшее количество функциональных зависимостей.

Несмотря на то, что покрытие может быть свободно от избыточных функциональных зависимостей, оно может содержать так называемые “лишние” атрибуты, удаление которых не повлечет за собой нарушения эквивалентности вновь полученного множества функциональных зависимостей исходному множеству. Например, в множестве F={A®B, AB®C} вторая функциональная зависимость содержит “лишний” атрибут В, поскольку согласно аксиоме о псевдотранзитивности из приведенных функциональных зависимостей следует, что A®C. В свою очередь функциональная зависимость AB®C следует из A®C на основании аксиомы о пополнении.

Определение 26

Функциональная зависимость называется редуцированной слева (справа), если ее левая (правая) часть не содержит посторонних атрибутов.

Определение 27

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

Определение 28

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

Определение 29

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

Алгоритм получения редуцированного покрытия включает в себя 3 шага:

· Удаляются посторонние атрибуты из левой части функциональных зависимостей.

· Удаляются посторонние атрибуты из правой части функциональных зависимостей.

· Удаляются функциональные зависимости типа A®ø.

Покрытия могут также отличаться друг от друга числом входящих в них атрибутов. Например, минимальные покрытия F1= {ABC®D; AB®E; E®AB}. F2={AB®E; EC®D; E®AB} эквивалентны, но вхождение атрибутов в множество F2 меньше. Если не будет найдено минимальное покрытие с еще меньшим вхождением в него атрибутов, то покрытие F2 можно будет считать оптимальным.

Определение 30

Множество F зависимостей оптимально, если не существует эквивалентного множества с меньшим числом атрибутных символов.




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


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


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



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




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