Нормализация базы данных.

Нормализация базы данных. Нормализация таблиц базы данных - первый шаг на пути проектирования структуры реляционной базы данных. База данных считается нормализованной, если ее таблицы (по крайней мере, большинство таблиц) представлены как минимум в третьей нормальной форме. Первая нормальная форма Первая нормальная форма (1 НФ). Отношение находится в 1НФ, если каждый его атрибут является атомарным (т.е. не содержит более одного значения), не содержит повторяющихся кортежей и ни одно из полей не является пустым. Пример: рассмотрим таблицу из базы данных «Сотрудники», содержащей взаимосвязи управляющего персонала. Логическое ограничение: что каждый менеджер может иметь одного или более подчиненного, а каждый подчиненный в свою очередь может иметь только одного менеджера. Первый подход: Интуитивно мы скорее всего разместили бы эту информацию следующим образом: Менеджер Подчиненный1 Подчиненный2 Подчиненный3 Подчиненный4 Bob Mary Jim Jim Mike Alan Mary Jason - Beth Carol - Mark - Недостатки: 1. Только Jim имеет одного подчиненного – поля Подчиненный2 - Подчиненный4 просто занимают место. 2. Более того, Mary уже имеет 4 подчиненных - и что случится, если появятся другие работники? Вся структура таблицы потребует модификации. Второй подход: мы не хотим иметь более одного столбца и хотим позволить себе хранить в нем сколь угодное количество данных. Тогда мы получаем что-то типа этого: Менеджеры Подчиненные Bob Jim, Mary, Beth Mary Mike,Jason, Carol, Mark Jim Alan Недостатки: 1. Что случится, когда мы будем нуждаться в добавлении или удалении подчиненных? Нам будет необходимо прочитать и записать целую таблицу. Это небольшая проблема в нашей ситуации, но что если менеджер имеет не одну сотню работников? 2. Также это осложняет процесс выборки данных их базы данных в будущих запросах. Третий подход: Отношение в первой нормальной форме. Менеджеры Подчиненные Bob Jim Bob Mary Bob Beth Mary Mike Mary Jason Mary Carol Mary Mark Jim Alan Выводы: Первая нормальная форма: запрещает повторяющиеся столбцы (содержащие одинаковую по смыслу информацию) - запрещает множественные столбцы (содержащие значения типа списка и т.п.) - требует определить первичный ключ для таблицы, то есть тот столбец или комбинацию столбцов, которые однозначно определяют каждую строку Пример отношения: СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ (Н_СОТР, Н_ОТД, ТЕЛ, Н_ПРО, ПРОЕКТ, Н_ЗАДАН) ФАМ, где Н_СОТР - табельный номер сотрудника ФАМ - фамилия сотрудника Н_ОТД - номер отдела, в котором числится сотрудник ТЕЛ - телефон сотрудника Н_ПРО - номер проекта, над которым работает сотрудник ПРОЕКТ - наименование проекта, над которым работает сотрудник Н_ЗАДАН - номер задания, над которым работает сотрудник Логическое ограничение: каждый сотрудник в каждом проекте выполняет ровно одно задание В качестве потенциального ключа отношения необходимо взять пару атрибутов {Н_СОТР, Н_ПРО}. Отношение СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ Н_СОТР 1 1 2 3 3 ФАМ Н_ОТД ТЕЛ Н_ПРО ПРОЕКТ Н_ЗАДАН Иванов 1 11-22-33 Космос 1 1 Иванов 1 11-22-33 Климат 1 2 Петров 1 11-22-33 Космос 2 1 Сидоров 2 33-22-11 Космос 3 1 Сидоров 2 33-22-11 Климат 2 2 Функциональные зависимости Зависимость атрибутов от ключа отношения: {Н_СОТР, Н_ПРО} ФАМ {Н_СОТР, Н_ПРО} Н_ОТД {Н_СОТР, Н_ПРО} ТЕЛ {Н_СОТР, Н_ПРО} ПРОЕКТ {Н_СОТР, Н_ПРО} Н_ЗАДАН Зависимость атрибутов, характеризующих сотрудника от табельного номера сотрудника: Н_СОТР ФАМ Н_СОТР Н_ОТД Н_СОТР ТЕЛ Зависимость наименования проекта от номера проекта: Н_ПРО ПРОЕКТ Зависимость номера телефона от номера отдела: Н_ОТД ТЕЛ Вторая нормальная форма Отношение находится во второй нормальной форме (2НФ) тогда и только тогда, когда отношение находится в 1НФ и нет неключевых атрибутов, зависящих от части сложного ключа. (Неключевой атрибут - это атрибут, не входящий в состав никакого потенциального ключа). Отношение СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ Н_СОТР 1 1 2 3 3 ФАМ Н_ОТД ТЕЛ Н_ПРО ПРОЕКТ Н_ЗАДАН Иванов 1 11-22-33 Космос 1 1 Иванов 1 11-22-33 Климат 1 2 Петров 1 11-22-33 Космос 2 1 Сидоров 2 33-22-11 Космос 3 1 Сидоров 2 33-22-11 Климат 2 2 Отношение СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ не находится в 2НФ, т.к. есть атрибуты, зависящие от части сложного ключа: Отношение СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ Н_СОТР 1 1 2 3 3 ФАМ Н_ОТД ТЕЛ Н_ПРО ПРОЕКТ Н_ЗАДАН Иванов 1 11-22-33 Космос 1 1 Иванов 1 11-22-33 Климат 1 2 Петров 1 11-22-33 Космос 2 1 Сидоров 2 33-22-11 Космос 3 1 Сидоров 2 33-22-11 Климат 2 2 Зависимость атрибутов, характеризующих сотрудника от табельного номера сотрудника является зависимостью от части сложного ключа: Н_СОТР ФАМ Н_СОТР Н_ОТД Н_СОТР ТЕЛ Зависимость наименования проекта от номера проекта является зависимостью от части сложного ключа: Н_ПРО ПРОЕКТ Для того, чтобы устранить зависимость атрибутов от части сложного ключа, нужно произвести декомпозицию отношения на несколько отношений. При этом те атрибуты, которые зависят от части сложного ключа, выносятся в отдельное отношение. Отношение СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ Н_СОТР ФАМ Н_ОТД ТЕЛ Н_ПРО ПРОЕКТ Н_ЗАДАН Иванов 1 11-22-33 Космос 1 1 1 Иванов 1 11-22-33 Климат 1 1 2 Петров 1 11-22-33 Космос 2 2 1 Сидоров 2 33-22-11 Космос 3 3 1 Сидоров 2 33-22-11 Климат 2 3 2 Отношение СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ декомпозируем на три отношения: СОТРУДНИКИ_ОТДЕЛЫ (Н_СОТР, ФАМ, Н_ОТД, ТЕЛ) ПРОЕКТЫ (Н_ПРО, ПРОЕКТ) ЗАДАНИЯ (Н_СОТР, Н_ПРО, Н_ЗАДАН) Отношение СОТРУДНИКИ_ОТДЕЛЫ (Н_СОТР, ФАМ, Н_ОТД, ТЕЛ): Функциональные зависимости: Зависимость атрибутов, характеризующих сотрудника от табельного номера сотрудника: Н_СОТР ФАМ Н_СОТР Н_ОТД Н_СОТР ТЕЛ Зависимость номера телефона от номера отдела: Н_ОТД ТЕЛ Отношение СОТРУДНИКИ_ОТДЕЛЫ Н_СОТР ФАМ Н_ОТД ТЕЛ Иванов 1 11-22-33 1 Петров 1 11-22-33 2 Сидоров 2 33-22-11 3 Отношение СОТРУДНИКИ_ОТДЕЛЫ имеет следовательно автоматически находится во 2НФ. простой ключ, Отношение ПРОЕКТЫ (Н_ПРО, ПРОЕКТ): Функциональные зависимости: Н_ПРО ПРОЕКТ Отношение ПРОЕКТЫ Н_ПРО ПРОЕКТ Космос 1 Климат 2 Отношение ПРОЕКТЫ имеет автоматически находится во 2НФ. простой ключ, следовательно Отношение ЗАДАНИЯ (Н_СОТР, Н_ПРО, Н_ЗАДАН): Функциональные зависимости: {Н_СОТР, Н_ПРО} Н_ЗАДАН Отношения ЗАДАНИЯ Н_СОТР Н_ПРО Н_ЗАДАН 1 1 1 1 1 2 2 2 1 3 3 1 2 3 2 Отношение ЗАДАНИЯ имеет сложный ключ, но единственный неключевой атрибут Н_ЗАДАН функционально зависит от всего ключа {Н_СОТР, Н_ПРО}. Отношение СОТРУДНИКИ_ОТДЕЛЫ Отношение ПРОЕКТЫ Н_СОТР ФАМ Н_ОТД ТЕЛ Н_ПРО ПРОЕКТ Отношения ЗАДАНИЯ Н_СОТР Н_ПРО Н_ЗАДАН 1 Иванов 1 11-22-33 1 Космос 1 1 1 2 Петров 1 11-22-33 2 Климат 1 2 1 3 Сидоров 2 33-22-11 2 1 2 3 1 3 3 2 2 Часть аномалий обновления устранена. 1) данные о сотрудниках и проектах теперь хранятся в различных отношениях, поэтому при появлении сотрудников, не участвующих ни в одном проекте просто добавляются кортежи в отношение СОТРУДНИКИ_ОТДЕЛЫ. Точно также, при появлении проекта, над которым не работает ни один сотрудник, просто вставляется кортеж в отношение ПРОЕКТЫ. 2) Фамилии сотрудников и наименования проектов теперь хранятся без избыточности. Если сотрудник сменит фамилию или проект сменит наименование, то такое обновление будет произведено в одном месте. 3) Если по проекту временно прекращены работы, но требуется, чтобы сам проект сохранился, то для этого проекта удаляются соответствующие кортежи в отношении ЗАДАНИЯ, а данные о самом проекте и данные о сотрудниках, участвовавших в проекте, остаются в отношениях ПРОЕКТЫ и СОТРУДНИКИ_ОТДЕЛЫ Отношение СОТРУДНИКИ_ОТДЕЛЫ Отношение ПРОЕКТЫ Н_СОТР ФАМ Н_ОТД ТЕЛ Н_ПРО ПРОЕКТ Отношения ЗАДАНИЯ Н_СОТР Н_ПРО Н_ЗАДАН 1 Иванов 1 11-22-33 1 Космос 1 1 1 2 Петров 1 11-22-33 2 Климат 1 2 1 3 Сидоров 2 33-22-11 2 1 2 3 1 3 3 2 2 Оставшиеся аномалии вставки (INSERT) В отношение СОТРУДНИКИ_ОТДЕЛЫ нельзя вставить кортеж (4, Пушников, 1, 33-22-11), т.к. при этом получится, что два сотрудника из 1-го отдела (Иванов и Пушников) имеют разные номера телефонов, а это противоречит модели предметной области. В этой ситуации можно предложить два решения, в зависимости от того, что реально произошло в предметной области. Другой номер телефона может быть введен по двум причинам - по ошибке человека, вводящего данные о новом сотруднике, или потому что номер в отделе действительно изменился. Тогда можно написать триггер, который при вставке записи о сотруднике проверяет, совпадает ли телефон с уже имеющимся телефоном у другого сотрудника этого же отдела. Если номера отличаются, то система должна задать вопрос, оставить ли старый номер в отделе или заменить его новым. 1) Если нужно оставить старый номер (новый номер введен ошибочно), то кортеж с данными о новом сотруднике будет вставлен, но номер телефона будет у него будет тот, который уже есть в отделе (в данном случае, 11-22-33). 2) Если же номер в отделе действительно изменился, то кортеж будет вставлен с новым номером, и одновременно будут изменены номера телефонов у всех сотрудников этого же отдела. И в том и в другом случае не обойтись без разработки громоздкого триггера. Причина аномалии - избыточность данных, порожденная тем, что в одном отношении хранится разнородная информация (о сотрудниках и об отделах). Вывод - увеличивается сложность разработки базы данных. База данных, основанная на такой модели, будет работать правильно только при наличии дополнительного программного кода в виде триггеров. Отношение СОТРУДНИКИ_ОТДЕЛЫ Отношение ПРОЕКТЫ Н_СОТР ФАМ Н_ОТД ТЕЛ Н_ПРО ПРОЕКТ 1 Иванов 1 11-22-33 1 Космос 2 Петров 1 11-22-33 2 Климат 3 Сидоров 2 33-22-11 Отношения ЗАДАНИЯ Н_СОТР Н_ПРО Н_ЗАДАН 1 1 1 1 2 1 2 1 2 3 1 3 3 2 2 Оставшиеся аномалии обновления (UPDATE) Одни и те же номера телефонов повторяются во многих кортежах отношения. Поэтому если в отделе меняется номер телефона, то такие изменения необходимо одновременно выполнить во всех местах, где этот номер телефона встречаются, иначе отношение станет некорректным. Таким образом, обновление базы данных одним действием реализовать невозможно. Необходимо написать триггер, который при обновлении одной записи корректно исправляет номера телефонов в других местах. Причина аномалии - избыточность данных, также порожденная тем, что в одном отношении хранится разнородная информация. Вывод - увеличивается сложность разработки базы данных. База данных, основанная на такой модели, будет работать правильно только при наличии дополнительного программного кода в виде триггеров. Отношение СОТРУДНИКИ_ОТДЕЛЫ Отношение ПРОЕКТЫ Н_СОТР ФАМ Н_ОТД ТЕЛ Н_ПРО ПРОЕКТ 1 Иванов 1 11-22-33 1 Космос 2 Петров 1 11-22-33 2 Климат 3 Сидоров 2 33-22-11 Отношения ЗАДАНИЯ Н_СОТР Н_ПРО Н_ЗАДАН 1 1 1 1 2 1 2 1 2 3 1 3 3 2 2 Оставшиеся аномалии удаления (DELETE) При удалении некоторых данных по-прежнему может произойти потеря другой информации. Например, если удалить сотрудника Сидорова, то будет потеряна информация о том, что в отделе номер 2 находится телефон 33-22-11. Причина аномалии - хранение в одном отношении разнородной информации (и о сотрудниках, и об отделах). Вывод - логическая модель данных неадекватна модели предметной области. База данных, основанная на такой модели, будет работать неправильно. Заметим, что при переходе ко второй нормальной форме отношения стали почти адекватными предметной области. Остались также трудности в разработке базы данных, связанные с необходимостью написания триггеров, поддерживающих целостность базы данных. Эти трудности теперь связаны только с одним отношением СОТРУДНИКИ_ОТДЕЛЫ. Выводы: Вторая нормальная форма требует, чтобы неключевые столбцы таблиц зависили от первичного ключа в целом, но не от его части. Если таблица находится в первой нормальной форме и первичный ключ у нее состоит из одного столбца, то она автоматически находится и во второй нормальной форме. Третья нормальная форма Атрибуты называются взаимно независимыми, если ни один из них не является функционально зависимым от другого. Отношение находится в третьей нормальной форме (3НФ) тогда и только тогда, когда отношение находится в 2НФ и все неключевые атрибуты взаимно независимы. Отношение СОТРУДНИКИ_ОТДЕЛЫ Отношение ПРОЕКТЫ Н_СОТР ФАМ Н_ОТД ТЕЛ Н_ПРО ПРОЕКТ 1 Иванов 1 11-22-33 1 Космос 2 Петров 1 11-22-33 2 Климат 3 Сидоров 2 33-22-11 Отношения ЗАДАНИЯ Н_СОТР Н_ПРО Н_ЗАДАН 1 1 1 1 2 1 2 1 2 3 1 3 3 2 2 Отношение СОТРУДНИКИ_ОТДЕЛЫ не находится в 3НФ, т.к. имеется функциональная зависимость неключевых атрибутов (зависимость номера телефона от номера отдела): Н_ОТД ТЕЛ Для того, чтобы устранить зависимость неключевых атрибутов, нужно произвести декомпозицию отношения на несколько отношений. При этом те неключевые атрибуты, которые являются зависимыми, выносятся в отдельное отношение. Отношение СОТРУДНИКИ_ОТДЕЛЫ декомпозируем на два отношения - СОТРУДНИКИ, ОТДЕЛЫ. Отношение СОТРУДНИКИ (Н_СОТР, ФАМ, Н_ОТД): Функциональные зависимости: Зависимость атрибутов, характеризующих сотрудника табельного номера сотрудника: Н_СОТР ФАМ Н_СОТР Н_ОТД Н_СОТР ТЕЛ Отношение СОТРУДНИКИ Н_СОТР ФАМ Н_ОТД Иванов 1 1 Петров 1 2 Сидоров 2 3 от Отношение ОТДЕЛЫ (Н_ОТД, ТЕЛ): Функциональные зависимости: Зависимость номера телефона от номера отдела: Н_ОТД ТЕЛ Отношение ОТДЕЛЫ Н_ОТД ТЕЛ 11-22-33 1 33-22-11 2 Атрибут Н_ОТД, не являвшийся ключевым в отношении СОТРУДНИКИ_ОТДЕЛЫ, становится потенциальным ключом в отношении ОТДЕЛЫ. Именно за счет этого устраняется избыточность, связанная с многократным хранением одних и тех же номеров телефонов. Отношение СОТРУДНИКИ Н_СОТР ФАМ Н_ОТД 1 Иванов Отношение ПРОЕКТЫ Н_ПРО ПРОЕКТ 1 1 Космос 2 Климат 2 Петров 1 3 Сидоров 2 Отношение ОТДЕЛЫ Н_ОТД ТЕЛ 1 11-22-33 1 11-22-33 2 33-22-11 Отношения ЗАДАНИЯ Н_СОТР Н_ПРО Н_ЗАДАН 1 1 1 1 2 1 2 1 2 3 1 3 3 2 2 Таким образом, все обнаруженные аномалии обновления устранены. Реляционная модель, состоящая из четырех отношений СОТРУДНИКИ, ОТДЕЛЫ, ПРОЕКТЫ, ЗАДАНИЯ, находящихся в третьей нормальной форме, является адекватной описанной модели предметной области, и требует наличия только тех триггеров, которые поддерживают ссылочную целостность. Такие триггеры являются стандартными и не требуют больших усилий в разработке. Выводы: Чтобы таблица находилась в третьей нормальной форме, необходимо, чтобы неключевые столбцы в ней не зависели от других неключевых столбцов, а зависели только от первичного ключа. Самая распространенная ситуация в данном контексте - это расчетные столбцы, значения которых можно получить путем каких-либо манипуляций с другими столбцами таблицы. Для приведения таблицы в третью нормальную форму такие столбцы из таблиц надо удалить. Алгоритм нормализации (приведение к 3НФ) Итак, алгоритм нормализации (т.е. алгоритм приведения отношений к 3НФ) описывается следующим образом. Шаг 1 (Приведение к 1НФ). На первом шаге задается одно или несколько отношений, отображающих понятия предметной области. По модели предметной области (не по внешнему виду полученных отношений!) выписываются обнаруженные функциональные зависимости. Все отношения автоматически находятся в 1НФ. Шаг 2 (Приведение к 2НФ). Если в некоторых отношениях обнаружена зависимость атрибутов от части сложного ключа, то проводим декомпозицию этих отношений на несколько отношений следующим образом: те атрибуты, которые зависят от части сложного ключа выносятся в отдельное отношение вместе с этой частью ключа. В исходном отношении остаются все ключевые атрибуты: Исходное отношение: . Ключ: - сложный. Функциональные зависимости: - зависимость всех атрибутов от ключа отношения. - зависимость некоторых атрибутов от части сложного ключа. Декомпозированные отношения: - остаток от исходного отношения. Ключ . - атрибуты, вынесенные из исходного отношения вместе с частью сложного ключа. Ключ . Шаг 3 (Приведение к 3НФ). Если в некоторых отношениях обнаружена зависимость некоторых неключевых атрибутов других неключевых атрибутов, то проводим декомпозицию этих отношений следующим образом: те неключевые атрибуты, которые зависят других неключевых атрибутов выносятся в отдельное отношение. В новом отношении ключом становится детерминант функциональной зависимости: Исходное отношение: . Ключ: . Функциональные зависимости: - зависимость всех атрибутов от ключа отношения. - зависимость некоторых неключевых атрибутов других неключевых атрибутов. Декомпозированные отношения: - остаток от исходного отношения. Ключ . - атрибуты, вынесенные из исходного отношения вместе с детерминантом функциональной зависимости. Ключ . Замечание. 1) На практике, при создании логической модели данных, как правило, не следуют прямо приведенному алгоритму нормализации. Опытные разработчики обычно сразу строят отношения в 3НФ. 2) Основным средством разработки логических моделей данных являются различные варианты ER-диаграмм. Особенность этих диаграмм в том, что они сразу позволяют создавать отношения в 3НФ. Тем не менее, приведенный алгоритм важен по двум причинам. Во-первых, этот алгоритм показывает, какие проблемы возникают при разработке слабо нормализованных отношений. Во-вторых, как правило, модель предметной области никогда не бывает правильно разработана с первого шага. Эксперты предметной области могут забыть о чем-либо упомянуть, разработчик может неправильно понять эксперта, во время разработки могут измениться правила, принятые в предметной области, и т.д. Все это может привести к появлению новых зависимостей, которые отсутствовали в первоначальной модели предметной области. Тут как раз и необходимо использовать алгоритм нормализации хотя бы для того, чтобы убедиться, что отношения остались в 3НФ и логическая модель не ухудшилась. Сравнение нормализованных и ненормализованных моделей влияние логического моделирования данных на качество физических моделей данных и производительность базы данных: Критерий Отношения слабо Отношения сильно нормализованы нормализованы (1НФ, 2НФ) (3НФ) Адекватность базы данных ХУЖЕ (-) ЛУЧШЕ (+) предметной области Легкость разработки и СЛОЖНЕЕ (-) ЛЕГЧЕ (+) сопровождения базы данных Скорость выполнения МЕДЛЕННЕЕ (-) БЫСТРЕЕ (+) вставки, обновления, удаления Скорость выполнения БЫСТРЕЕ (+) МЕДЛЕННЕЕ (-) выборки данных 1) Как видно из таблицы, более сильно нормализованные отношения оказываются лучше спроектированы (три плюса, один минус). Они больше соответствуют предметной области, легче в разработке, для них быстрее выполняются операции модификации базы данных. Правда, это достигается ценой некоторого замедления выполнения операций выборки данных. 2) У слабо нормализованных отношений единственное преимущество - если к базе данных обращаться только с запросами на выборку данных, то для слабо нормализованных отношений такие запросы выполняются быстрее. Это связано с тем, что в таких отношениях уже как бы произведено соединение отношений и на это не тратится время при выборке данных. Таким образом, выбор степени нормализации отношений зависит от характера запросов, с которыми чаще всего обращаются к базе данных. Нормальная форма Бойса-Кодда Нормальная форма Бойса — Кодда (усиленная 3 НФ). Отношение находится в НФ Бойса — Кодда, если любая функциональная зависимость между его атрибутами сводится к полной функциональной зависимости от первичного ключа. Нормальная форма Бойса-Кодда требует, чтобы в таблице был только один потенциальный первичный ключ. Чаще всего у таблиц, находящихся в третьей нормальной форме, так и бывает, но не всегда. Если обнаружился второй столбец (комбинация столбцов), позволяющий однозначно идентифицировать строку, то для приведения к нормальной форме Бойса-Кодда такие данные надо вынести в отдельную таблицу. Четвертая нормальная форма Для приведения таблицы, находящейся в нормальной форме Бойса-Кодда, к четвертой нормальной форме необходимо устранить имеющиеся в ней многозначные зависимости. То есть обеспечить, чтобы вставка / удаление любой строки таблицы не требовала бы вставки / удаления / модификации других строк этой же таблицы. Пятая нормальная форма Таблицу, находящуюся в четвертой нормальной форме и, казалось бы, уже нормализованную до предела, в некоторых случаях еще можно бывает разбить на три или более (но не на две!) таблиц, соединив которые, мы получим исходную таблицу. Получившиеся в результате такой, как правило, весьма искусственной, декомпозиции таблицы и называют находящимися в пятой нормальная форме. Формальное определение пятой нормальной формы таково: это форма, в которой устранены зависимости соединения. В большинстве случаев практической пользы от нормализации таблиц до пятой нормальной формы не наблюдается. Разработаны специальные формальные математические методы нормализации таблиц реляционных баз данных