Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата

Здесь DERIVES алгоритм проверяет условие F |= G и имеет вид:

Алгоритм DERIVES
Вход: два множества F- зависимостей F и G.
Выход: истина, если F |= G; ложь в противном случае.

DERIVES(F,G)

begin

v= истина for каждая F-зависимость X -> Y из G do v = v and MEMBER(F, X -> Y)

end return(v) end

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

B, B -> C, A -> C}. Множество F= B, B -> C} эквивалентно G, но избыточно, потому что F’ =
{A -> B, B -> C} также является покрытием G. Множество F’ представляет собой не избыточное покрытие G.

Действительно, согласно алгоритму EQUIV [pic] , так как DERIVES(F,G) дает истину и DERIVES(G,F) так же истина. То же самое можно сказать относительно F’ и G.

(Подробнее)

Множество F не избыточно, если в нем не существует F-зависимости X ->
Y, такой, что F - { X -> Y} |= X -> Y . Назовем F-зависимость из F избыточной в F , если F - { X -> Y} |= X -> Y.

Для любого множества F-зависимостей G существует некоторое подмножество F, такое, что F является не избыточным покрытием G. Если G не избыточно, то F=G. Для определения не избыточного покрытия множества F- зависимостей G существует алгоритм NONREDUN, который имеет вид:

Вход: множество F-зависимостей G.
Выход: не избыточное покрытие G.

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

C}.

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

C}.

C, B -> A , B ->
C} , то результатом работы алгоритма было бы

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

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

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

Рекомендуем скачать другие рефераты по теме: капитанская дочка сочинение, курсовик.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата