Неизбыточные покрытия

End.

Begin

End.

Begin

v:= истина

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

v:= v and MEMBER(F, );

return (v)

Функция EQUIV алгоритма 2 проверяет эквивалентность двух множеств F-зависимо­стей.

Алгоритм 2. EQUIV

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

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

EQUIV (F,G)

v:= DERIVES(F,G) and DERIVES(G,F);

return (v)

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

Пример. Пусть . Множество эквивалентно G, но избыточно, потому что F’=является покрытием G. Множество F’ представляет собой неизбыточное покрытие.

По равносильной характеристике неизбыточности множество F неизбыточно, если в нем не существует F-зависимости , такой, что . Назовем F-зависимость из F избыточной в F, если . Это свойство положено в основу алгоритма 5.3 проверки избыточности F.

Алгоритм 3. REDUNDANT

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

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

REDUNDANT (F)

Дата добавления: 2014-01-11