3. Нормализация структур баз данных

Ни одно приспособление универсального кухонного

комбайна не будет работать нормально.

Из законов Мэрфи

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

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

2. Универсальная БД анализируется на предмет необходимости дробления выбранных атрибутов.

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

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

5. Между отношениями формируются связи, объединяющие их в законченную БД.

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

NAME	PHONE
Иванов А.Б.	123456
Иванов В.Г.	123457
Петров Д.Е.	345678
Сидоров М.В.	9876543

Рис. 3.4 – Структура телефонного справочника.

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

NAME	I1	I2	PHONE
Иванов	А	Б	123456
Иванов	В	Г	123457
Петров	Д	Е	345678
Сидоров	М	В	9876543

Рис. 3.5 – Дробление атрибутов.

Смысл дробления - в увеличении схожести записей. Теперь можно перейти к этапу 3 - декомпозиции нашей универсальной БД. В любом случае декомпозиция выполняется по следующему простому правилу:

Атрибут, содержащий повторяющуюся информацию, выделяется в отдельную таблицу

В нашем случае атрибут NAME следует выделить в отдельную таблицу (обозначим ее Т1, а таблицу с телефонами - Т0).

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

T1 T0

NAME		I1	I2	PHONE
Иванов		А	Б	123456
Петров		В	Г	123457
Сидоров		Д	Е	345678
		М	В	9876543

Рис. 3.6 – Разделение БД на таблицы.

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

Итак, первым делом мы зададим в отношении Т1 уникальный ключ по атрибуту NAME. Это означает, что все записи окажутся отсортированными по выбранному полю, что делает их пригодными для быстрого (двоичного) поиска. С каждой записью оказывается связанным некоторое ключевое выражение - например, номер записи в отношении Т1.

Это ключевое выражение мы и будем хранить в атрибуте связи отношения Т0.

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

T1 T0

NAME		NAME	I1	I2	PHONE
Иванов		1	А	Б	123456
Петров		1	В	Г	123457
Сидоров		2	Д	Е	345678
		3	М	В	9876543

Рис. 3.7 – Установление связи между таблицами.

Следует заметить, что декомпозиция должна быть оправдана не только с точки зрения избежания дублирования, но и с точки зрения минимизации размера БД. Так, в рассматриваемом примере значения атрибутов I1 или I2 отношения T0 могут повторяться, но их вынесение в отдельные отношения было бы нерациональным решением. Давайте посчитаем: в отношении Т0 каждое из этих полей занимает 1 байт. Вынос их в отдельные отношения приведет к тому, что ключевое выражение будет иметь длину также 1 байт (число букв, для русского языка равное 32, вполне умещается в 1 байт). Поле связи, соответственно, тоже будет иметь размер в 1 байт. В итоге не имеем никакого выигрыша в размере отношения Т0 и сверх этого получаем еще два отношения. В данном случае подобная оптимизация неоправданна.

И, наконец, последний, завершающий этап создания БД - установление связей между отношениями. Прежде всего, надо выделить главное отношение. Главным отношением будет, как правило, то, которое содержит поля связи. В нашем случае это Т0. Мы должны установить следующее правило: при переходе с записи на запись в Т0 берется ключевое значение из поля Т0NAME и по нему выполняется двоичный поиск в отношении Т1. Тогда всегда в отношении Т1 текущей будет запись с фамилией, соответствующей текущему номеру телефона в отношении Т0.

Связь может устанавливаться программным способом, а в ряде БД (InterBase, MS Access) связи хранятся непосредственно в самой БД.

БЫЛО:

PRODUCT	FIRM
Привод	ОАО "Электроприбор"
Задвижка	ООО "Арматура"
Задвижка	ОАО "Электроприбор"
Привод	ООО "Арматура"

СТАЛО:

PRODUCT		PRODUCT	FIRM		FIRM
Привод		1	1		ОАО "Электроприбор"
Задвижка		2	2		ООО "Арматура"
		2	1
		1	2

Рис. 3.8 – Нормализация связи "многий-ко-многим".

Интересный вопрос возникает при удалении записи из нормализованного отношения, не являющего главным. Скажем, оказалось, что всем абонентам по фамилии "Петров" сняли телефоны. Тогда можно удалить соответствующую запись из отношения Т1. При этом правильно спроектированная БД выполнит каскадное удаление: автоматически удалит все записи в Т0, атрибут связи которых ссылался на запись "Петров" в отношении Т1. Каскадное удаление гарантирует отсутствие в главном отношении "потерянных" записей, которые ссылаются в никуда.

Необходимо знать три вида связей между атрибутами двух отношений. Они называются "один-к-одному", "один-ко-многим" и "многий-ко-многим".

Связь "один-к-одному". Между атрибутами А и В существует связь "один к одному", если каждому значению атрибута А соответствует одно и только одно значение атрибута В. Обратное может быть неверно. Именно такой вид связи установлен между атрибутами "Имя абонента" (А) и "Номер телефона" в ненормализованной базе данных (В): каждому абоненту соответствует один и только один телефонный номер.

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

Связь "один-ко-многим": одному значению атрибута А соответствуют одно или несколько значений атрибута В. Это самый распространенный вид связи. В нашем примере, если рассматривать Т1 как главное отношение, атрибут T1NAME (A) связан связью "один-ко-многим" с атрибутом T0PHONE (B), поскольку абоненты с разными номерами телефонов могут иметь одинаковые фамилии. Нормализация такой связи заключается в выделении в отдельное отношение атрибута А.

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