Нормализация реляционных таблиц (отношений)

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

Пример: таблица «Должность» (значение поля “ФИО” уникально). Каждому сотруднику соответствует одна должность, но одна и та же должность может быть у нескольких сотрудников. В этом случае считается, что поле “должность” функционально зависит от поля “ФИО”.

 

ФИО	должность
В	экономист
К	экономист
Ч	главбух
Л	ген. директор

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

Существуют 3 нормальные формы: 1НФ, 2НФ, 3НФ.

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

Реляционная таблица удовлетворяет 2НФ, если она соответствует 1НФ и не содержит неполных функциональных зависимостей.

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

Другими словами, в 2НФ не должно быть атрибутов, зависящих только от части составного ключа, а не от него целиком.

Пример: таблица «Булочная». Соответствует 2НФ. Поле “цена” и “количество” целиком определяются составным ключом «“хлеб завод” & “продукт”».

хлеб завод ¿	продукт ¿	цена	кол-во
Пекарь	нарезной	12-80
Кушелевский	нарезной	12-50
Каравай	нарезной	12-70
Кушелевский	дарницкий	14-00
Каравай	дарницкий	14-20	50

Если же булочная будет назначать одну и ту же цену на определенный вид продукции любого завода (например: любой нарезной батон будет стоить 12-70, а дарницкий 14-10), то поле “цена” будет функционально зависеть как от ключа целиком, так и от его части – поля “продукт”. Такая зависимость является неполной. Для устранения неполной зависимости необходимо разбить таблицу «Булочная» на две таблицы.

хлеб завод ¿	код продукта ¿	кол-во		продукт ¿	цена	код продукта
пекарь	Нб1		нарезной	12-70	Нб1

Реляционная таблица удовлетворяет 3НФ, если она находится во 2НФ и среди ее атрибутов отсутствуют транзитивные функциональные зависимости.

Транзитивная зависимость – это две зависимости: 1) ключ таблицы функционально определяет неключевой атрибут; 2) этот неключевой атрибут функционально определяет другой неключевой атрибут.

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

Пример: таблица «Должность». В таблице существует транзитивная зависимость: “должность” зависит от “ФИО”, а “оклад” зависит от “ФИО” через “должность”.

ФИО ¿	должность	оклад
В	экономист
К	экономист
Ч	главбух
Л	ген. директор

Для приведения таблицы к 3НФ необходимо разделить ее на две таблицы:

ФИО ¿	код должности		код ¿	должность	оклад

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

5. Обеспечение целостности данных в реляционных таблицах

В таблице должны выполняться правила:

1. для любой таблицы первичный ключ должен быть уникальным и непустым (иметь значение).

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

Пример: таблицы «Группа»–«Студент». Если есть студенты из группы 4078/4, то запись об этой группе обязательно должна быть в главной таблице «Группа».

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

Пример: правило «каскад» требует при удалении (обновлении) какой-либо записи в главной таблице удаления (обновления) всех соответствующих записей в подчиненных таблицах (установлено в Access): если в таблице «Клиент» удаляется запись с кодом клиента 1578, то в связанной таблице «Заказ» удаляются все записи с кодом 1578.

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

Понятие об индексах

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

Преимущество двоичного поиска: в самой неблагоприятной ситуации (искомая запись – последняя из N) при последовательном поиске нужно сделать N шагов, а при двоичном – log₂N.