Общий подход к декомпозиции

В общем виде алгоритм проектирования БД может выглядеть следующим образом:

1. Разработка универсального отношения для БД.

2. Определение всех ФЗ между атрибутами отношения.

3. Определение того, находится ли отношение в НФБК. Если да, проектирование завершается; если нет, отношение должно быть разложено на два отношения.

4. Повторение шагов 2 и 3 для каждого нового отношения, полученного в результате декомпозиции. Проектирование завершается, когда все отношения будут находится в НФБК.

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

Пусть отношение R(A,B,C,D,E,...) не приведено к НФБК. Определяется ФЗ, например, С -> D, про которую известно, что она является причиной того, что отношение R не находится в НФБК (С является детерминантом, но не является возможным ключом).

Создается два новых отношения: R1(A,B,C,E,...) и R2(C,D), где зависимостная часть ФЗ была выделена из R и опущена при формировании отношения R1 и ФЗ была использована полностью при формировании отношения R2. Теперь необходимо проверить, находятся ли в НФБК отношения R1 и R2. Про отношение R2(C,D) говорят, что одно является проекцией отношения R. Этот тип декомпозиции называется декомпозицией без потерь при естественном соединении. Указанный метод декомпозиции может быть использован на шаге 3 приведенного выше алгоритма проектирования.

В качестве примера использования метода выполним декомпозицию отношения УСПЕВАЕМОСТЬ. Обращаясь вновь к детерминантам и возможным ключам отношения УСПЕВАЕМОСТЬ, видим, что имеются три детерминанта, не являющихся возможными ключами: <Сном>, <Тном> и <Кном>

Кандидатами среди ФЗ для осуществления проекции являются: Сном -> Кном; Сном -> Тном; Кном -> Тном и Тном -> Кном.

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

 Простым правилом выбора ФЗ для проекции может служить поиск "цепочки" вида А -> В -> С с последующим использованием для проекции крайней правой зависимости. В нашем случае такой "цепочкой" является Сном -> Кном -> Тном и "конец цепочки" Кном -> Тном порождает первую проекцию. Полученные в итоге отношения R1 и R2 приведены на рис.11 вместе со связанными с ними ФЗ.

R1(Cном, Д исц, Семестр, Сфам, Кном, Оценка)

Возможные ключи              Детерминанты

<Сном, Дисц, Семестр>  < Сном, Дисц, Семестр >

                                           < Сном >

R2(Кном, Тном)

Возможные ключи              Детерминанты

< Кном >                                < Кном >

< Тном >                                 < Тном >

Рис.11. Отношения R1 и R2 получены в результате проекции Кном <-> Тном  из отношения УСПЕВАЕМОСТЬ.

Отношение R2(Кном, Тном) находится в НФБК, поскольку все его детерминанты являются возможными ключами и оно не нуждается более в декомпозиции. Первичным ключом отношения R2 могут быть как Кном, так и Тном. Отношение R1 не находится в НФБК, т.к. детерминант <Сном> не является возможным ключом.

Следовательно отношение R1 необходимо подвергнуть дальнейшей декомпозиции.

 Детерминант <Сном> имеет два зависимых от него атрибута Сном -> Сфам, Сном -> Кном, что можно рассматривать в качестве единичной ФЗ с составной правой частью Сном -> Сфам, Кном.

Проекция отношения R1, порождаемая этой ФЗ приводит к получению отношений R3 и R4, показанных на рис.12. Эти два отношения находятся в НФБК и вместе с отношением R2 могут использоваться при формировании БД для учета успеваемости.

               R3(Сном, Дисц, Семестр, Оценка)

Возможные ключи                     Детерминанты

<Сном,Дисц.,Семестр>        < Сном,Дисц.,Семестр >

               R4(Сном, Сфам, Кном)

Возможные ключи                     Детерминанты

        <Сном>                                     <Сном>

Рис.12. Отношение R3 и R4 полученные в результате проекции

