Студопедия

КАТЕГОРИИ:


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

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




 

Рассмотрим некоторые методы представления множеств F-зависимостей. Например, любая F-зависимость, выводимая из множеств , также выводима из множества , поскольку все F-зависимости из F мо­гут быть выведены из F-зависимостей, принадлежащих G. По какой причине предпочтительнее более короткие представления?

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

В системах баз данных F-зависимости способствуют обеспечению согласованности и целостности баз данных. Меньшее число F-зависимостей означает меньший объем исполь­зуемой памяти и меньшее количество проверок при модификации баз данных.

 

Определение 1. Два множества F-зависимостей F и G над схемой R эквивалентны, , если . Если , то F есть покрытие G.

В определении для покрытия нет упоминания об относительных размерах F и G. Однако далее рассматриваются покрытия частного вида, в которых F не превосходит G по числу F-зависимостей.

Если , то, поскольку , для каждой зависимости из следует .

В частности, для каждой F-зависимости из G имеет место . Обобщим понятие выводимости на множество F-зависимостей, записав это условие в виде . Поскольку определение эквивалентности симметрично относительно F и G, из сле­дует .

Так как включает каждую F-зависимость , такую, что , то из следует . Применяя операцию замыкания к обеим частям неравенства, полу­чаем . Аналогично влечет за собой . Таким образом, дока­зана

Лемма 1. Для заданных множеств F-зависимостей F и G над схемой R тождество имеет место тогда и только тогда, когда и .

Пример 1. Множества и эквивалентны. Множество F не эквивалентно множе­ству G¢ , поскольку соотношение G¢ |= CD E не выполняется.

Лемма 1 содержит простой способ проверки эквивалентности двух множеств F-зави­симостей. Функция DERIVES проверяет условие .

Алгоритм 1. DERIVES

Вход: два множества F-зависимостей F и G.

Выход: истина, если ; ложь в противном случае.

DERIVES (F,G)




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


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


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



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




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