4.2. Нормализация базы данных

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

Так, скажем, в структуре БД, приведенной на рис. 4.1, интуи­тивно чувствуется, что имеется избыточность. Действительно, в отношении SP присутствует атрибут NAME, однако и в отноше­нии S этот атрибут имеет место. Таким образом, информация о фамилии и имени студента дублируется При этом возникают проблемы, например связанные с тем, что при изменении фами­лии студента возникает необходимость ее изменения в обоих от­ношениях.

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

В теории реляционных БД обычно выделяется следующая по­следовательность нормальных форм:

- первая нормальная форма (1НФ):

- вторая нормальная форма (2НФ);

- третья нормальная форма (ЗНФ):

- нормальная форма Бойса-Кодда (НФБК);

- четвертая нормальная форма (4НФ);

- пятая нормальная форма, или нормальная форма проек­ции-соединения (5НФ или НФПС).

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

Основные свойства НФ:

- каждая следующая НФ в некотором смысле лучше предыдущей;

- при переходе к следующей НФ свойства предыдущих нормальных форм сохраняются.

В основе процесса проектирования лежит метод нормализа­ции - декомпозиция отношения, находящегося в предыдущей НФ.

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

Отношение будет находиться в 1НФ при условии, что оно содержит только логически неделимые значения. Такие значе­ния в дальнейшем будем называть скалярными. При этом не­обходимо заметить, что приведенное определение говорит о нахождении любого нормализованного отношения в 1НФ. В то же время отношение, находящееся только в 1НФ, обладает структурой не совсем желательной, например, по причине ее возможной избыточности.

Допустим, что отношение SP (см. рисунок 4.1) содержит всю информацию о студенческой группе и оценках. Назовем его SP1, что приведено на рис. 4.2.

SP1 (Оценки)
OCENKA	SN	SPEC	GROUP	PN

Рис. 4.2. Структура отношения SP1

Для отношения SP1 имеем в качестве первичного ключа

комбинацию {SN, PN}. Кроме того, имеет место функциональная зависимость номера группы студента и его специальности, то есть GROUP —> SPEC. Если построить диаграмму функциональ­ных зависимостей для отношения SP1, то она будет иметь вид, представленный на рис. 4.3 (для упрощения некоторые функ­циональные связи не показаны).

Рис. 4.3.Диаграмма функциональных зависимостей для отношения SP1

Нежелательность такой структуры связана, например, с тем, что неключевые атрибуты не являются взаимно независимыми (GROUP —> SPEC), или с тем, что неключевые атрибуты не все неприводимо зависимы от первичного ключа (GROUP и SPEC зависимы от SN каждый в отдельности).

Кроме того, возникают дополнительные проблемы, связанные с избыточностью SP1. Так скажем, при выполнении операции INSERT (вставка) нельзя вставить данные о студентах и студен­ческой группе, если еще ими не сдавался экзамен - ведь для тако­го случая не будет известно значение первичного ключа.

При выполнении операции DELETE (удаление) будет удалена информация не только о конкретной оценке студента по конкрет­ному экзамену, но и информация о том, в какой группе и на какой специальности этот студент учится.

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

Избежать этих ситуаций можно путем замены отношения SP1 на два - SP2 и SP, диаграмма функциональных зависимо­стей для которых приведена на рис. 4.4. Такая структура по­зволяет выполнить без проблем операцию INSERT в отноше­ние SP2 даже при отсутствии информации о сданных экзаме­нах; операцию DELETE над оценками без потери информации о студенте; операцию UPDATE без необходимости исправле­ния данных во всех кортежах, относящихся к переводимому в другую группу студенту.

Рис. 4.4. Диаграмма функциональных зависимостей для отношений SP2 и SP

Отношение находится во 2НФ в том случае, когда оно уже считается находящимся в 1НФ, и каждый неключевой атрибут полностью (неприводимо) зависит от первичного ключа. Кроме того, всякое отношение, которое находится в 1НФ и не находится во 2НФ, всегда можно преобразовать и свести к эквивалентному набору отношений, находящихся во 2НФ. Этот процесс заключа­ется заменой отношения, находящегося в 1НФ набором проек­ций, эквивалентных исходному. Соответственно, соединение этих проекций даст исходное отношение.

