Рассматриваемый метод проектирования называют декомпозиционным методом.

1.5.1 Универсальное отношение

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

Первый шаг процесса проектирования состоит в определении как всех атрибутов, наличие которых обязательно в БД, так и связей между атрибутами.

Имена и условия, связанные с атрибутами, хранение которых предполагается, определим следующим образом:

Сном: Номер студента. Целое значение, уникальное для каждого студента института.

Сфам: Фамилия студента. Каждый студент имеет только одну фамилию, но возможно, что одну фамилию носят несколько студентов.

Кном: Номер комнаты в общежитии. В одной комнате может проживать более одного студента.

Тном: Номер телефона студента. Каждая комната общежития имеет один телефон и им пользуются все студенты, проживающие в этой комнате.

Дисц: Название дисциплины. В БД будут храниться данные о дисциплинах, по которым проведена итоговая аттестация студента.

Семестр: Институтский семестр. Представляет собой семестр, в котором данная дисциплина была завершена студентом.

Возможно, что студент изучал одну и ту же дисциплину в различных семестрах.

Оценка: Оценка за дисциплину. Оценка, полученная студентом за определенную дисциплину в данном семестре.

На рис.5.1 представлена таблица с данными, которые должны хранится в БД. Хотя на рисунке приведен пример в виде таблицы данных, которые могут храниться в БД в некоторый момент времени, указанная таблица отношением не является.

Рис.5.1. Данные для размещения в БД

Для иллюстрации того, почему таблица на рис.5.1 не является отношением, выделим одну "строку" из таблицы (рис.5.2.).

Рис.5.2 Одна "строка" таблицы, приведенной на рис.5.1.

На этом рисунке значения четырех полей Сном, Сфам, Кном и Тном - атомарные (атомарным называется неделимое значение, а не множество, или кортеж, значений из некоторых доменов), в то время как значения в полях Дисциплина, Семестр и Оценка - множественные.

Данная "строка" очевидным образом отличается по форме от кортежей. Отличие в том, что не все поля строки содержат атрибуты, значения которых атомарные. Для придания данным, приведенным на рис.5.1, формы отношения необходимо реконструировать их таким образом, чтобы каждый элемент кортежа имел атомарное значение. Обычно это удается сделать с помощью простого процесса вставки (результат для данного случая показан на рис.5.3). В результате этого процесса добавляется большой объем избыточных данных - исключение избыточности достигается на следующих этапах проектирования.

Рис.5.3 Данные из таблицы, приведенной на рис.5.1, помещенные в корректное отношение.

Таблица на рис.5.3 представляет собой экземпляр корректного отношения. Его называют универсальным отношением проектируемой БД. В одно универсальное отношение включаются все представляющие интерес атрибуты, и оно может содержать все данные, которые предполагается размещать в БД в будущем. Для малых БД (включающих не более 20 атрибутов) универсальное отношение может использоваться в качестве отправной точки при проектировании БД.

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

1.5.2 Проблемы, вызываемые использованием универсального отношения

Существует несколько причин, почему не следует использовать универсальное отношение в качестве единственного в БД. Различают три специфические проблемы: проблема, связанная с обновлением (модификацией) данных в БД; проблема, обусловленная необходимостью удаления кортежей; проблема, обусловленная необходимостью включения новых кортежей. Выделенные проблемы обычно называют аномалиями обновления, удаления и вставки, понимая под аномалией отклонение от нормы.

Проблема вставки

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

На рис.5.4,а показан пример того, как будет выглядеть отношение УСПЕВАЕМОСТЬ в случае принудительного включения в него информации о студенте, не завершившем изучение ни одной дисциплины.

Рис.5.4. а- результат вставки записи с пустыми полями; б- ошибочный результат выполнения запроса, вызванный наличием пустых полей.

Пустые символьные строки представляются пробельными полями (Дисциплина и Семестр), в то время как нулевые численные значения в поле Оценка интерпретируются как 0.

Рис.5.4,б иллюстрирует возможные последствия появления 0.0 при отсутствии информации. Получен ответ на запрос "Выдать список Сном и Сфам всех студентов, получивших хотя бы одну оценку ниже 3.0". В число таких студентов попал Белов, хотя он не закончил изучение ни одной дисциплины.

Проблемы обновления

В отношении УСПЕВАЕМОСТЬ большое число избыточных данных. Она характеризуется как явной, так и неявной избыточностью. Явная избыточность заключается в том, что фамилия данного студента, номер комнаты и номер телефона могут появляться в отношении несколько раз.

Неявная избыточность обнаруживается в том, что один и тот же номер телефона имеют все студенты, живущие в одной комнате.

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

Проблемы удаления

В экземпляре отношения УСПЕВАЕМОСТЬ (рис.5.4) присутствует только один кортеж, в котором Сном=110. Этот кортеж соответствует студенту с фамилией Поляков.

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

1.5.3 Нормальная форма Бойса -Кодда

Приведенное на рис.5.3. универсальное отношение находится в первой нормальной форме (1НФ).

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

Функциональные зависимости

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

