Лекции по теории проектирования баз данных (БД)
| Категория реферата: Рефераты по информатике, программированию
| Теги реферата: шпоры по философии, доклад на тему культура
| Добавил(а) на сайт: Сурнин.
Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 11 | Следующая страница реферата
Если F-неизбыточное множество F-зависимостей, то в нем нет “лишних” зависимостей в том смысле, что нельзя уменьшить F , удалив некоторые из них. Удаление любой F-зависимости из F приведет к множеству, не эквивалентному F. Однако размер можно уменьшить, удалив некоторые атрибуты F-зависимостей F.
Определение. Пусть F-множество F-зависимостей над R и X -> Y есть F- зависимость из F. Атрибут А из R называется посторонним в X -> Y относительно F, если
1. [pic] и (F - {X -> Y}) [pic] {Z -> Y}[pic]F или
1. Y = AW, Y[pic]W и (F - {X -> Y}) [pic] {X -> W}[pic]F.
Иными словами, А - посторонний атрибут, если он может быть удален из правой или левой части X -> Y без изменения замыкания F.
BC, а атрибут B - в левой части AB -> D. Определение. Пусть F - множество F-зависимостей над R и X -> Y принадлежит F. F-зависимость X -> Y называется редуцированной слева, если
Х не содержит постороннего атрибута А и редуцированной справа, если Y не содержит атрибута А , постороннего для X -> y. Зависимость X -> Y называется редуцированной, если она редуцирована слева и справа и Y
[pic]. Редуцированная слева F-зависимость называется также полной F- зависимостью.
Определение. Множество F-зависимостей F называется редуцированным
(слева, справа), если каждая F-зависимость из F редуцирована
(соответственно слева, справа).
Для нахождения редуцированных покрытий используется алгоритм:
REDUCE
Вход: множество F-зависимостей G.
Выход: редуцированное покрытие G.
REDUCE(G)
begin
F = RIGHTRED(LEFTRED(G)) удалить из F все F-зависимости вида X -> [pic] return(F) end
здесь RIGHTRED и LEFTRED алгоритмы редуцирования соответственно справа и слева, которые имеют вид:
RIGHTRED
Вход: множество F-зависимостей G.
Выход: редуцированное справа покрытие G.
RIGHTRED(G)
begin
F = G for каждая зависимость X -> Y из G do
for каждый атрибут А из Y do
if MEMBER(F - {X -> Y} [pic] {X ->(Y - A)}, X -> A) then
удалить А из Y в X -> Y из F[pic]
end
end
return(F) end
Рекомендуем скачать другие рефераты по теме: капитанская дочка сочинение, курсовик.
Категории:
Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 11 | Следующая страница реферата
Главная