Лекции по теории проектирования баз данных (БД) — страница 4

Алгоритм MEMBER. Вход: Множество F-зависимостей F и F-зависимость X -> Y. MEMBER(F, X -> Y) begin if Y CLOSURE(X,F) then return (истина) else return(ложь) end Здесь CLOSURE алгоритм, позволяющий выявить список атрибутов входящих в множество F, который имеет вид. Алгоритм CLOSURE. Вход: Множество атрибутов Х и множество F-зависимостей F. Выход: Замыкание Х над F. CLOSURE(X,F) begin OLDDEP = 0; NEWDEP = X while NEWDEP OLDDEP do begin OLDDEP = NEWDEP for каждая F- зависимость W -> Z в F do if NEWDEP W then NEWDEP = NEWDEP Z end return(NEWDEP) end

Пример работы алгоритма MEMBER Пусть F = {НОМЕР_РЕЙСА ДАТА_ВЫЛЕТА -> КОЛИЧЕСТВО_МЕСТ, НОМЕР_РЕЙСА -> ПУНКТ_ОТПРАВЛЕНИЯ, НОМЕР_РЕЙСА ДАТА_ВЫЛЕТА -> ПИЛОТ} и необходимо установить F |= НОМЕР_РЕЙСА -> ПИЛОТ Используем для этого алгоритм MEMBER Покрытия функциональных зависимостей Для формирования БД, как системы взаимосвязанных отношений на основании известных (из семантических соображений) F-зависимостей необходимо иметь способ

минимизации первоначального множества F-зависимостей. Это необходимо для минимизации дублирования данных, обеспечения их согласованности и целостности. Теоретической основой для построения такого способа является теория покрытий функциональных зависимостей. Определение. Два множества F-зависимостей F и G над отношением R эквивалентны, , если F+ = G+ . Если покрытие для G. Предполагается, что имеет смысл рассматривать в качестве

покрытий такие множества F, которые не превосходят множество G по числу F-зависимостей. Из этого определения следует, что для установления факта, что множество функциональных зависимостей F является покрытием G , необходимо определить эквивалентность F и G. Практически это достигается путем использования следующего алгоритма: Алгоритм EQUIV Вход: два множества F- зависимостей F и G. Выход: истина, если EQUIV(F,G) begin v=DERIVES(F,G) and DERIVES(G,F); return(v)

end Здесь 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’ Пример. Пусть G = { AB -> C, A -> B, B -> C, A -> C}. Множество F= {AB -> C, A -> B, B -> C} эквивалентно G, но

избыточно, потому что F’ = {A -> B, B -> C} также является покрытием G. Множество F’ представляет собой не избыточное покрытие G. Действительно, согласно алгоритму EQUIV , так как 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.