Сущность нормализации

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

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

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

Рассмотрим БД для консультанта университета, состоящую из одной таблицы Консультант со следующими полями: № студента, ФИО студента, № комнаты, № телефона, № курса, Семестр1, Оценка:

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

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

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

Неявная избыточность: один и тот же номер телефона имеют все студенты, живущие в одной комнате. Допустим, Васильев О.И. извещает консультанта о том, что его номер телефона изменен на 7777, забыв при этом сообщить о друге по комнате, консультант меняет телефонный номер в кортежах для Васильева О.И. – в результате правильный номер телефона будет фактически утерян.

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

Рассмотрим отношение СлужащийНачальник:

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

Дублированные фамилии удалены – и невозможно узнать фамилии начальников для служащих с номерами 195 и 200.

Теперь рассмотрим отношение СлужащийНачальникТелефон (предполагаем, что каждый начальник имеет только один телефонный номер):

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

Для исключения избыточности телефонных номеров данное отношение разбивается на следующие два:

СлужащийНачальник НачальникТелефон

Данные отношения являются проекциями исходного отношения, естественное соединение которых даст опять таки его.

Проблема удаления. В экземпляре1 отношения Консультант имеется только один кортеж для студента с фамилией Гатаулин. Предположим, консультант узнает, что этот студент не закончил курс ООП, как это отмечено, и удаляет соответствующий кортеж, что приведет к потере из БД информации об этом студенте.

Дадим определение функциональнойзависимости между данными.

Пусть имеется отношение r(A₁, A₂, …, A_n). Атрибут А₂ отношения r функционально зависит от атрибута A₁ того же отношения, если в каждый момент времени каждому значению атрибута А₁ соответствует не более, чем одно значение атрибута А₂ (то есть функциональная зависимость А₂ от А₁ означает, что если в любой момент времени известно значение А₁, то можно однозначно получить и значение А₂). Обозначается:

А₁ ® А₂.

Рассмотрим отношение Студент (№ зачетной книжки, № группы, ФИО).

Функционально зависимы следующие атрибуты:

№ зачетной книжки ® № группы;

№ зачетной книжки ® ФИО.

Если предположить, что имеются полные однофамильцы, то:

ФИО ↛ № зачетной книжки;

ФИО ↛ № группы.

Атрибут может функционально зависеть не от какого-то одного атрибута, а от целой группы атрибутов, то есть А₁ и А₂ могут быть составными.

В связи с этим дадим определение полной функциональной зависимости.

Если в отношении r для множеств атрибутов А₁ и А₂ имеет место А₁ ® А₂ и при этом ↛ А₂, где – подмножество А₁ ( ), то говорят, что множество атрибутов А₂ функционально полно зависит от всего множества А₁, но не зависит ни от какого подмножества А₁.

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

В качестве примера обратимся к атрибутам отношения Консультант. Функционально зависимы следующие атрибуты:

№ студента ® ФИО студента;

№ студента ® № комнаты;

№ студента ® № телефона;

№ комнаты ® № телефона;

№ телефона ® № комнаты;

№ студента, № курса, Семестр ® Оценка.

Другой способ представления функциональных зависимостей:

Нормальные формы

Наличие тех или иных зависимостей в отношении определяет степень его нормализации.

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

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

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

Атрибут A_i отношения r называют основным атрибутом, если он является элементом первичного ключа данного отношения.

Рассмотрим отношение Факультет (Код факультета, Наименование факультета, ФИО декана, № телефона).

Функционально зависимы следующие атрибуты (исходим из предположения, что на одном телефонном номере может «висеть» несколько абонентов):

Код факультета

Наименование факультета

ФИО декана

№ телефона

Таким образом, в рассматриваемом отношении три возможных ключа: Код факультета, Наименование факультета, ФИО декана. Выберем в качестве первичного ключа атрибут Код факультета. Атрибуты Наименование факультета, ФИО декана, № телефона, не являющиеся основными, функционально полно зависят от первичного ключа отношения, значит отношение находится во 2НФ.

Рассмотрим отношение СтудентКурспроект (№ студента, Код предмета, ФИО студента, № группы, ФИО преподавателя, Процент выполнения). Предположим, что в одной группе могут учиться полные однофамильцы. Тогда у этого отношения один возможный ключ: № студента, Код предмета. Атрибуты ФИО студента и № группы не являются основными, но функционально зависят от основного атрибута № студента, являющегося элементом ключа (т. е. отношение не находится во 2НФ).

ФЗ между атрибутами данного отношения:

№ студента

Код предмета

ФИО студента

№ группы

ФИО преподавателя

Процент выполнения

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

№ студента

ФИО студента

№ группы

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

№ студента

Код предмета

ФИО преподавателя

Процент выполнения

получим два отношения во 2НФ.

Отношения Студент (№ студента, ФИО студента, № группы) и Курспроект (№ студента, Код предмета, ФИО преподавателя, Процент выполнения) являются проекциями исходного отношения, естественное соединение которых даст его. Таким образом, в процессе преобразования никакая информация не теряется, любая информация, которая может быть получена из первоначальной структуры, может быть получена и из новой структуры. Обратное, однако, неверно: новая структура может содержать информацию (например, о студентах, еще не получивших задания на курсовое проектирование), которая не может быть представлена в первоначальной структуре. В этом смысле новая структура является более точным отображением реального мира.

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

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

