Нормальная форма Бойса-Кодда (БКНФ): детерминант суперключ

Нормальная форма Бойса-Кодда (БКНФ, по-английски BCNF) - это усиленный вариант третьей нормальной формы, в котором требование одно и предельно строгое: детерминант любой нетривиальной функциональной зависимости обязан быть суперключом. Никаких поблажек вроде «или зависимый атрибут входит в ключ», которые допускает 3НФ, здесь нет. Эта строгость нужна, чтобы закрыть редкий, но коварный класс аномалий - когда таблица формально в 3НФ, а избыточность всё равно осталась. Ниже разберём, что такое детерминант и суперключ, чем именно БКНФ строже 3НФ, на каком примере они расходятся и как декомпозировать таблицу до БКНФ. Если нужно проверить конкретную схему - соберите запрос в форме ниже.

Что требует БКНФ: одно правило вместо двух

Третья нормальная форма формулируется через два разных случая: для зависимости $X \rightarrow A$ либо $X$ - суперключ, либо $A$ - ключевой атрибут (входит хотя бы в один потенциальный ключ). Бойс и Кодд заметили, что вторая лазейка («или $A$ ключевой») и порождает остаточные аномалии. БКНФ её закрывает.

Таблица находится в БКНФ, если для каждой нетривиальной функциональной зависимости $X \rightarrow A$ детерминант $X$ является суперключом отношения. Нетривиальная - значит $A$ не входит в $X$. Суперключ - любой набор атрибутов, функционально определяющий все остальные. Иначе говоря: всё, что в таблице что-то определяет, обязано определять вообще всё. Если этого нет - БКНФ нарушена.

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

Детерминант и суперключ: два ключевых термина

Чтобы проверять БКНФ механически, нужно уверенно различать два понятия.

Детерминант - это левая часть функциональной зависимости, то, от чего зависят другие атрибуты. В записи $X \rightarrow Y$ детерминантом является $X$. В таблице детерминантов может быть несколько: каждый источник зависимости - отдельный детерминант.

Суперключ - это набор атрибутов, который однозначно определяет строку, то есть функционально определяет все атрибуты отношения. Минимальный суперключ называют потенциальным (кандидатным) ключом. Любой потенциальный ключ - суперключ, но не любой суперключ минимален.

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

Чем БКНФ строже третьей нормальной формы

3НФ и БКНФ совпадают почти всегда. Расхождение возможно только при особой конфигурации ключей, поэтому БКНФ иногда называют «3.5НФ» - она лежит между 3НФ и четвёртой формой.

Разница ровно в одном слове. 3НФ разрешает зависимость $X \rightarrow A$, если $A$ - ключевой атрибут, даже когда $X$ не суперключ. БКНФ это запрещает: $X$ обязан быть суперключом всегда, независимо от того, ключевой $A$ или нет. Условие срабатывает, когда в таблице есть несколько перекрывающихся составных потенциальных ключей - общих атрибутов у них достаточно, чтобы появился «частичный детерминант».

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

Из-за этого любая таблица в БКНФ автоматически находится и в 3НФ, но не наоборот. БКНФ - более сильное требование, и приводит оно к более «чистой» схеме ценой одного компромисса, о котором ниже.

Классический пример: 3НФ выполнена, БКНФ - нет

Возьмём учебную таблицу Запись, описывающую закрепление студентов за преподавателями по предметам:

Правила предметной области таковы:

• каждый преподаватель ведёт ровно один предмет;
• по каждому предмету студент закреплён за одним преподавателем.

Отсюда две функциональные зависимости:

$$\{\text{Студент}, \text{Предмет}\} \rightarrow \text{Преподаватель}, \qquad \text{Преподаватель} \rightarrow \text{Предмет}$$

Потенциальных ключей два: $\{\text{Студент}, \text{Предмет}\}$ и $\{\text{Студент}, \text{Преподаватель}\}$. Атрибут Предмет входит во второй ключ, то есть он ключевой. Поэтому зависимость $\text{Преподаватель} \rightarrow \text{Предмет}$ для 3НФ допустима: пусть Преподаватель и не суперключ, зато Предмет ключевой - лазейка 3НФ сработала.

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

Как декомпозировать таблицу до БКНФ

Алгоритм прямолинеен: находим нарушающую зависимость $X \rightarrow A$ и выносим её в отдельную таблицу. Для примера выше нарушает $\text{Преподаватель} \rightarrow \text{Предмет}$. Создаём таблицу с детерминантом в роли ключа:

Таблица Преподаватели:

Таблица Записи:

