Реферат: Лекции по теории проектирования баз данных (БД)
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. Не существует базы данных с меньшим числом отношений, удовлетворяющим пунктам 1 и 2.
4. Соединение всех полученных отношений Ri дает исходное отношение R.
Алгоритм порождающий базу данных из заданных F-зависимостей называется алгоритмом синтеза.
Определение. Если R – база данных и на ней задано множество F-зависимостей G, то в ней существует по крайней мере |EG | отношений. Это означает, что в R столько же отношений, сколько и классов эквивалентности. Из этого следует следующее.
Пусть F - множество F – зависимостей. Любая база данных должна иметь |EF ’ | отношений, где F’ неизбыточное покрытие для F.
Исходя из этого строится способ построения структуры базы данных.
Сначала находится неизбыточное покрытиеF’ для F и в EF ’ вычисляем классы эквивалентности. Для каждого EF ’ (X) строим отношение, состоящее из всех атрибутов, появляющихся в EF ’ (X). При этом атрибуты левой части каждого класса эквивалентности образуют выделенный ключ.
Реализация этого способа позволяет получить алгоритм SYNTHESIZE
Вход: множество F – зависимостей F над R.
Выход: полная схема баз данных для F.
1. Наити для F редуцированное минимальное покрытие G.
2. 
Для каждой CF – зависимости (X1 ,X2 ,…,Xk ) Y из G построить отношение Rj = X1 X2 …Xk Y с выделенными ключами K={X1 ,X2 ,…Xk ).
3. Вернуться к п. 2.
Пример.
A B1 B2 C1 C2 DEI1 I2 I3 J
B1 B2 C1 AC2 DEI1 I2 I3 J