3NF: устранение transitive dependencies

Таблица в 2NF: она в 1NF и в ней нет partial dependencies — ни один non-prime атрибут не зависит от части ключа. Но 2NF закрывает только один вид «неправильной» зависимости. Остаётся ещё один: non-prime атрибут может зависеть от другого non-prime атрибута. Такой дефект 2NF не замечает — а избыточность и аномалии он порождает ровно те же.

Третья нормальная форма (3NF) устраняет этот последний из «школьных» дефектов — transitive dependency (транзитивную зависимость). 3NF — это практический рабочий стандарт для OLTP-схем: подавляющее большинство нормализованных баз приложений доводят именно до 3NF. В этом уроке мы дадим определение 3NF, разберём транзитивную зависимость и пройдём декомпозицию из 2NF в 3NF на конкретной таблице.

Что такое transitive dependency

Transitive dependency (транзитивная зависимость) — это зависимость non-prime атрибута от другого non-prime атрибута. Название — от аксиомы транзитивности Армстронга: если ключ -> A и A -> B, то по транзитивности ключ -> B, но при этом B достаётся ключу «через посредника» A, а не напрямую.

Рассмотрим таблицу сотрудников. Первичный ключ — emp_id, одноатомный, значит таблица заведомо в 2NF (partial dependency невозможна):

EMPLOYEES
emp_id PK | emp_name | dept_id | dept_name   | dept_location
----------+----------+---------+-------------+--------------
1         | Анна     | D-1     | Продажи     | Москва
2         | Иван     | D-1     | Продажи     | Москва
3         | Пётр     | D-2     | Логистика   | Казань
4         | Мария    | D-1     | Продажи     | Москва

Выпишем FD:

emp_id  -> emp_name
emp_id  -> dept_id
dept_id -> dept_name
dept_id -> dept_location

Атрибуты dept_name и dept_location зависят от dept_id. Но dept_id — non-prime атрибут (в ключ emp_id он не входит). Получается цепочка:

emp_id -> dept_id -> dept_name
(ключ)    (non-prime)  (non-prime)

dept_name зависит от ключа emp_id транзитивно — через посредника dept_id. Это и есть transitive dependency. Формально: non-prime атрибут dept_name зависит от non-prime атрибута dept_id.

Partial dependency здесь нет (ключ одноатомный), поэтому 2NF выполняется. Но транзитивная зависимость делает своё дело. Так как dept_name и dept_location зависят только от dept_id, они одинаковы во всех строках сотрудников одного отдела. Отдел D-1 «Продажи / Москва» в нашем примере продублирован трижды. Полный набор аномалий: переименование отдела — UPDATE множества строк сотрудников (риск рассинхрона); новый отдел без сотрудников не завести (insert anomaly — нет emp_id); увольнение последнего сотрудника отдела стирает сам отдел (delete anomaly).

Определение 3NF

Есть две эквивалентные формулировки 3NF. Полезно знать обе.

Формулировка 1 (через транзитивные зависимости). Таблица в 3NF, если она в 2NF и не содержит транзитивных зависимостей — то есть ни один non-prime атрибут не зависит от другого non-prime атрибута. Каждый non-prime атрибут зависит от ключа напрямую, «не через посредника».

Формулировка 2 (общий критерий). Таблица в 3NF, если для каждой нетривиальной функциональной зависимости X -> A выполнено хотя бы одно из двух условий:

• X является superkey, либо
• A является prime attribute (входит в какой-нибудь candidate key).

Вторая формулировка строже и удобнее для проверки. Прогоним по ней нашу таблицу. FD dept_id -> dept_name: является ли dept_id superkey? Нет — {dept_id}+ = {dept_id, dept_name, dept_location}, не все атрибуты. Является ли dept_name prime-атрибутом? Нет — единственный candidate key это emp_id, dept_name в него не входит. Оба условия нарушены — значит таблица не в 3NF.

Декомпозиция в 3NF: пошагово

Приведём EMPLOYEES к 3NF. Принцип: вынести атрибуты, зависящие от non-prime «посредника», в отдельную таблицу, где посредник станет первичным ключом.

Шаг 1. Найти candidate keys. {emp_id}+ = все атрибуты — candidate key. Других нет. Единственный candidate key — emp_id; prime-атрибут один — emp_id.

Шаг 2. Выписать FD и найти транзитивные. emp_id -> emp_name — напрямую от ключа, в порядке. emp_id -> dept_id — напрямую от ключа, в порядке. dept_id -> dept_name и dept_id -> dept_location — детерминант dept_id не superkey, правые части не prime — это транзитивные зависимости, дефект.

Шаг 3. Вынести зависимые от посредника атрибуты в свою таблицу. Атрибуты, зависящие от dept_id, переезжают в DEPARTMENTS, где dept_id становится первичным ключом:

DEPARTMENTS (3NF)
dept_id PK | dept_name  | dept_location
-----------+------------+--------------
D-1        | Продажи    | Москва
D-2        | Логистика  | Казань

Шаг 4. В исходной таблице оставить ключ и атрибуты прямой зависимости. В EMPLOYEES остаётся emp_name и dept_id; dept_id превращается в foreign key на DEPARTMENTS:

EMPLOYEES (3NF)
emp_id PK | emp_name | dept_id FK
----------+----------+-----------
1         | Анна     | D-1
2         | Иван     | D-1
3         | Пётр     | D-2
4         | Мария    | D-1