Теперь Преподаватель - суперключ в Преподаватели (он определяет Предмет), а в Записи ключ составной $\{\text{Студент}, \text{Преподаватель}\}$, и других зависимостей нет. Обе таблицы в БКНФ. Соединение по Преподаватель восстанавливает исходное отношение без потерь.

Общий рецепт: для каждой зависимости $X \rightarrow A$, где $X$ не суперключ, заводим таблицу $(X, A)$ с ключом $X$, а в исходной удаляем $A$, оставляя $X$ как связующий атрибут.

Цена строгости: потеря сохранения зависимостей

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

В примере выше зависимость $\{\text{Студент}, \text{Предмет}\} \rightarrow \text{Преподаватель}$ после декомпозиции «размазалась» между двумя таблицами: ни в одной из них целиком она не проверяется. Чтобы гарантировать её, нужен JOIN при каждой вставке - а это дорого и неудобно для СУБД.

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

Алгоритм проверки таблицы на БКНФ

Чтобы проверить отношение, действуйте по шагам:

1. Выпишите все нетривиальные функциональные зависимости (минимальное покрытие удобнее).
2. Найдите все потенциальные ключи: переберите наборы атрибутов и проверьте через замыкание, определяет ли набор все остальные атрибуты.
3. Для каждой зависимости $X \rightarrow A$ проверьте, является ли $X$ суперключом (то есть замыкание $X^{+}$ содержит все атрибуты).
4. Если хотя бы у одной зависимости детерминант не суперключ - таблица не в БКНФ; эту зависимость и выносим декомпозицией.
5. Повторяйте, пока все детерминанты не станут суперключами.

Замыкание $X^{+}$ - это множество атрибутов, выводимых из $X$ по зависимостям. Если $X^{+}$ равно всему набору атрибутов, $X$ - суперключ, и зависимость БКНФ не нарушает.

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

• Путать детерминант с ключом. БКНФ требует, чтобы детерминант был суперключом, а не наоборот. Атрибут может быть ключевым (входить в ключ) и при этом стоять справа в нарушающей зависимости - как Предмет в примере.
• Считать, что 3НФ всегда влечёт БКНФ. Влечение обратное: БКНФ строже, из неё следует 3НФ, но не наоборот. Таблица в 3НФ может нарушать БКНФ при перекрывающихся составных ключах.
• Декомпозировать до БКНФ любой ценой. Если разбиение теряет сохранение зависимостей, а остаточная аномалия некритична, разумнее остаться в 3НФ. БКНФ не догма.
• Проверять только один потенциальный ключ. При нескольких перекрывающихся ключах нужно найти их все - нарушение БКНФ как раз и прячется в зависимости на атрибут «чужого» ключа.
• Игнорировать тривиальные зависимости как помеху. Зависимость $X \rightarrow A$ при $A \subseteq X$ тривиальна и БКНФ не нарушает никогда - её в проверку не включают.

FAQ

Чем БКНФ отличается от 3НФ простыми словами? 3НФ разрешает зависимость на ключевой атрибут даже от не-суперключа, БКНФ это запрещает: любой детерминант обязан быть суперключом. Различие проявляется только при нескольких перекрывающихся составных ключах; в остальных схемах 3НФ и БКНФ совпадают.

Всегда ли можно привести таблицу к БКНФ без потерь? Декомпозиция до БКНФ всегда возможна без потерь соединения, но не всегда сохраняет функциональные зависимости. Если сохранение зависимостей важно, иногда сознательно останавливаются на 3НФ - это нормальный инженерный компромисс.

Что такое детерминант в функциональной зависимости? Детерминант - это левая часть зависимости $X \rightarrow Y$, набор атрибутов $X$, от которого зависят остальные. БКНФ требует, чтобы каждый детерминант был суперключом, то есть определял все атрибуты отношения, а не только часть.

Коротко

Нормальная форма Бойса-Кодда (БКНФ) - усиление 3НФ с единственным требованием: детерминант любой нетривиальной функциональной зависимости должен быть суперключом. Она убирает остаточную избыточность, которую 3НФ пропускает через лазейку «или зависимый атрибут ключевой». Расхождение 3НФ и БКНФ возникает только при перекрывающихся составных ключах, классический пример - Запись(Студент, Предмет, Преподаватель). Лечится декомпозицией: нарушающая зависимость выносится в таблицу с детерминантом-ключом. Плата за строгость - БКНФ гарантирует отсутствие потерь соединения, но не сохранение зависимостей, поэтому в проектах 3НФ остаётся целью по умолчанию, а БКНФ применяют точечно.