Нормализация баз данных: нормальные формы

Нормализация - это процесс приведения схемы реляционной базы данных к форме, при которой каждый факт хранится ровно в одном месте. Без неё одна и та же информация дублируется в нескольких строках: изменение адреса клиента требует обновления десятков записей, а случайное удаление строки заказа может унести за собой все данные о товаре. Нормальные формы - это последовательные требования к структуре таблицы, каждое из которых устраняет определённый класс аномалий. Попробуйте задать параметры своей таблицы в калькуляторе ниже: он сразу покажет, как снижается избыточность при переходе от 1НФ к 4НФ и сколько таблиц получится после декомпозиции.

Зачем нужна нормализация

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

Аномалия вставки: нельзя добавить новый факт без связанного с ним другого факта. Например, нельзя записать нового поставщика, пока у него нет ни одного заказа, если поставщик хранится только внутри строки заказа.

Аномалия удаления: удаление одной записи непреднамеренно уничтожает другую. Если удалить последний заказ поставщика, вместе с ним исчезнут и все данные о самом поставщике.

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

Рассчитать для своей задачи

Нормализация убирает эти аномалии поэтапно, опираясь на понятие функциональной зависимости: атрибут $B$ функционально зависит от атрибута $A$ (пишут $A \to B$), если каждому значению $A$ соответствует ровно одно значение $B$. Первичный ключ таблицы функционально определяет все остальные атрибуты - это фундамент всех нормальных форм.

Первая нормальная форма (1НФ)

Таблица находится в первой нормальной форме, если все её атрибуты атомарны: ни одна ячейка не содержит массивов, списков или вложенных таблиц.

Типичное нарушение - столбец «Телефоны» со значениями вида «+7-900-123, +7-900-456». Такую колонку нельзя индексировать по отдельному номеру и нельзя корректно связать с другой таблицей. Исправление: вынести каждый телефон в отдельную строку или в отдельную таблицу.

Формальное требование: пересечение любой строки и любого столбца содержит ровно одно неделимое значение. Ключ (простой или составной) однозначно идентифицирует строку.

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

Вторая нормальная форма (2НФ)

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

Пример нарушения: таблица Сессия(Студент_ID, Дисциплина_ID, ФИО_студента, Оценка). Ключ составной: (Студент_ID, Дисциплина_ID). Атрибут ФИО_студента зависит только от Студент_ID - это частичная зависимость. При изменении имени студента придётся обновлять все его строки в сессии.

Декомпозиция без потерь:

• Студент(Студент_ID, ФИО_студента) - первичный ключ Студент_ID
• Сессия(Студент_ID, Дисциплина_ID, Оценка) - первичный ключ (Студент_ID, Дисциплина_ID), внешний ключ Студент_ID

Соединение двух таблиц по Студент_ID восстанавливает исходную без дублирования - это и есть декомпозиция без потерь (lossless decomposition).

Рассчитать для своей задачи

На схеме показано, как разделяется таблица при устранении частичной зависимости. Стрелки обозначают функциональные зависимости; пунктирная стрелка указывает зависимость, нарушающую 2НФ.

Третья нормальная форма (3НФ)

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

Пример нарушения: таблица Заказ(Заказ_ID, Клиент_ID, Город_клиента). Ключ - Заказ_ID. Зависимости: Заказ_ID -> Клиент_ID и Клиент_ID -> Город_клиента, поэтому Заказ_ID -> Город_клиента - транзитивная зависимость через неключевой Клиент_ID. Город дублируется в каждом заказе; изменить город придётся во всех строках клиента.

Декомпозиция:

• Клиент(Клиент_ID, Город_клиента)
• Заказ(Заказ_ID, Клиент_ID), внешний ключ на Клиент

После декомпозиции к 3НФ устраняются все три вида аномалий для основной массы реальных схем. Это и есть та точка, которую Кодд называл «достаточной нормализацией» для операционных баз данных.

Нормальная форма Бойса-Кодда (НФБК)

НФБК - усиленная версия 3НФ. Таблица в НФБК, если каждый детерминант (левая часть любой нетривиальной функциональной зависимости) является потенциальным ключом. Проще: ни один атрибут не определяет другой, если сам не является ключом.

НФБК отличается от 3НФ только в редком случае: когда в таблице несколько перекрывающихся потенциальных ключей. Классический пример: Расписание(Студент, Дисциплина, Преподаватель), где каждый преподаватель ведёт ровно одну дисциплину. Тогда Преподаватель -> Дисциплина - нетривиальная зависимость, и Преподаватель - детерминант, но не потенциальный ключ. Таблица в 3НФ, но не в НФБК.

Декомпозиция к НФБК может нарушить сохранение зависимостей (dependency preservation) - одна из зависимостей исходной таблицы перестаёт проверяться без соединения таблиц. Это приемлемо, если СУБД поддерживает декларативные ограничения, но в простых схемах часто предпочитают остаться в 3НФ.

Четвёртая нормальная форма (4НФ)

4НФ устраняет многозначные зависимости. Атрибут $C$ многозначно зависит от $A$ (пишут $A \twoheadrightarrow C$), если каждому значению $A$ соответствует независимое множество значений $C$, никак не связанное с другими атрибутами строки.