Ключевым для осуществления декомпозиции является понятие функциональных зависимостей между атрибутами в рассматриваемом отношении.

Функциональная зависимость (ФЗ) определяется следующим образом:

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

С практической точки зрения смысл данного определения состоит в том, что если В функционально зависит от А, то каждый из кортежей, имеющих одно и то же значение А, должен иметь также одно и то же значение В. Значение А и В могут изменяться время от времени, но при этом они должны изменяться так, чтобы каждое уникальное значение А имело только одно значение В, связанное с ним. ФЗ описываются с помощью нескольких различных способов, два из которых изображены на рис.5.5.

А -> В - математическая форма записи

 - диаграмма или графическая форма записи

Рис.5.5 Два возможных способа записи того, что атрибут В функционально зависит от атрибута А.

При графической форме атрибуты могут помещаться в прямоугольник, круг, овал и т.д.

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

В качестве примера вновь обратимся к атрибутам в отношении УСПЕВАЕМОСТЬ (рис.5.3). И, в частности, к подробному объяснению того, как эти атрибуты связаны между собой. После изучения описаний атрибутов могут быть выведены ФЗ, приведенные на рис.5.5.

Сном -> Сфам

Сном -> Кном

Кном -> Тном

Тном -> Кном

Сном -> Тном

Сном, Дисциплина, Семестр -> Оценка

Рис.5.5. Различные способы представления ФЗ, существующих между атрибутами отношения.

Соображение, приведшие к ФЗ, изображенным на рис.5.5 в деталях обсуждаются ниже.

1. Номера студентов являются уникальными. Каждому студенту назначается номер Сном, причем все номера различны. Таким образом, если известны Сном, то с ним связана только одна фамилия Сфам: Сном -> Сфам. Обратное не является верным, поскольку несколько студентовмогут иметь одинаковые фамилии.

2. Каждый студент прикреплен к одной комнате общежития, но в одной комнате может проживать более чем один студент. Таким образом, Сном -> Кном является верным, а Кном -> Сном - нет.

3. Поскольку в каждой комнате только один телефон и каждый телефон, в свою очередь, имеет уникальный номер, получаем Кном -> Тном и Тном-> Кном. Данная ситуация обычно обозначается в виде Кном <--> Тном, и говорят, что Сном и Тном взаимозависимы.

4. Поскольку в каждой комнате только один телефон и этот телефон имеет уникальный номер, следовательно только один телефонный номер может быть связан с данным студентом, или иначе Сном -> Тном.

5. Последняя ФЗ представляет собой пример сложного набора атрибутов, входящих в ФЗ. Зависимость Сном, Дисциплина, Семестр -> Оценка означает, что оценка однозначно определяется только в том случае, если известен Сном студента, изучающего данную Дисциплину в данном семестре. (Необходимо помнить, что студент может пересдать данную дисциплину и получить при этом другую оценку).

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

Возможный ключ.Возможный ключ представляет собой атрибут или набор атрибутов, который может быть использован для данного отношения в качестве первичного ключа. Первичный ключ всегда является возможным ключом; однако не исключено наличие других возможных ключей, которые могли бы быть, но не были использованы в качестве первичного ключа.

Детерминант. Если А -> В есть ФЗ и В не зависит функционально от любого подмножества А, то говорят, что А представляет собой детерминант В.

Из рис.5.5 можно заключить, что отношение УСПЕВАЕМОСТЬ имеет только один возможный ключ, а именно набор атрибутов <Сном, Дисциплина, Семестр >. Этот вывод получен путем нахождения минимального набора значений атрибутов, которые, если они известны, определяют значение всех других атрибутов кортежа. С помощью ФЗ, представленных на рис.5.5, легко видеть, что один номер Сном определяет Сфам, Кном, Тном и для определения оценки должен быть известен весь набор Сном, Дисциплина и Семестр.

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

Детерминантами в отношении УСПЕВАЕМОСТЬ являются левые части всех ФЗ в отношении. Детерминантами здесь являются

<Сном, Дисциплина, Семестр >, <Сном>, <Кном> и <Тном>.

Детерминанты заключены в угловые скобки для того, чтобы в данном случае выделить четыре различных детерминанта. Следует заметить, что взаимные зависимости дают два детерминанта.

Коддом доказано, что большинство потенциальных аномалий в БД будет устранено в случае должной декомпозиции каждого отношения в нормальную форму Бойса-Кодда (НФБК), которая определяется следующим образом:

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

Отношение УСПЕВАЕМОСТЬ не находится в НФБК. Это легко обнаружить, если расположить рядом перечень всех детерминантов и перечень всех возможных ключей и посмотреть, является ли каждый детерминант возможным ключом.

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

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

<Сном>

<Тном>

<Кном>

Поскольку не каждый детерминант в отношении УСПЕВАЕМОСТЬ является возможным ключом, следовательно оно не находится в НФБК и его необходимо подвергнуть декомпозиции.

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

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

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 приведены на рис.5.6 вместе со связанными с ними ФЗ.

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

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

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

< Сном >

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.5.4 Возможные потери ФЗ при декомпозиции

