RIGHTRED(G)

begin

F = G

for каждая зависимость X -> Y из G do

for каждый атрибут А из Y do

if MEMBER(F - {X -> Y} {X ->(Y - A)}, X -> A) then

удалить А из Y в X -> Y из F

end

end

return(F)

end

Алгоритм LEFTRED

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

Выход: редуцированное слева покрытие G.

Begin

F = G

for каждая зависимость X -> Y из G do

for каждый атрибут А из Х do

if MEMBER(F,{X - A) -> Y) then

удалить А из X в X -> Y из F

end

end

return(F)

end

Пример. Пусть G’= {A -> C, AB -> DE, AB ->CDI, AC -> J}.Из LEFTRED(G’) получаем G” = {A -> C, AB -> DE, AB -> CDI, A -> J} и из RIGHTRED(G”) получаем F= {A -> C, AB -> E, AB -> DI, A -> J}, уже редуцированное.

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

Определение: два множества атрибутов X и Y называются эквивалентными на множестве F- зависимостей F, если F |= X->Y и F |= Y ->X.

Например пусть дано F={A -> BC, B -> A, AD -> E}, найдем все F- зависимости эквивалентные левой части первой, т.е. А. Левая часть второй F- зависимости (В) эквивалентна А ? Проверим F |= A -> B и F |= B -> A . Это действительно так. Следовательно А эквивалентно В и первые две F- зависимости можно объединить в один класс эквивалентности, который обозначается в общем случае Е_А(Х). Множество классов эквивалентности для заданного множества F- зависимостей обозначается _F . Сокращенным способом записи F- зависимостей с эквивалентными левыми частями является составная функциональная зависимость (CF-зависимость), которая имеет вид:

(X₁, X₂, ..., X_k) -> Y

где X₁, X₂, ..., X_k , множество эквивалентных левых частей F- зависимостей, а Y объединение правых частей F- зависимостей.