Пример: Преподаватель(Преподаватель, Дисциплина, Хобби). Дисциплины и хобби преподавателя независимы - нужны все комбинации. При добавлении нового хобби придётся вставить столько строк, сколько дисциплин ведёт преподаватель. Это расцветает в $m \times n$ строк вместо $m + n$.

Декомпозиция: Преп_Дисциплины(Преподаватель, Дисциплина) и Преп_Хобби(Преподаватель, Хобби).

4НФ и выше нужны редко - в основном при моделировании «многие ко многим ко многим» и в хранилищах данных с богатыми метаданными.

Практика: от денорм-таблицы до 3НФ

Рассмотрим типичную учебную схему, с которой начинается большинство курсовых работ:

Заказ(Заказ_ID, Дата, Клиент_ID, Имя_клиента, Город, Товар_ID,
      Название_товара, Цена_за_ед, Кол-во)

Первичный ключ - (Заказ_ID, Товар_ID). Проверяем последовательно:

1НФ - все значения атомарны? Да, нарушений нет.

2НФ - нет ли частичных зависимостей?

• Клиент_ID -> Имя_клиента, Город - зависит от Заказ_ID (части ключа).
• Товар_ID -> Название_товара, Цена_за_ед - зависит от Товар_ID (части ключа).

Декомпозиция к 2НФ:

• Клиент(Клиент_ID, Имя_клиента, Город)
• Товар(Товар_ID, Название_товара, Цена_за_ед)
• Заказ_Строка(Заказ_ID, Товар_ID, Кол-во)
• Заказ(Заказ_ID, Дата, Клиент_ID) + внешний ключ на Клиент

3НФ - нет ли транзитивных зависимостей? В Клиент - нет. В Заказ - нет. Схема уже в 3НФ.

Декомпозиция без потерь: теорема Хита

Декомпозиция таблицы $R$ на $R_1$ и $R_2$ является декомпозицией без потерь (lossless), если:

$R_1 \bowtie R_2 = R,$

то есть естественное соединение декомпозированных таблиц точно восстанавливает исходную. Теорема Хита даёт достаточное условие: если $A \to B$ - функциональная зависимость в $R$, то декомпозиция $R$ на $R_1 = A \cup B$ и $R_2 = R - B$ (при сохранении $A$) - без потерь.

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

Частые ошибки

• Путают 1НФ с нормализацией вообще: говорят «таблица нормализована» и имеют в виду только атомарные значения, хотя до 3НФ ещё далеко.
• Применяют 2НФ к таблицам с простым ключом: если ключ состоит из одного атрибута, частичных зависимостей не бывает по определению. Переход 1НФ→2НФ здесь тривиален.
• Декомпозируют без проверки lossless: делят таблицу «по смыслу» без контроля пересечения схем. В итоге соединение даёт декартово произведение (больше строк, чем в оригинале).
• Забывают о функциональных зависимостях, не указанных в задаче: в реальных схемах зависимости иногда неочевидны. Например, Почтовый_индекс -> Город - реальная зависимость, которая часто игнорируется.
• Путают НФБК и 3НФ: для таблиц с одним потенциальным ключом они совпадают. Разница проявляется только при нескольких перекрывающихся ключах.

FAQ

Что такое функциональная зависимость простыми словами? Атрибут $B$ функционально зависит от $A$, если по значению $A$ можно однозначно определить значение $B$. Например, по табельному номеру сотрудника (Сотр_ID) всегда можно найти его ФИО - значит, Сотр_ID -> ФИО. Именно эти зависимости диктуют, в какую таблицу должен попасть каждый атрибут.

Всегда ли нужно доводить схему до 3НФ или выше? Не всегда. В аналитических хранилищах данных (OLAP) денормализация намеренна: звёздная схема и схема «снежинка» жертвуют избыточностью ради скорости аналитических запросов. Нормализацию до 3НФ и выше применяют в транзакционных базах (OLTP), где важны согласованность и точечные обновления. Для аналитики часто выбирают 2НФ или даже 1НФ ради производительности агрегатов.

Как проверить нормальную форму таблицы на экзамене? Алгоритм: (1) определить все функциональные зависимости в таблице; (2) найти минимальное покрытие (минимальное множество зависимостей, из которого выводятся все остальные); (3) найти потенциальные ключи - атрибуты, которые функционально определяют все остальные; (4) проверить требования нужной НФ. Для 3НФ: в каждой зависимости $X \to Y$ либо $X$ - суперключ, либо $Y$ - часть ключа (ключевой атрибут).

Коротко

Нормализация баз данных - это поэтапное устранение избыточности путём декомпозиции таблиц без потерь. Первая нормальная форма требует атомарных значений; вторая убирает частичные зависимости от составного ключа; третья устраняет транзитивные зависимости между неключевыми атрибутами; НФБК закрывает пограничный случай с несколькими перекрывающимися ключами. Для большинства транзакционных приложений достаточно привести схему к 3НФ: аномалии вставки, обновления и удаления исчезнут, а производительность JOIN останется приемлемой.