NONREDUN(G)

begin

F=G

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

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

end

return(F)

end

Пример: Пусть G= {A -> B, B -> A, B -> C, A -> C}.

Результатом работы алгоритма является множество:

{A -> B, B -> A, A -> C}.

Если бы G было представлено в порядке {A -> B, A -> C, B -> A , B -> C} , то результатом работы алгоритма было бы

{A -> B, B -> A, B -> C}.

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

F = {A -> B, B -> A, AB -> C}.

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

Определение. Пусть F-множество F-зависимостей над R и X -> Y есть F-зависимость из F. Атрибут А из R называется посторонним в X -> Y относительно F, если

и (F - {X -> Y}) {Z -> Y} F или

Y = AW, Y W и (F - {X -> Y}) {X -> W} F.

Иными словами, А - посторонний атрибут, если он может быть удален из правой или левой части X -> Y без изменения замыкания F.

Пример. Пусть G = {A -> BC,B -> C,AB -> D}. Атрибут С является посторонним в правой части A -> BC, а атрибут B - в левой части AB -> D.

Определение. Пусть F - множество F-зависимостей над R и X -> Y принадлежит F. F-зависимость X -> Y называется редуцированной слева, если Х не содержит постороннего атрибута А и редуцированной справа, если Y не содержит атрибута А , постороннего для X -> y. Зависимость X -> Y называется редуцированной, если она редуцирована слева и справа и Y . Редуцированная слева F-зависимость называется также полной F-зависимостью.

Определение. Множество F-зависимостей F называется редуцированным (слева, справа), если каждая F-зависимость из F редуцирована (соответственно слева, справа).

Пример. Множество G = {A -> BC, B -> C, AB -> D} не является редуцированным ни справа, ни слева. Множество G₁ = {A -> BC, B -> C, A -> D} редуцировано слева, но не справа, а G₂ = {A -> B, B -> C, AB -> D} редуцировано справа, но не слева. Множество G₃ = {A -> B, B -> C, A -> D} редуцировано слева и справа, следовательно, поскольку правые части не пусты, редуцировано.

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

REDUCE

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

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