Функциональные зависимости и аксиомы Армстронга

Нормализация — это не набор ритуалов «разбей таблицу на куски». Это инженерная дисциплина, у которой есть точный математический фундамент. Этот фундамент — функциональные зависимости (functional dependencies, FD). Пока вы не умеете находить FD в данных и работать с ними формально, любые правила «1NF, 2NF, 3NF» останутся заучиванием без понимания. С функциональными зависимостями всё становится механикой: можно доказать, что таблица в нужной форме, можно вычислить ключи, можно проверить декомпозицию.

Этот урок — про сам инструмент. Мы разберём, что такое FD, как из небольшого набора FD вывести все остальные через аксиомы Армстронга, и как алгоритмом замыкания атрибутов находить ключи таблицы. Дальше в модуле всё опирается на эти три вещи.

Что такое функциональная зависимость

Функциональная зависимость X -> Y означает: значение набора атрибутов X однозначно определяет значение набора атрибутов Y. Если в двух строках таблицы совпали значения X, то в этих строках обязаны совпасть и значения Y. Запись X -> Y читается «X определяет Y» или «Y функционально зависит от X». X называют детерминантом, Y — зависимой частью.

Ключевое слово здесь — «однозначно». FD — это не наблюдение «в текущих данных так получилось». Это утверждение о правиле предметной области, которое верно для всех возможных строк, которые когда-либо появятся в таблице. FD выводят из бизнес-смысла, а не из конкретного снимка данных.

Возьмём таблицу заказов интернет-магазина:

ORDERS(order_id, customer_id, customer_email, product_id, product_name, qty, unit_price)

Какие FD здесь действуют, исходя из смысла предметной области:

• order_id -> customer_id — у заказа ровно один покупатель.
• customer_id -> customer_email — у покупателя ровно один email.
• order_id -> customer_email — следствие двух предыдущих (об этом ниже).
• product_id -> product_name — у товара ровно одно название.
• product_id -> unit_price — цена закреплена за товаром (упрощение для примера).
• {order_id, product_id} -> qty — количество определяется парой «заказ + товар».

Обратите внимание: customer_email -> customer_id тоже верно, если email уникален у каждого покупателя. А вот product_name -> product_id верно только если названия товаров не повторяются — это решение бизнеса, и его надо подтвердить, а не предполагать.

Тривиальная FD — это зависимость, где правая часть является подмножеством левой: {order_id, product_id} -> order_id. Она верна всегда, безо всяких условий, и поэтому не несёт информации. Нетривиальная FD — та, где правая часть содержит хотя бы один атрибут, которого нет в левой. Нормализация занимается только нетривиальными FD: именно они говорят о реальной структуре данных.

Аксиомы Армстронга: вывод новых FD

Если задан набор FD, из него логически следуют другие FD. order_id -> customer_id и customer_id -> customer_email вместе дают order_id -> customer_email, даже если последнюю никто не записывал явно. Чтобы выводить такие следствия не на интуиции, а строго, используют аксиомы Армстронга — три правила, сформулированные William Armstrong в 1974 году. Они доказанно полны (выводят все верные FD) и корректны (не выводят ни одной ложной).

Из этих трёх выводятся удобные производные правила:

• Объединение (union): если X -> Y и X -> Z, то X -> YZ. Несколько зависимостей с одним детерминантом можно слить в одну.
• Декомпозиция (decomposition): если X -> YZ, то X -> Y и X -> Z. Зависимость с составной правой частью можно разбить.
• Псевдотранзитивность: если X -> Y и WY -> Z, то WX -> Z.

Правило объединения и декомпозиции означает важную вещь: правую часть FD всегда можно привести к одному атрибуту без потери информации. Поэтому в анализе нормализации FD часто записывают в «каноническом» виде, где справа стоит ровно один атрибут.

Покажем транзитивность на нашей таблице. Дано order_id -> customer_id и customer_id -> customer_email. По аксиоме транзитивности немедленно следует order_id -> customer_email. Эта выведенная FD — не лишняя деталь: именно она в уроке про 3NF окажется транзитивной зависимостью, которую нормализация устраняет.

Замыкание атрибутов: алгоритм

Самый практичный инструмент — замыкание набора атрибутов (attribute closure), обозначается X+. Это множество всех атрибутов, которые функционально определяются набором X при заданном наборе FD. Если вы умеете считать X+, вы умеете проверять, является ли X ключом, и можете проверять любую FD: X -> Y верна тогда и только тогда, когда Y содержится в X+.

Алгоритм прост и всегда завершается:

closure(X, F):              # X — стартовый набор, F — набор FD
    result = X              # начинаем с самого X (рефлексивность)
    repeat:
        for каждой FD (A -> B) из F:
            if A является подмножеством result:
                result = result + B      # добавляем B
    until result перестал меняться
    return result