Отношения SP и SP2 находятся во 2НФ с первичными ключа­ми соответственно SN и {SN, PN}. Действительно, если над от­ношениями SP и SP2 произвести соединение по атрибуту SN, то получим отношение SP1.

Однако в отношении SP2 из-за функциональной зависимости GROUP —> SPEC все равно могут возникнуть проблемы при ма­нипуляции с данными. Так, при выполнении операции INSERT нельзя указать, что данная группа относится к некоторой специ­альности, пока в этой группе не появится хотя бы один студент. Если над отношением SP2 будет выполнена операция DELETE, то вместе с информацией о группе будет утрачена информация о специальности, по- которой проходит обучение данная группа. В то же время, при выполнении операции UPDATE, при изменении наименования специальности возникнет необходимость либо ис­кать всю информацию по корректируемой специальности во всем отношении, внося соответствующие изменения, либо будет иметь место несовместимый результат

Для решения вновь возникших проблем заменим отношение SP2 на две проекции - SG и GS. структура которых приведена на рис. 4.5.

SG			GS
SN	GROUP		GROUP	SPEC

Рис. 4.5. Структура отношений SG и GS

Действительно, путем декомпозиции была исключена "двой­ная" зависимость атрибута SPEC от первичного ключа SN и ат­рибута GROUP. Таким образом, диаграмма функциональных за­висимостей для отношений SG и GS будет иметь вид. показанный на рис. 4.6.

Рис. 4.6. Диаграмма функциональных зависимостей отношений SG и GS

Отношение находится в ЗНФ в том случае, если оно находит­ся во 2НФ, неключевые атрибуты взаимно независимы и каждый неключевой атрибут неприводимо зависит от первичного ключа (то есть возможно изменять значение атрибутов без изменения первичного ключа и других неключевых атрибутов). Отношение, находящееся во 2НФ, всегда может быть приведено к эквива­лентному набору отношений в ЗНФ.

Отношения SG и GS находятся в ЗНФ, причем первичными ключами в них являются соответственно атрибуты SN и GROUP

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

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

Для рассмотренных выше примеров можно сказать, что отно­шение SP1 не находится в НФБК, а отношения SP, SG и GS нахо­дятся в НФБК.

Действительно, отношение SP1 (см. рисунок 4.3) содержит три детерминанта - SN, GROUP и {SN, PN}. из которых только {SN, PN} является потенциальным ключом. Отсюда и сделан вы­вод, что SP1 не находится в НФБК. Для отношений SP, SG и GS можно говорить о том, что они находятся в НФБК, поскольку в каждом из них единственный потенциальный ключ является единственным детерминантом.

Рассмотрим схему отношения PR (ПРЕДМЕТЫ), приведен­ную на рис. 4.7.

Рис. 4.7. Структура отношения PR (ПРЕДМЕТЫ)

Отношение ПРЕДМЕТЫ содержит номера (коды) предметов, для каждого предмета - перечень курсов, включенных в этот предмет, и, наконец, перечень заданий, предусматриваемых по курсу. При этом по курсу их может быть несколько, а разные кур­сы могут включать одинаковые задания.

Каждый кортеж отношения связывает некоторый предмет с курсом и заданием, которые должны быть выполнены в рамках данного курса. По причине сформулированных выше условий, единственным возможным ключом отношения является состав­ной атрибут {PN, PNAME, PZAN} и нет никаких других детер­минантов. Следовательно, отношение ПРЕДМЕТЫ находится в НФБК. Но при этом оно обладает недостатками: если, например, некоторое задание добавляется к данному курсу, необходимо вставить в отношение ПРЕДМЕТЫ столько кортежей, сколько заданий в нем предусмотрено.

