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

Алгоритм 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[pic] end end return(F) end

Пример. Пусть G’= {A -> C, AB -> DE, AB ->CDI, AC -> J}.Из J} и из J}, уже редуцированное.

Далее потребуется находить разбиение множества F- зависимостей, заданных на отношении R на подмножества, которые представляют собой классы F- зависимостей с эквивалентной левой частью.

Определение: два множества атрибутов X и Y называются эквивалентными на множестве F- зависимостей F, если F |= X->Y и F |= Y ->X.

Например пусть дано F={A -> BC, B -> A, AD -> E}, найдем все F- зависимости эквивалентные левой части первой, т.е. А. Левая часть второй B и F |= B -> A .
Это действительно так. Следовательно А эквивалентно В и первые две F- зависимости можно объединить в один класс эквивалентности, который обозначается в общем случае ЕА(Х). Множество классов эквивалентности для заданного множества F- зависимостей обозначается [pic]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.

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





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