BCNF: каждая нетривиальная FD имеет superkey слева

В прошлом модуле мы дошли до 3NF — практического стандарта нормализации. Но 3NF содержит одно послабление, которое в редких, но реальных случаях оставляет лазейку для аномалий. Нормальная форма Бойса-Кодда (BCNF, Boyce-Codd Normal Form) закрывает эту лазейку. Её сформулировали Raymond Boyce и Edgar Codd в 1974 году как более строгую версию 3NF.

В этом уроке мы разберём, чем именно BCNF строже 3NF, на конкретной таблице покажем случай, где 3NF выполняется, а BCNF — нет, и обсудим важнейший компромисс: BCNF-декомпозиция всегда lossless, но может не сохранять зависимости. Этот компромисс — причина, по которой BCNF не объявляют автоматически «лучше» 3NF.

Определение BCNF

Таблица находится в BCNF, если для каждой нетривиальной функциональной зависимости X -> Y детерминант X является superkey.

Сравним с общим критерием 3NF. Напомним его: таблица в 3NF, если для каждой нетривиальной FD X -> A выполнено X — superkey или A — prime attribute.

Разница — ровно в одном союзе. 3NF даёт послабление «или A — prime»: она разрешает зависимость X -> A с не-superkey-детерминантом X, при условии что зависимый атрибут A входит в какой-нибудь candidate key. BCNF этого послабления не даёт: единственное допустимое условие — X является superkey. Точка.

Отсюда сразу следует: любая таблица в BCNF находится и в 3NF. Если каждый детерминант — superkey, то первое условие 3NF выполнено для всех FD автоматически. Обратное неверно: таблица может быть в 3NF и не быть в BCNF — именно тогда, когда она «держится» на послаблении про prime-атрибут.

Когда 3NF выполняется, а BCNF — нет

Лазейку видно только на таблице с перекрывающимися candidate keys — несколькими ключами, которые делят общие атрибуты. Классический пример — расписание занятий.

Условие предметной области: студент посещает курс в назначенное время; курс ведёт ровно один преподаватель; преподаватель в один момент времени ведёт ровно один курс.

LESSONS(student_id, slot, course, teacher)

Из условия — функциональные зависимости:

FD1: {student_id, slot} -> course      студент в данный слот на одном курсе
FD2: {student_id, slot} -> teacher     => и у одного преподавателя
FD3: {course} -> teacher               у курса один преподаватель
FD4: {teacher} -> course               преподаватель в момент времени ведёт один курс

Найдём candidate keys через замыкания. {student_id, slot}+ = все четыре атрибута — это candidate key. А {student_id, course}? Замыкание: по FD4 нет, но course -> teacher (FD3) даёт teacher, далее {student_id, slot} мы не получаем… посчитаем аккуратно: {student_id, course} -> по FD3 += teacher -> {student_id, course, teacher}. Атрибута slot не достаём — не ключ. А вот {student_id, teacher}: по FD4 teacher -> course += course -> {student_id, teacher, course} — slot опять не достаём, не ключ.

Получается, единственный candidate key — {student_id, slot}. Тогда prime-атрибуты — student_id и slot; non-prime — course и teacher.

Проверяем 3NF. Проблемная зависимость — FD4 teacher -> course (и симметрично FD3 course -> teacher). Является ли teacher superkey? Нет — {teacher}+ = {teacher, course}, не все атрибуты. Тогда проверяем послабление: является ли course prime-атрибутом? Да — course… стоп, course в наш единственный candidate key {student_id, slot} не входит. Значит course non-prime, и FD4 нарушает 3NF.

Сделаем пример честнее: добавим, что каждый студент занимается с каждым преподавателем максимум в одном слоте — тогда {student_id, teacher} становится candidate key, и появляются перекрывающиеся ключи. Чтобы не усложнять, возьмём канонический трёхатрибутный вариант, где лазейка 3NF/BCNF видна в чистом виде.

Канонический пример лазейки

Рассмотрим таблицу: преподаватель ведёт предметы, и за каждым предметом закреплён один преподаватель.

TEACHING(student, subject, teacher)

Предметная область:

FD1: {student, subject} -> teacher    студент по предмету занимается у одного препода
FD2: {teacher} -> subject             каждый преподаватель ведёт ровно один предмет

Замыкания. {student, subject}+: по FD1 += teacher -> все атрибуты — candidate key. {student, teacher}+: по FD2 teacher -> subject += subject -> все атрибуты — тоже candidate key! Два candidate key: {student, subject} и {student, teacher}. Они перекрываются — общий атрибут student.

Prime-атрибуты — те, что входят хоть в один ключ: student, subject, teacher. Все три атрибута prime, non-prime атрибутов нет вообще.