Идея: начинаем с самих атрибутов X и многократно «дотягиваем» всё, до чего можем дойти по FD, пока множество не перестанет расти. Применим к таблице ORDERS. Набор FD:

F1: order_id -> customer_id
F2: customer_id -> customer_email
F3: product_id -> product_name
F4: product_id -> unit_price
F5: {order_id, product_id} -> qty

Вычислим замыкание {order_id, product_id}+:

result = {order_id, product_id}                  стартуем
F1: order_id ⊆ result      -> += customer_id     result = {order_id, product_id, customer_id}
F2: customer_id ⊆ result   -> += customer_email  result += customer_email
F3: product_id ⊆ result    -> += product_name    result += product_name
F4: product_id ⊆ result    -> += unit_price      result += unit_price
F5: {order_id,product_id}⊆ -> += qty             result += qty
итог: {order_id, product_id, customer_id, customer_email, product_name, unit_price, qty}

Замыкание {order_id, product_id}+ содержит все семь атрибутов таблицы. Это означает: пара {order_id, product_id} однозначно определяет всю строку — то есть является superkey.

Теперь проверим, что пара минимальна. Посчитаем замыкание каждого атрибута по отдельности:

{order_id}+   = {order_id, customer_id, customer_email}      -- НЕ все атрибуты
{product_id}+ = {product_id, product_name, unit_price}       -- НЕ все атрибуты

Ни один атрибут поодиночке не определяет всю строку. Значит, из пары {order_id, product_id} нельзя выкинуть ни один атрибут — это candidate key (минимальный superkey). Так алгоритм замыкания формально находит ключи: перебираем наборы атрибутов, считаем замыкание, набор является superkey, если замыкание покрывает все атрибуты, и candidate key, если при этом ни одно подмножество не является superkey.

Введём ещё два термина, без которых не обойтись дальше. Prime attribute (ключевой атрибут) — атрибут, входящий хотя бы в один candidate key. В ORDERS это order_id и product_id. Non-prime attribute (неключевой атрибут) — все остальные: customer_id, customer_email, product_name, unit_price, qty. Различие prime / non-prime будет центральным в правилах 2NF и 3NF.

Поиск всех candidate keys

Перебирать все подмножества атрибутов в поисках ключей — дорого: для таблицы из n атрибутов подмножеств 2^n. Есть приём, который резко сокращает работу: он опирается на то, какие атрибуты вообще могут или не могут входить в ключ.

Разделим все атрибуты таблицы на три группы по тому, как они встречаются в наборе FD:

• Атрибуты, которые встречаются только слева в FD (или не встречаются вообще). Такой атрибут не определяется ничем — значит он обязан входить в каждый candidate key. Иначе замыкание ключа его не достанет.
• Атрибуты, которые встречаются только справа. Такой атрибут определяется другими — он не нужен в ключе и не входит ни в один candidate key.
• Атрибуты, встречающиеся и слева, и справа. Они могут входить в ключ, а могут и нет — их перебирают.

Алгоритм: возьмём множество «только слева»-атрибутов как обязательное ядро будущего ключа. Посчитаем его замыкание. Если оно уже покрывает все атрибуты — это единственный candidate key, перебор не нужен. Если нет — поочерёдно добавляем к ядру атрибуты из третьей группы и ищем минимальные комбинации, дающие полное замыкание.

Применим к таблице ORDERS с её набором FD F1..F5. Распределим атрибуты:

только слева:  order_id, product_id          -> обязаны быть в каждом ключе
только справа: customer_email, product_name, unit_price, qty
и там, и там:  customer_id                   -> кандидат на перебор

Ядро — {order_id, product_id}. Его замыкание мы уже считали: оно покрывает все семь атрибутов. Значит ядро само является superkey, добавлять customer_id не нужно, и {order_id, product_id} — единственный candidate key таблицы. Перебор 2^7 подмножеств свёлся к одному вычислению замыкания.

Попробуй сам

Возьмите таблицу расписания университета:

SCHEDULE(course_id, course_title, teacher_id, teacher_name, room, slot, student_id)

Действующие функциональные зависимости:

course_id  -> course_title
course_id  -> teacher_id
teacher_id -> teacher_name
{room, slot} -> course_id
{course_id, slot} -> room

Выполните три задания на бумаге:

1. Вычислите замыкание {room, slot}+ по алгоритму. Покрывает ли оно все атрибуты, кроме student_id? Что это говорит о роли student_id?
2. Является ли {room, slot, student_id} superkey? А candidate key? Проверьте минимальность, посчитав замыкание подмножеств.
3. Найдите ещё хотя бы один candidate key. Подсказка: посмотрите на FD {course_id, slot} -> room и подумайте, какой набор с участием slot и student_id тоже даёт полное замыкание.

Запишите для каждого шага, какую FD вы применили — именно это и есть «работа с FD руками», которой пользуются при нормализации.