Нормализация таблиц

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

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

С формальной точки зрения нормализацию можно представить как последовательный процесс разбиения и преобразования некоторого небольшого исходного набора таблиц для построения набора взаимосвязанных таблиц в нормальных формах. Основатель реляционной модели данных Е. Кодд выделял три нормальные формы — первую, вторую и третью. Этот набор в дальнейшем был дополнен нормальной формой Бойса-Кодда, и далее четвертой и пятой нормальными формами.

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

Рис. 1. Пример приведения таблицы к первой нормальной форме

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

Из приведенного примера видно, что таблицы в первой нормальной форме могут содержать многочисленные ситуации дублирования данных (в приведенном примере по полям «Фамилия», «Звание», «Кабинет», «Сл.тел.»). Кроме того, в таблице, находящейся в первой нормальной форме, могут встречаться и другие аномалии схемы таблиц-отношений. В частности, в приведенном примере нельзя образовать запись для сотрудника, не участвовавшего ни в одной операции. Удаляя запись об участии определенного сотрудника в определенной операции, можно удалить информацию о том, что он вообще работает в определенном подразделении. При переводе сотрудника в другое подразделение или при его перемещении в другой кабинет приходится изменять все записи-кортежи с данным сотрудником по различным операциям. Поэтому Е. Коддом был разработан специальный механизм разбиения таблиц для приведения к более совершенным нормальным формам. Этот механизм основан на понятии функциональной зависимости полей-атрибутов.

Поле-атрибут Y функционально зависит от поля-атрибута X, если любому значению Х всегда соответствует в точности одно значение Y. К примеру, атрибут «ФИО» функционально зависит от атрибута «Таб.№», т. е. каждому значению атрибута «Таб.№» соответствует только одно значение атрибута «ФИО». Другим примером является функциональная зависимость поля «Кабинет» от поля «Фамилия», так как обычно один сотрудник имеет рабочее место только в одном кабинете. Легко убедиться, что в таблице, находящейся в первой нормальной форме, все неключевые атрибуты функционально зависят от ключа таблицы.

Вторая нормальная форма основывается на понятии полной функциональной зависимости. Функциональная зависимость неключевого атрибута от составного ключа таблицы называется полной, если он функционально зависит в целом от составного ключа, но не зависит отдельно от любой части составного ключа. В примере, приведенном на рис. 1, значение поля-атрибута «Фамилия» определяется только значением поля «Лич.№ сотр.», которое является частью составного ключа таблицы, и, следовательно, функционально полной зависимости неключевого поля-атрибута «Фамилия» от составного ключа нет. В полной функциональной зависимости от составного ключа находится поле-атрибут «Награда», так как только комбинация значений полей «Лич.№ сотр.» и «Условное наименование мероприятий…» определяет конкретное значение поля «Награда».

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

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

• построить еще одну или несколько проекций на часть составного ключа с полями, функционально зависящими от этой части ключа.

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

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

В таблицах, находящихся во второй нормальной форме, большинство аномалий, присущих первой скорме, устранено. Вместе с тем по определенным атрибутам также могут сохраняться многочисленные ситуации дублирования данных. Так, например, в приведенном на рис. 2 примере происходит неоправданное дублирование информации о служебном телефоне «11 22 33», так как атрибут «Сл. тел.» фактически зависит не от атрибута «Лич.№ сотр.»», а от атрибута «Кабинет».* Иначе говоря, наблюдается цепочка функциональной зависимости атрибутов «Лич. № сотр.» — «Кабинет» — «Сл. тел.», а функциональная зависимость атрибута «Сл.тел.» от атрибута «Лич. № сотр.» является лишь логическим следствием такой цепочки зависимостей. В таких ситуациях говорят о транзитивной зависимости атрибута «Сл. тел.» от атрибута «Лич. № сотр.».

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

 

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

