Лекции по теории проектирования баз данных (БД)
Категория реферата: Рефераты по информатике, программированию
Теги реферата: шпоры по философии, доклад на тему культура
Добавил(а) на сайт: Сурнин.
Предыдущая страница реферата | 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 | Следующая страница реферата