Работа с базами данных 2 (стр. 7 из 18)

4) Повторение шагов 2) и 3) для каждого нового отношения, построенного в результате декомпозиции.

Разбиение отношения на два отношения на шаге 2) осуществляется по следующему правилу.

Пусть отношение

не находится в НФБК. Определяется ФЗ, например, , которое является причиной того, что r не находится в НФБК, т.е. С является детерминантом но не является возможным ключом.

Создаются два новых отношения,

и , где зависимая часть была выделена из отношения и опущена при формировании отношения r1, и полностью использована при формировании отношения r2. Теперь нужно проверить, находится ли полученное отношение в НФБК. Про отношение говорят, что оно является проекцией отношения r. Этот тип декомпозиции называется декомпозицией без потерь.

На этом же этапе должно быть принято решение, какую ФЗ выбрать для проведения первой проекции. Не исключено, что в итоге выбора той или иной I (начальной) проекции будут получены разные БД. Простым правилом выбора …

, с последующим использованием для I проекции правой зависимости ( ). Если таких цепочек нет, то безразлично, с чего начинать.

Это правило можно сформулировать и так: следует избегать выбора ФЗ, правая часть которой сама (целиком или частично), является детерминантом другой ФЗ.

Отношение, получаемое в результате декомпозиции, должно удовлетворять требованиям:

1) Возможность восстановить в точности исходное отношение путем естественного соединения отношений — результатов декомпозиции;

2) Сохранение всех ФЗ исходного отношения.

Пусть в отношении r со схемой R имеется множество ФЗ. Говорят, что схема R разложима без потерь на отношения

с сохранением ФЗ, если для любого кортежа . Кортеж может быть восстановлен

соединением его проекций. Невыполнение этих требований приведет к получению набора отношений, порождающих не согласующиеся данные.

Условия разложения без потерь:

а) для разложения, состоящего из двух отношений. Если отношение R1 и R2 являются разложением с сохранением множества ФЗ, это разложение обеспечивает соединение без потерь, если

либо . Здесь операции " Ç " и " – " определены над списками атрибутов отношений. Это правило можно сформулировать по-другому: отсутствие потерь при декомпозиции гарантируется, если от общего атрибута двух получаемых отношений зависит хотя бы один атрибут из двух оставшихся.

б) для разложения, состоящего более чем из двух отношений (метод табло). Процедура состоит в построении таблицы, строками которой являются имена, полученные при декомпозиции отношений, а столбцы — список атрибутов

этих отношений без повторений. Таблица заполняется символами , если элемент i-й строки в j-м столбце соответствует атрибуту Aj в отношении Ri, в противном случае ничего не ставится. После заполнения таблицы следует итеративный просмотр всех ФЗ . Если для атрибутов из Х найдутся строки, где в соответствующих местах стоят aj, то пустые элементы этих строк, соответствующие столбцам атрибутов из Y, заменяются на aj*. Если в результате появится строка таблицы, заполненная полностью aj и aj*, то данное соединение без потерь. В противном случае — с потерями.

Метод декомпозиции применим для задач с малым числом атрибутов и отношений.

2.1.2 Метод синтеза

Отметим еще одно важное правило, лежащее в основе метода синтеза.

Все ФЗ с одинаковыми детерминантами нужно выделять в одну группу и каждой такой группе отводить свои собственные отношения. Получаемые отношения проверяются на соответствие с НФБК.

Этот прием следует применять в том случае, когда использование метода декомпозиции может привести к потере ФЗ, например, при выделении из

зависимости будут получены отношения и , ни одно из которых не будет содержать зависимость . В этом случае метод декомпозиции не работает.

Правильно (метод синтеза):

,

Использование описанного выше правила декомпозиции может быть осложнено присутствием избыточных ФЗ (ИФЗ).

ИФЗ — зависимость, не заключающая в себе такой информации, которая не могла бы быть получена на основе других зависимостей, использованных при проектировании БД.

Поскольку ИФЗ не содержит уникальной информации, она может быть удалена из набора ФЗ. ИФЗ удаляется до начала проектирования (т.е. декомпозиции).

Возникновение ИФЗ связано с:

a) наличием транзитивных зависимостей;

b) добавлением.

Пример:

a) Исходный набор ФЗ После удаления ИФЗ

b) Эта форма избыточности имеет несколько видов:

1) Если

, то является правильной, но избыточной;

2) Если

, то избыточна.

Рассмотренные ПВ ФЗ из исходных ФЗ входят в состав так называемых аксиом вывода (АВ).

АВ — правило, согласно которому, если отношение удовлетворяет определенным ФЗ, то оно должно удовлетворять и другим определенным ФЗ.

Рассмотрим 6 основных правил вывода (АВ).

1) Рефлексивность. А®А,

2) Добавление (расширение)

а) если А®В, то А,С®В

б) если А-В, то А, С - В,С ИФЗ

3) Транзитивность. Если А®B и B®C, то А®С ИФЗ

4) Псевдотранзитивность. Если А®B и B,С®D, то А,С®D ИФЗ

5) Объединение (аддитивность). Если А®B и А®С, то А®В,С

6) Декомпозиция (проективность). Если А®В,С, то А®B и А®С

Используя аксиомы вывода f1-f6 можно получить другие правила вывода для ФЗ. Например, с использованием аксиом f1 и f2 можно получить A,B®B. Первые три аксиомы называются аксиомами Армстронга, оставшиеся три следуют из них. Использование полной системы аксиом позволяет вывести все функциональные зависимости, допустимые в множестве ФЗ. Пусть F – множество ФЗ для схемы отношений R. Множество ФЗ, которые логически следуют из F, называют замыканием F (F+). Если F=F+, то говорят, что F — полное семейство зависимости. Вычисление F+ для F являются трудоемкой задачей, поскольку мощность F+ может быть велика даже при небольшой мощности F. Вычисление же X+ для данного множества атрибутов Х не представляет трудности. Х+— это замыкание Х относительно F, если есть множество атрибутов А таких, что зависимость Х®А может быть выведена из F по аксиомам f1,f2, f4.

2.1.3 Метод объектной связи

Отличается от метода декомпозиции тем, что ФЗ привлекаются не на начальном, а на конечном этапе проектирования.

Предположим, что проектируется БД, предназначенная для хранения информации о преподавателях и курсах, которые они читают. Двумя главными сущностями здесь являются преподаватель и курс. Они соотносятся с помощью связи "читает", что позволяет нам сказать "преподаватель читает курс". Связь "читает" может быть представлена двумя способами.

1) Метод ER-диаграмм в ER-экземплярах;

2) Метод ER-типов.

1) 2)

Необходимо различать понятия сущности и отношения. Сущность переходит в отношение путем выделения ее из ER-диаграмм. Отсюда различие между ключом сущности и ключом отношения, они не всегда совпадают. В процессе перехода сущность ® отношение ключ сущности может быть дополнен некоторым атрибутом и стать ключом отношения. В большинстве случаев для определения набора отношений используется диаграмма ER-типа (вторая схема).