Для преобразования из второй в третью нормальную форму таблицу-отношение разделяют на две или более проекции так, чтобы конечные поля-атрибуты в цепочках транзитивной зависимости вынести в отдельные таблицы, связав разделившиеся части таблицы внешними ключами по полям-атрибутам, находящимся внутри цепочек транзитивной зависимости. На рис. 3 проиллюстрирован процесс приведения таблицы из второй в третью нормальную форму путем разделения цепочки транзитивной зависимости «Лич.№ сотр.» — «Кабинет» — «Сл. тел.». Внутреннее в этой цепочке поле-атрибут «Кабинет» стало соответственно внешним ключом в первой таблице и первичным ключом во второй таблице.

Рис. 3. Пример приведения таблицы в третью нормальную форму

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

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

Рис. 4. Пример приведения таблицы из третьей нормальной формы в форму Бойса-Кодда

В данной таблице имеются два детерминанта — («Лич. № сотр.», «Операция») и («Фамилия», «Операция»), от каждого из которых функционально полно зависит поле-атрибут «Мероприятие».

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

* Поэтому иногда нормальную форму Бойса-Кодда считают частным случаем третьей нормальной формы.

 

Таблица, приведенная на рис. 4, не удовлетворяет требованию нормальной формы Бойса-Кодда, так как если установить ключом детерминант («Лич.№ сотр.», «Операция»), то поле-атрибут «Фамилия» будет функционально зависеть от части составного ключа (от поля «Лич.№ сотр.») и нарушатся требования второй нормальной формы. Следствием такой ситуации является дублирование данных по полям-атрибутам «Лич. № сотр.» и «Фамилия».

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

Встречаются также случаи, требующие «улучшения» и нормальной формы Бойса-Кодда. Такие ситуации связаны с многозначной зависимостью атрибутов. В таблице-отношении с полями-атрибутами X, Y, Z существует многозначная зависимость атрибута Y от атрибута Х тогда и только тогда, когда любое значение из множества Y, соответствующее паре значений атрибутов Х и Z, зависит только от значения Y. Для примера рассмотрим таблицу на рис. 5. При этом будем считать, что каждый сотрудник, привлеченный к какой-либо операции, в обязательном порядке участвует во всех проводимых в рамках данной операции мероприятиях. В этом случае единственно возможным ключом является совокупность всех трех полей атрибутов (каждый сотрудник может участвовать в разных операциях, в одной операции может участвовать несколько сотрудников).

Рис. 5. Пример декомпозиции таблицы из нормальной формы Бойса-Кодда в четвертую нормальную форму

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

Подобные аномалии устраняет четвертая нормальная форма. Таблица-отношение находится в четвертой нормальной форме тогда и только тогда, когда в случае существования мно­гозначной зависимости атрибута Y от атрибута Х все остальные атрибуты функционально зависят от атрибута X.

Приведение таблицы в четвертую нормальную форму основывается на теореме Фейджина, в которой доказывается возможность проецирования без потерь* таблицы с атрибутами X, Y, Z в две таблицы с атрибутами X, Y и X, Z, когда существует многозначная зависимость атрибута Y от атрибута X. Процесс декомпозиции проиллюстрирован на рис. 5.

* Проецирование без потерь предполагает полное и безызбыточное восстановление исходной таблицы путем операции соединения таблиц — результатов декомпозиции.

 

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

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

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

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

Приведение таблицы в пятую нормальную форму осуще­ствляется путем ее декомпозиции сразу на несколько таблиц отношений. Если предположить, что в таблице, представленной на рис. 6. имеется зависимость соединения по составным атрибутам «Фамилия»-«Группа», «Фамилия»-«Мероприятие», «Группа»-«Мероприятие»,* то, разбив таблицу на три проекции по соответствующим полям-атрибутам, можно удовлетворить требованиям пятой нормальной формы и устранить отмеченные аномалии.

* Наличие зависимости соединения является нетривиальным предположением, основывающимся в большинстве случаев на эвристических соображениях, т.е. в данном случае на уверенности, что при соединении трех таблиц «Фамилия»-«Группа», «Фамилия»-«Мероприятие» и «Группа»-«Мероприятие» не произойдет каких-либо потерь пли появления лишних данных относительно исходной таблицы.

 

Из-за нетривиальности зависимости соединения пятая нормальная форма практически не используется.

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