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

G. REDUCE(G) begin F = RIGHTRED(LEFTRED(G)) удалить из F все F-зависимости вида X -> return(F) end здесь RIGHTRED и LEFTRED алгоритмы редуцирования соответственно справа и слева, которые имеют вид: RIGHTRED Вход: множество F-зависимостей G. Выход: редуцированное справа покрытие G. RIGHTRED(G) begin F = G for каждая зависимость X -> Y из G do for каждый атрибут А из Y do if MEMBER(F - {X -> Y} {X ->(Y - A)}, X -> A) then удалить А из Y в X -> Y из F end end return(F) end Алгоритм LEFTRED Вход: множество F-зависимостей G. Выход:

редуцированное слева покрытие G. Begin F = G for каждая зависимость X -> Y из G do for каждый атрибут А из Х do if MEMBER(F,{X - A) -> Y) then удалить А из X в X -> Y из F end end return(F) end Пример. Пусть G’= {A -> C, AB -> DE, AB ->CDI, AC -> J}.Из LEFTRED(G’) получаем G” = {A -> C, AB -> DE, AB -> CDI, A -> J} и из RIGHTRED(G”) получаем F= {A -> C, AB -> E, AB -> DI, A -> J}, уже редуцированное. Далее потребуется находить разбиение множества F- зависимостей, заданных на отношении R на подмножества, которые

представляют собой классы F- зависимостей с эквивалентной левой частью. Определение: два множества атрибутов X и Y называются эквивалентными на множестве F- зависимостей F, если F |= X->Y и F |= Y ->X. Например пусть дано F={A -> BC, B -> A, AD -> E}, найдем все F- зависимости эквивалентные левой части первой, т.е. А. Левая часть второй F- зависимости (В) эквивалентна А ? Проверим F |= A -> B и F |= B -> A . Это действительно так. Следовательно А

эквивалентно В и первые две F- зависимости можно объединить в один класс эквивалентности, который обозначается в общем случае ЕА(Х). Множество классов эквивалентности для заданного множества F- зависимостей обозначается F . Сокращенным способом записи F- зависимостей с эквивалентными левыми частями является составная функциональная зависимость (CF-зависимость), которая имеет вид: (X1, X2, ..., Xk) -> Y где X1, X2, ..., Xk , множество

эквивалентных левых частей F- зависимостей, а Y объединение правых частей F- зависимостей. Синтез реляционных баз данных База данных состоит из множества атрибутов и ключей. С точки зрения теоретико-множественного описания реляционной базой данных d называется такая совокупность отношений {R1, R2, ...,Rp}, в которой каждое отношение имеет вид Ri= (Si,Ki), где Si- множество атрибутов, а Ki - множество атрибутов образующих ключ. Предположим на

входе задано множество F- зависимостей F над R. С их помощью требуется создать базу данных R=( R1, R2, ...,Rp). Эта БД должна удовлетворять следующим требованиям: 1.      множество F полностью характеризуется с помощью R , т.е. где К – выделенный ключ Ri} 2.      Ri находится в третьей нормальной форме. 3.      4.      Ri дает исходное отношение R. Алгоритм порождающий базу данных из заданных