Дело в том, что в данном отношении существуют многознач­ные зависимости. В отношении R {А, В, С} существует много­значная зависимость между А и В в том случае, если множество значений В, соответствующее паре значений А и С, зависит только от А и не зависит от С.

Дальнейшая нормализация отношений, подобных отношению ПРЕДМЕТЫ, основывается на проецировании без потерь. Здесь под последним понимается такой способ декомпозиции отноше­ния, при котором исходное отношение полностью и без избыточ­ности восстанавливается путем естественного соединения полу­ченных отношений.

Таким образом, отношение находится в 4НФ в том случае, если в случае существования многозначной зависимости А, В все остальные атрибуты отношения функционально зависят от А.

В нашем примере можно произвести декомпозицию отноше­ния ПРЕДМЕТЫ в два отношения ПРЕДМЕТЫ-КУРСЫ и ПРЕДМЕТЫ-ЗАДАНИЯ, как показано на рис. 4.8

Рис. 4.8. Декомпозиция отношения PR (ПРЕДМЕТЫ)

Оба полученных отношения находятся в 4НФ и свободны от отмеченных выше проблем.

Во всех рассмотренных до этого момента нормализация про­изводилась декомпозицией одного отношения в два. Иногда это сделать не удается, но возможна декомпозиция в большее число отношений, каждое из которых обладает лучшими свойствами. Рассмотрим отношение Р1 (ПРЕПОДАВАТЕЛИ), структура ко­торого приведена на рис. 4.9.

Рис. 4.9. Структура отношения Р1 (ПРЕПОДАВАТЕЛИ)

Предположим, что один и тот же преподаватель может рабо­тать на разных кафедрах и проводить занятия по нескольким учебным предметам. Первичным ключом этого отношения явля­ется полная совокупность его атрибутов, то есть {TEACHER, KAFEDRA, PNAME}. В отношении отсутствуют функциональ­ные и многозначные зависимости. Поэтому отношение находится в 4НФ. Однако в нем могут существовать проблемы, которые можно устранить путем декомпозиции в три отношения.

Введем понятие зависимости соединения. Отношение R (X, Y,..., Z) удовлетворяет зависимости соединения (X, Y, Z) толь­ко в том случае, когда R восстанавливается без потерь путем со­единения своих проекций на X, Y,..., Z.

Тогда отношение находится в 5НФ (НФПС) только в том случае, когда любая зависимость соединения в отношении следует из существования некоторого возможного ключа в данном отношении.

Введем следующие имена составных атрибутов: ТК = {TEACHER, KAFEDRA}, ТР = {TEACHER, PNAME}, КР = {KAFEDRA, PNAME}

Предположим, что в отношении ПРЕПОДАВАТЕЛИ сущест­вует зависимость соединения (ТК, ТР, КР).

На примерах легко показать, что при вставках и удалении кортежей из ПРЕПОДАВАТЕЛИ могут возникнуть проблемы. Их можно устранить путем декомпозиции исходного отношения в три новых отношения, представленных на рис. 4.10.

Рис. 4.10. Декомпозиция отношения Р1 (ПРЕПОДАВАТЕЛИ)

5НФ - это последняя нормальная форма, которую можно по­лучить путем декомпозиции. Ее условия достаточно нетривиаль­ны, и на практике 5НФ используется достаточно редко.

Таким образом, мы пришли к итоговой схеме процедуры норма­лизации отношений: отношение в 1НФ необходимо разбить на проекции для исключения всех зависимостей, не являющихся неприводимыми.

Как результат в итоге будет получен набор отношений в 2НФ. Отношение, находящееся в 2НФ следует разбить на проекции для исключения "двойных" функциональных -зависимостей. В результате будет получен набор отношений в ЗНФ.

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

Отношения, находящиеся в НФБК. необходимо разбить на проекции для исключения любых многозначных зависимостей, которые не являются функциональными. В итоге получим набор отношений в 4НФ.

Отношения в 4НФ разбивают на проекции с целью исключе­ния любых зависимостей соединения, которые не обусловлены потенциальными ключами. Таким образом будет получен набор отношений в 5НФ.