Ранее было сказано, что в процессе проектирования с помощью проекции декомпозицию следует осуществлять путем поиска цепочек ФЗ, а именно: A -> B -> C с последующим проецированием, порождаемым ФЗ, замыкающей цепочки. В данном случае это ФЗ В -> С.

Отступим от этого правила и в качестве ФЗ для композиции возьмем А -> В. Если исходное отношение имеет вид R(A,B,C),то полученные в результате отношения будут R1(A, В) и R2(A, С).

Хотя оба эти отношения находятся в НФБК, со всей отчетливостью обнаруживается следующая проблема. Ни отношение R1(А,В), ни R2(A,C) не содержит ФЗ В -> С, которая является ФЗ исходного отношения.

Эта зависимость утеряна в процессе декомпозиции. С практической точки зрения это означает, что если приведенные выше отношения R1 и R2 будут использованы для создания БД, то нельзя будет утверждать, что некорректные связи между В и С не будут привнесены в БД.

Проблема в данном примере возникает из-за проекции, порожденной ФЗ, зависимостная часть которой сама является детерминантом другой ФЗ. При использовании правила цепочки эта проблема не возникает.

Таким образом, следует избегать выбора ФЗ, зависимостная часть которой сама - целиком или частично является детерминантом другой ФЗ.

Другим случаем возможной потери ФЗ в процессе декомпозиции является ситуация, в которой один атрибут зависит от двух различных детерминантов. Пусть для отношения R(A,B,C) определены зависимости, показанные на рис.5.9.

Это отношение не находится в НФБК, т.к. имеется только один возможный ключ <A,C>, в то время как детерминантами являются <А> и <C>. Правило цепочек здесь не приемлемо по причине их отсутствия. Кроме того, если одна из ФЗ будет выделена обычным способом, то другая будет потеряна. Например, при выделении из R(A, B,C) зависимости А -> В будут получены отношения R1(A,C) и R2(A,B), ни одно из которых не будет содержать зависимости С -> В. Наоборот, при первоочередном выделении С -> В будет утеряна зависимость А -> В.

Таким образом, возникла ситуация, обязывающая проектировщика найти способ разбиения отношения R(A,B,C) на два, не приводящей к утере ни одной ФЗ. Этот путь не соответствует стандартному методу декомпозиции, но может привести к лучшему результату. Единственное что может сделать проектировщик, столкнувшись с указанной ситуацией, это проверить три возможных набора отношений и оценить, какой из трех наиболее соответствует нуждам пользователя. В частности, полученные в последнем случае отношения необходимо проверить на предмет возникновения проблем в случае соединения двух итоговых отношений при поиске данных на этапе эксплуатации окончательного варианта базы.

Второй метод разбиения отношения, основан на подходе к проектированию, отличном от декомпозиции, тем не менее используется многими проектировщиками. В основе подхода, называемого некоторыми МЕТОДОМ СИНТЕЗА, лежит утверждение (в своей простейшей форме), что необходимо все ФЗ с одинаковыми детерминантами выделять в группы и каждой группе отводить свое собственное отношение. Получаемые отношения проверяются на их соответствие НФБК. В последнем примере были две зависимости с различными детерминантами. Согласно методу синтеза каждой ФЗ следует выделить ее отношение - R1(A,B) и R2(C,B). Метод синтеза может быть использован как самостоятельно, так и в сочетании с методом декомпозиции.

Тот факт, что существует различные методы проектирования, которые могут быть использованы как порознь, так и смешанным образом, свидетельствует о том, что проектирование БД является частично наукой, а частично искусством. Возможность развития нескольких вполне "законных" проектов, имеющих общую исходную точку, является неотъемлемым фактором области проектирования БД. Часть процесса проектирования заключается в оценке нескольких альтернатив с целью выявления наиболее отвечающей нуждам пользователя.

1.5.5 Избыточные функциональные зависимости

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

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

Приемы удаления избыточных ФЗ

Транзитивные зависимости. Одним из вариантов появления в наборе ФЗ избыточных зависимостей является наличие ФЗ, представляющих транзитивные зависимости, которая определяется следующим образом:

Если A -> B и B -> C, то A -> C - транзитивная зависимость.

Здесь следует подчеркнуть два момента:

1. Транзитивная зависимость A -> C, приведенная в определении выше, является вполне корректной зависимостью.

2. Если A -> B, B -> C и A -> C входят в набор ФЗ, то A -> C является избыточной и ее использование в процессе проектирования не требуется. Действительно, транзитивная зависимость A -> C причинит больше вреда, чем пользы при проектировании, и ее следует исключить из набора перед началом проектирования.

Добавление атрибутов в ФЗ. Второй путь возникновения избыточных ФЗ связан с концепцией добавления. Эта форма избыточности имеет несколько видов, из которых только два самые простые, но и крайне полезные, обсуждаются ниже.

Вид первый формулируется следующим образом: Если А -> В, то А,Z -> В является корректной, но избыточной ФЗ. Атрибут Z был добавлен к детерминанту А без привнесения какой-либо новой информации в процесс проектирования. (Здесь А,В и Z - атрибуты, каждый из которых может быть составным).