3NF выполняется. Проверим проблемную FD2 teacher -> subject. teacher — superkey? Нет ({teacher}+ = {teacher, subject}). Тогда послабление: subject — prime? Да, subject входит в candidate key {student, subject}. Условие 3NF «X — superkey ИЛИ A — prime» выполнено за счёт второго дизъюнкта. Таблица в 3NF.

BCNF не выполняется. Для той же FD2 teacher -> subject критерий BCNF требует, чтобы teacher был superkey. Он не superkey. Послабления про prime у BCNF нет. Таблица не в BCNF.

И вот здесь видно, что лазейка 3NF — не формальность. Посмотрим на данные:

student | subject  | teacher
--------+----------+----------
Анна    | Физика   | Петров
Иван    | Физика   | Петров
Мария   | Физика   | Петров
Анна    | Химия    | Сидоров

Факт «Петров ведёт Физику» (это FD2: teacher -> subject) дублируется в каждой строке студента, занимающегося у Петрова. Это избыточность, и она даёт аномалии. Update: если Петров переводится на другой предмет, менять надо все строки с Петровым — пропуск даёт рассинхрон. Insert: нельзя записать «Козлов ведёт Биологию», пока у Козлова нет ни одного студента — student входит в оба candidate key и не может быть NULL. Delete: удаление последнего студента Петрова стирает факт «Петров ведёт Физику».

3NF эти аномалии пропустила именно из-за послабления «A — prime». BCNF их ловит.

Декомпозиция в BCNF и её цена

Алгоритм приведения к BCNF: пока есть нарушающая FD X -> Y (где X не superkey), разбиваем таблицу на две — (X плюс все атрибуты, зависящие от X) и (X плюс остальные атрибуты). Разложим TEACHING по нарушающей FD2 teacher -> subject:

TEACHER_SUBJECT(teacher PK, subject)        -- из FD2
    Петров  | Физика
    Сидоров | Химия

ENROLLMENT(student, teacher)                -- остаток; PK = {student, teacher}
    Анна  | Петров
    Иван  | Петров
    Мария | Петров
    Анна  | Сидоров

Проверим обе таблицы. TEACHER_SUBJECT: единственная нетривиальная FD teacher -> subject, teacher — её первичный ключ, то есть superkey — BCNF. ENROLLMENT: нетривиальных FD с не-superkey слева нет — BCNF. Факт «Петров ведёт Физику» теперь хранится один раз. Аномалии устранены.

Но у BCNF-декомпозиции есть цена. Сформулируем точно — это ключевой факт всего модуля:

Что значит «потеряли зависимость» на нашем примере. Исходная FD1 — {student, subject} -> teacher. После декомпозиции student и subject оказались в разных таблицах: student в ENROLLMENT, subject в TEACHER_SUBJECT. Теперь нет ни одной таблицы, где FD1 можно проверить локально, обычным UNIQUE-ограничением. Чтобы убедиться, что студент по предмету не попал к двум преподавателям, придётся соединять обе таблицы — а это уже не декларативный constraint, а отдельная проверка.

Декомпозиция при этом честно lossless: ENROLLMENT JOIN TEACHER_SUBJECT по teacher восстановит исходную таблицу без лишних строк, потому что общий атрибут teacher — ключ таблицы TEACHER_SUBJECT (формальный критерий lossless разберём отдельным уроком).

Когда останавливаться на 3NF

Из-за компромисса «BCNF теряет зависимости» практика такова: доводят схему до BCNF, если при этом сохраняются все зависимости. Если же BCNF-декомпозиция ломает важную FD, а её проверка критична для корректности данных — сознательно останавливаются на 3NF, оставляя одну «неидеальную» зависимость, но сохраняя возможность проверять все ограничения декларативно.

Это инженерное решение, а не признак небрежности. 3NF в таком случае — обоснованный выбор: чуть больше потенциальной избыточности в обмен на то, что СУБД сама стережёт все бизнес-правила. Поэтому формулировка «BCNF строго лучше 3NF» — распространённое заблуждение, и теперь вы понимаете, почему оно неверно.

Попробуй сам

Дана таблица бронирования переговорных:

BOOKINGS(employee, time_slot, room)

Предметная область: сотрудник в данный слот сидит в одной комнате; в данный слот в комнате — один сотрудник; за каждым сотрудником закреплена постоянная комната (всегда работает из неё).

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

1. Выпишите функциональные зависимости из условия. Их три.
2. Найдите все candidate keys через замыкания. Перекрываются ли они?
3. Проверьте таблицу на 3NF и на BCNF по их критериям. Найдите FD, которая проходит 3NF (за счёт prime-атрибута), но нарушает BCNF.
4. Выполните BCNF-декомпозицию по нарушающей FD. Затем проверьте: сохранилась ли каждая исходная FD в пределах одной таблицы? Если какая-то FD «разъехалась» по двум таблицам — назовите её и объясните, почему это пример not dependency-preserving.