Транзитивная зависимость определяется следующим образом: если X ® Y и Y ® Z, то X ® Z (Z транзитивно зависит от X).

Приведение отношения к 3НФ заключается в устранении транзитивных зависимостей в отношении путем разбиения исходного отношения r(X, Y, Z) на: r1(X, Y) и r2(Y, Z).

Рассмотрим отношение Общежитие (Код студента, № группы, № комнаты, Староста комнаты).

F-зависимости между атрибутами данного отношения:

Код студента

№ группы

№ комнаты

Староста комнаты

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

Для устранения недостатков разобьем отношение на следующие два:

Код студента № комнаты

№ группы Староста комнаты

№ комнаты

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

Отношение может быть в 3НФ и при этом все же иметь некоторые нежелательные свойства.

Например, рассмотрим отношение ГАИ (город, адрес, индекс), где индекс – это индекс отделения связи, адрес – название улицы, номер дома и номер квартиры.

F-зависимости между атрибутами отношения:

Город

Адрес

Индекс

Т. е. полный адрес определяет почтовый индекс, а тот, в свою очередь, определяет название города, но не определяет адрес.

Ключом отношения является составной атрибут: город, адрес. Отношение находится в 3НФ (в нем нет транзитивных и неполных зависимостей).

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

Для устранения недостатков 3НФ вводится четвертая нормальная форма, имеющая две разновидности.

Первая разновидность известна под названием нормальнойформыБойса -Кодда (НФБК) (в некоторых литературных источниках она называется усовершенствованной 3НФ).

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

Детерминантом отношения называют атрибут (возможно, составной) от которого функционально полно зависит другой атрибут.

Пример отношения в НФБК: ВыдачаВозврат (Код книги, Код читателя, Дата выдачи, Дата возврата).

Функциональные зависимости, имеющие место в данном отношении:

Код книги Код книги

Дата выдачи Дата возврата

Код читателя Код читателя

Дата возврата Дата выдачи

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

Может оказаться так, что отношение в 3НФ нельзя будет привести к НФБК без потери зависимостей между атрибутами этого отношения.

Обратимся, например, к отношению ГАИ (город, адрес, индекс), которое не находится в НФБК, так как имеет место зависимость индекс ® город.

Это отношение можно разбить на отношения: ГА (город, адрес) и АИ (адрес, индекс), но тогда зависимость индекс ® город будет утеряна.

Определение второй разновидности четвертой нормальной формы (4НФ): отношение r находится в 4НФ тогда и только тогда, когда при существовании многозначной зависимости в r атрибута Y от атрибута X, все остальные атрибуты r функционально зависят от Х.

Атрибут Х многозначно определяет атрибут Y, если с каждым значением x может использоваться значение y из фиксированного подмножества значений Y. Обозначается: X ↠ Y.

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

В качестве примера рассмотрим отношение КПУ (Курс, Преподаватель, Учебник), где Курс – наименование курса, Преподаватель – фамилия преподавателя, Учебник – название учебника. Пусть данному курсу может соответствовать любое число преподавателей и любое количество учебников, и пусть преподаватели и учебники не зависят друг от друга.

Экземпляр отношения КПУ, касающийся только одного курса:

Атрибут Курс многозначно определяет атрибут Преподаватель и имеется многозначная зависимость атрибута Учебник от атрибута Курс:

Курс ↠ Преподаватель;

Курс ↠ Учебник.

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

Для устранения недостатков отношения, представленного в 3НФ, выполняют разложение по многозначным зависимостям данного отношения, т. е. отношение r (A, B, C), где A ↠ B и A ↠ C, разбивают на два: r1 (A, B) и r2 (A, C).

Для нашего примера: КП (Курс, Преподаватель), КУ (Курс, Учебник). Каждое из полученных отношений находится в четвертой нормальной форме.

Приведем примеры выявления нормальной формы отношений.

Дана диаграмма функциональных зависимостей для некоторого отношения (варианты а, б):

а) б)

Необходимо определить, в какой нормальной форме находится данное отношение.

Для варианта а: имеем две функциональные зависимости: А ® С и А, В ® D, т.е. ключом отношения является составной атрибут А, В. Будем считать, что каждый из имеющихся атрибутов имеет атомарное значение. Тогда рассматриваемое отношение находится в 1НФ. Отношение не находится во 2НФ, в силу имеющейся функциональной зависимости неосновного атрибута С от атрибута А – части ключа.

Для варианта б: имеем три функциональные зависимости: D ® A, D ® B и A, B ® C, т.е. ключом отношения является атрибут D. Будем считать, что каждый из имеющихся атрибутов имеет атомарное значение. Тогда рассматриваемое отношение находится в 1НФ. Отношение находится во 2НФ, т.к. все неосновные атрибуты: A, B и С функционально полно зависят от ключа отношения. Отношение не находится в 3НФ, так как неосновной атрибут С транзитивно зависит от ключа D: D ® A, B ® C.