CREATE TABLE departments (
    dept_id       TEXT PRIMARY KEY,
    dept_name     TEXT NOT NULL,
    dept_location TEXT NOT NULL
);
CREATE TABLE employees (
    emp_id   INT  PRIMARY KEY,
    emp_name TEXT NOT NULL,
    dept_id  TEXT NOT NULL REFERENCES departments(dept_id)
);

Шаг 5. Проверить результат. DEPARTMENTS: единственный candidate key dept_id, FD dept_id -> dept_name имеет superkey слева — 3NF. EMPLOYEES: FD emp_id -> emp_name и emp_id -> dept_id имеют superkey emp_id слева, транзитивных зависимостей нет — 3NF.

Аномалии исчезли. Переименование отдела — UPDATE одной строки DEPARTMENTS. Новый отдел — INSERT INTO departments без сотрудников. Увольнение последнего сотрудника отдела трогает только EMPLOYEES, строка отдела цела. Декомпозиция lossless: общий атрибут dept_id — первичный ключ DEPARTMENTS, соединение по нему точно восстановит исходную таблицу.

Почему транзитивная зависимость опаснее, чем кажется

Транзитивную зависимость легко недооценить: «ну продублировано название отдела, не страшно». Покажем на цифрах, почему страшно — и почему 3NF на практике обязательна.

Избыточность от транзитивной зависимости масштабируется с размером дочерней группы. Если в отделе D-1 работает 500 сотрудников, то строка «D-1 / Продажи / Москва» физически записана 500 раз. Переименование отдела — это UPDATE 500 строк. И каждая такая строка — отдельная цель для рассинхрона: достаточно одной незавершённой транзакции, одного кривого WHERE, одной гонки — и часть сотрудников «работает в Продажах», а часть в старом названии. На вопрос «как называется отдел D-1» база начинает давать два ответа.

Сравним стоимость одной и той же операции «переименовать отдел» в двух схемах:

              | строк под UPDATE | риск рассинхрона | новый отдел без людей
--------------+------------------+------------------+----------------------
до 3NF        | N (= число       | высокий, растёт  | невозможно
(EMPLOYEES    |   сотрудников     | с N              | (insert anomaly)
 с dept_*)    |   отдела)        |                  |
--------------+------------------+------------------+----------------------
после 3NF     | ровно 1          | нулевой          | INSERT в departments
(DEPARTMENTS) | (одна строка)    | (один факт —     | без сотрудников
              |                  |  одна ячейка)    |

Разница не количественная, а качественная. До 3NF корректность операции зависит от того, безошибочно ли отработал код на всех N строках. После 3NF корректность гарантирована структурой: факт хранится в одной ячейке, рассинхронизировать его физически нечем. Транзитивная зависимость — это не «немного лишних байт», это перенос ответственности за инвариант с СУБД на надежду.

Поэтому 3NF — не «уровень для перфекционистов», а практический минимум для любой OLTP-схемы, которую правят в реальном времени. Остановиться раньше 3NF — значит сознательно оставить в базе незащищённые инварианты.

Worked example: вся цепочка 1NF -> 2NF -> 3NF

Соберём весь модуль в одном примере. Денормализованная таблица:

ORDER_REPORT (нарушает 1NF)
order_id | items                 | customer_id | customer_name | city_code | city_name
---------+-----------------------+-------------+---------------+-----------+----------
1001     | P-7:2, P-9:1          | 42          | Анна          | C-MOW     | Москва

FD: order_id -> customer_id, customer_id -> customer_name, customer_id -> city_code, city_code -> city_name, {order_id, product_id} -> qty, product_id -> product_name.

В 1NF — развернём список товаров в строки, заведём составной ключ {order_id, product_id}:

ORDER_REPORT_1NF(order_id, product_id, qty, product_name, customer_id, customer_name, city_code, city_name)
PK = {order_id, product_id}

В 2NF — уберём partial dependencies. От части ключа product_id зависит product_name; от части ключа order_id зависят customer_id, customer_name, city_code, city_name (через order_id -> customer_id -> ...):

PRODUCTS(product_id PK, product_name)
ORDERS(order_id PK, customer_id, customer_name, city_code, city_name)
ORDER_ITEMS(order_id FK, product_id FK, qty)   PK = {order_id, product_id}

В 3NF — в таблице ORDERS остались транзитивные зависимости: order_id -> customer_id -> customer_name и далее customer_id -> city_code -> city_name. Цепочку разворачиваем по посредникам customer_id и city_code:

CITIES(city_code PK, city_name)
CUSTOMERS(customer_id PK, customer_name, city_code FK)
ORDERS(order_id PK, customer_id FK)
PRODUCTS(product_id PK, product_name)
ORDER_ITEMS(order_id FK, product_id FK, qty)   PK = {order_id, product_id}

Пять таблиц, каждая в 3NF. Каждый факт хранится ровно один раз: название города — в CITIES, имя покупателя — в CUSTOMERS, название товара — в PRODUCTS. Все insert/update/delete-аномалии устранены.

Попробуй сам

Дана таблица в 2NF (ключ одноатомный):

BOOKS
book_id PK | title | publisher_id | publisher_name | publisher_country

FD: book_id -> title, book_id -> publisher_id, publisher_id -> publisher_name, publisher_id -> publisher_country.

Выполните на бумаге:

1. Найдите транзитивную зависимость. Назовите посредника и объясните, почему этот атрибут non-prime.
2. Проверьте таблицу по второй формулировке 3NF (X — superkey или A — prime) для FD publisher_id -> publisher_name. Какое из двух условий нарушено?
3. Приведите таблицу к 3NF. Укажите PK и FK получившихся таблиц.
4. Покажите на конкретной операции delete anomaly, который существовал до декомпозиции и исчез после.