Избыточность данных и нормализация

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

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

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

Аномалии в базе данных – это проблемы связанные с обработкой информации, а точнее с удаление данных из базы данных, с модификацией данных в таблице базы данных и аномалия добавления данных в базу данных:

 

Аномалия включения – это проблема, связанная с добавлением данных в базу данных

Аномалия модификации – это проблема, связанная с изменением данных в базе данных

Аномалия удаления – это проблема, связанная с удаление данных в базе данных

 

Все эти проблемы связаны с целостностью баз данных, а именно с избыточностью данных в базе данных.

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

Рассмотрим пример таблицы, которую проектировали не профессиональные разработчики, а обычные пользователи:

Наим.	Город	Адрес	Эл. почта	WWW	Вид	Конт. лица
Хлебозавод 1	Санкт-Петербург	Невский пр, д. 100	[e-mail]	www.bread.ru	Поставщик	Иванов И.И., зам. дир., тел [phone]
Хлебозавод 1	Санкт-Петербург	Невский пр, д. 100	[e-mail]	www.bread.ru	Поставщик	Петров П.П., нач. отд. сбыта, тел [phone]
ООО «Молоко»	Оренбург	Ул. Гоголя, 25	[e-mail]		Клиент	Сидоров С.С., директор, тел. [phone]
ИЧП «Гамма»	Санкт-Петербург	Лиговский пр-кт, 15	[e-mail]		Клиент	Михайлов М.М., директор, тел [phone]

Конечно же, такая структура таблицы является неоптимальной по нескольким причинам:

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

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

3) при изменении, к примеру, адреса для фирмы, нам потребуется этот адрес поменять во всех записях для данной фирмы.

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

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

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

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

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

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

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

· первая нормальная форма (1NF);

· вторая нормальная форма (2NF);

· третья нормальная форма (3NF);

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

· четвертая нормальная форма (4NF);

· пятая нормальная форма, или нормальная форма проекции-соединения (5NF или PJ/NF).

Основные свойства нормальных форм:

· каждая следующая нормальная форма в некотором смысле лучше предыдущей;

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

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

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

Определение 1. Функциональная зависимость

В отношении R атрибут Y функционально зависит от атрибута X (X и Y могут быть составными) в том и только в том случае, если каждому значению X соответствует в точности одно значение Y: R.X (r) R.Y.

Определение 2. Полная функциональная зависимость

Функциональная зависимость R.X (r) R.Y называется полной, если атрибут Y не зависит функционально от любого точного подмножества X.

Определение 3. Транзитивная функциональная зависимость

Функциональная зависимость R.X (r) R.Y называется транзитивной, если существует такой атрибут Z, что имеются функциональные зависимости R.X (r) R.Z и R.Z (r) R.Y и отсутствует функциональная зависимость R.Z --> R.X. (При отсутствии последнего требования мы имели бы "неинтересные" транзитивные зависимости в любом отношении, обладающем несколькими ключами.)

Определение 4. Неключевой атрибут

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

Определение 5. Взаимно независимые атрибуты

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

 

Первая нормальная форма

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

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

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

Вторая нормальная форма

Рассмотрим следующий пример схемы отношения:

СОТРУДНИКИ-ОТДЕЛЫ-ПРОЕКТЫ

(СОТР_НОМЕР, СОТР_ЗАРП, ОТД_НОМЕР, ПРО_НОМЕР, СОТР_ЗАДАН)

Первичный ключ:

(СОТР_НОМЕР, ПРО_НОМЕР)

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

СОТР_НОМЕР (r) СОТР_ЗАРП

СОТР_НОМЕР (r) ОТД_НОМЕР

ОТД_НОМЕР (r) СОТР_ЗАРП

СОТР_НОМЕР, ПРО_НОМЕР (r) СОТР_ЗАДАН

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

Определение 6. Вторая нормальная форма (в этом определении предполагается, что единственным ключом отношения является первичный ключ)

Отношение R находится во второй нормальной форме (2NF) в том и только в том случае, когда находится в 1NF, и каждый неключевой атрибут полностью зависит от первичного ключа.

Можно произвести следующую декомпозицию отношения СОТРУДНИКИ-ОТДЕЛЫ-ПРОЕКТЫ в два отношения СОТРУДНИКИ-ОТДЕЛЫ и СОТРУДНИКИ-ПРОЕКТЫ:

СОТРУДНИКИ-ОТДЕЛЫ (СОТР_НОМЕР, СОТР_ЗАРП, ОТД_НОМЕР)

Первичный ключ:

СОТР_НОМЕР

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

СОТР_НОМЕР (r) СОТР_ЗАРП

СОТР_НОМЕР (r) ОТД_НОМЕР

ОТД_НОМЕР (r) СОТР_ЗАРП

СОТРУДНИКИ-ПРОЕКТЫ (СОТР_НОМЕР, ПРО_НОМЕР, СОТР_ЗАДАН)

Первичный ключ:

СОТР_НОМЕР, ПРО_НОМЕР

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

СОТР_НОМЕР, ПРО_НОМЕР (r) CОТР_ЗАДАН

Каждое из этих двух отношений находится в 2NF, и в них устранены отмеченные выше аномалии (легко проверить, что все указанные операции выполняются без проблем).

Если допустить наличие нескольких ключей, то определение 6 примет следующий вид:

Определение 6~

Отношение R находится во второй нормальной форме (2NF) в том и только в том случае, когда оно находится в 1NF, и каждый неключевой атрибут полностью зависит от каждого ключа R.

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

 

Третья нормальная форма

Рассмотрим еще раз отношение СОТРУДНИКИ-ОТДЕЛЫ, находящееся в 2NF. Заметим, что функциональная зависимость СОТР_НОМЕР (r) СОТР_ЗАРП является транзитивной; она является следствием функциональных зависимостей СОТР_НОМЕР (r) ОТД_НОМЕР и ОТД_НОМЕР (r) СОТР_ЗАРП. Другими словами, заработная плата сотрудника на самом деле является характеристикой не сотрудника, а отдела, в котором он работает (это не очень естественное предположение, но достаточное для примера).

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

Определение 7. Третья нормальная форма. (Снова определение дается в предположении существования единственного ключа.)

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

Можно произвести декомпозицию отношения СОТРУДНИКИ-ОТДЕЛЫ в два отношения СОТРУДНИКИ и ОТДЕЛЫ:

СОТРУДНИКИ (СОТР_НОМЕР, ОТД_НОМЕР)

Первичный ключ:

СОТР_НОМЕР

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

СОТР_НОМЕР (r) ОТД_НОМЕР

ОТДЕЛЫ (ОТД_НОМЕР, СОТР_ЗАРП)

Первичный ключ:

ОТД_НОМЕР

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

ОТД_НОМЕР (r) СОТР_ЗАРП

Каждое из этих двух отношений находится в 3NF и свободно от отмеченных аномалий.

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

Определение 7~

Отношение R находится в третьей нормальной форме (3NF) в том и только в том случае, если находится в 1NF, и каждый неключевой атрибут не является транзитивно зависимым от какого-либо ключа R.

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