На рис.13 представлен окончательный   вид отношений для такой БД (названной УСПЕХИ), а также экземпляры каждого отношения с данными, совпадающими с использованными для исходного отношения УСПЕВАЕМОСТЬ. Заметим, в частности, что в процессе декомпозиции автоматически произошло разбиение исходного отношения УСПЕВАЕМОСТЬ на три логических компонента: R2, в котором содержится информация о комнатах и телефонах; R3, в котором содержится информация об учебных дисциплинах и полученных студентами оценках; R4, в котором содержится информация о студентах. Такое логическое разбиение является прямым результатом использования в процессе декомпозиции заложенной в ФЗ информации, детализирующей то, как различные атрибуты в исходном отношении соотносятся друг с другом.

R2(Кном, Тном)

R3(Сном, Дисц, Семестр, Оценка)

R4(Сном, Сфам, Кном)

 

                     а)

   УСПЕХИ

R3                                                                   R2

Сном	Дисц	Сем	Оценка		Кном	Тном
111	ВМ	3	2		120	2135
111	ТМ	2	4		211	3257
111	Физика	3	5		301	3589
222	ВМ	3	4		201	3290
222	Химия	1	5		401	5452
222	ВТ	4	4	R4
333	ТМ	2	5	Сном	Сфам	Кном
110	ВМ	1	4	111	Серов	120
				222	Перов	211
				333	Иванов	301
				110	Поляков	201
				444	Белов	401

                                          б)

Рис.13. а - база данных УСПЕХИ; б - экземпляр БД в котором используются данные, приведенные на рис.8,а

Анализ исходных аномалий

Зададимся вопросом: присутствует ли в БД УСПЕХИ те же аномалии, которые характеризовали отношение УСПЕВАЕМОСТЬ, или декомпозиция автоматически привела к их устранению? Для того, чтобы подтвердить устранение аномалий, а именно эта цель ставилась в первую очередь при осуществлении декомпозиции, рассмотрим, опираясь на приведенную на рис.13  БД УСПЕХИ, проблемы вставки, удаления и обновления.

Вставка. Когда отношение УСПЕВАЕМОСТЬ служило основой БД, новый студент не мог быть в нее включен до действительного завершения им хотя бы одного семестра. В БД УСПЕХИ информация общего характера о студентах хранится в отношении R4. Как только новый студент принимается в институт и ему отводится комната, так этот студент может быть включен в БД (в R4). Студенту даже нет необходимости просто приступить к посещению занятий для того, чтобы быть включенным в БД. Таким образом, исходная аномалия вставки исключена с помощью декомпозиции.

Обновление. В исходном отношении УСПЕВАЕМОСТЬ попытка изменить номер телефона Серова, проживающего в комнате 120 может привести к тому, что в БД появится два различных телефонных номера, установленного в комнате 120. В БД УСПЕХИ телефонные номера располагаются в отношении R2 и каждая комната может иметь только один телефонный номер. Следует помнить, что Кном является первичным ключом отношения R2, а значения первичного ключа по определению должны быть уникальными. Для изменения телефонного номера Серова следует в кортеже отношения R2, в котором Кном=120, изменить номер Тном. При этом будет изменен номер телефона для всех студентов, живущих в этой комнате. Таким образом, исходная аномалия обновления устраняется с помощью НФБК-проектирования.

Необходимо еще раз подчеркнуть, что устранение аномалии обновления базируется на том положении, что СУБД, в среде которой будет создаваться БД, не допускает дублирования значений первичных ключей.

Удаление. Когда отношение УСПЕВАЕМОСТЬ использовалось в качестве БД, удаление кортежа включавшего значения Сном=110 и Дисц. ВМ, привело к исчезновению из БД студента с номерами 110. Этого не может произойти в случае БД УСПЕХИ, поскольку информация о студентах общего характера разнесена в два различных отношения (R3 и R4). При исключении из отношения R3 кортежа <110,ВМ,1,4>, общая информация о студенте, хранимая в R4, останется.

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