Предыдущая страница реферата | 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 редуцирована
(соответственно слева, справа).

D} редуцировано слева и справа, следовательно, поскольку правые части не пусты, редуцировано.

Для нахождения редуцированных покрытий используется алгоритм:

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 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки