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

Функциональная зависимость — это формальный язык, на котором описывают «правила» предметной области. На нём строится вся теория нормализации.

Функциональная зависимость X → Y означает: если два кортежа совпадают по атрибутам X, то они обязательно совпадают и по Y. Иными словами, значение X однозначно определяет значение Y.

Зачем нужны функциональные зависимости

Нормализация (проектирование схемы без аномалий) не работает «на глаз» — ей нужен точный вход. Этим входом служат функциональные зависимости (ФЗ): они формально фиксируют правила предметной области, которые иначе остались бы в головах. «У одного почтового индекса один город» — это правило, и записывается оно как index → city. Из набора таких ФЗ теория механически выводит ключи и нормальные формы. Поэтому без ФЗ нет и строгой нормализации — это её фундамент.

Определение через кортежи

Строго: в отношении R зависимость X → Y выполняется, если для любых двух кортежей t1 и t2 из равенства t1[X] = t2[X] следует t1[Y] = t2[Y]. Здесь X и Y — наборы атрибутов. Слева — детерминант (определяющая часть), справа — зависимая часть.

Важно: ФЗ — это утверждение о всех возможных состояниях отношения, то есть о правиле предметной области, а не о конкретных данных в таблице сейчас. Если сегодня в таблице у каждого города один индекс, это ещё не значит, что city → index — настоящая ФЗ: завтра у города может появиться второй индекс. ФЗ задаёт проектировщик, исходя из смысла, а не из текущих строк.

Пример из интернет-магазина

Возьмём «плоскую» таблицу заказов с дублированием: OrderLine(order_id, product_id, client_name, product_name, cena, qty). Сформулируем её ФЗ:

• order_id → client_name — у заказа один клиент.
• product_id → product_name, cena — артикул определяет название и цену.
• {order_id, product_id} → qty — количество определяется парой «заказ + товар».

Эти три ФЗ — формальное описание правил магазина. Заметьте: client_name зависит только от части ключа (order_id), а product_name — только от product_id. Именно такие «частичные» зависимости позже породят аномалии и потребуют декомпозиции.

Полное множество ФЗ и его замыкание

Заданный нами набор ФЗ — это лишь «исходные» правила. Но из них логически следуют другие. Если order_id → client_id и client_id → client_city, то и order_id → client_city — мы этого не записывали, но это следует. Множество всех ФЗ, выводимых из исходного набора F, называют замыканием множества зависимостей и обозначают F⁺. Именно F⁺, а не исходный список, определяет истинные ограничения на данные. Полностью выписывать F⁺ обычно не нужно (оно огромно), но важно понимать: когда мы проверяем нормальную форму или ищем ключи, мы рассуждаем о всех следствиях, а не только о записанных правилах. Инструмент для работы с F⁺, не выписывая его целиком, — замыкание атрибутов, которому посвящён следующий урок.

Минимальное покрытие

У одного и того же набора ограничений может быть много эквивалентных формулировок. Минимальное (каноническое) покрытие — это «самая экономная» версия набора ФЗ, эквивалентная исходной: без избыточных зависимостей, без лишних атрибутов в левых частях, с единичными правыми частями. Зачем оно нужно? Во-первых, с минимальным набором проще рассуждать и строить декомпозицию. Во-вторых, алгоритмы нормализации (например, синтез 3NF) работают именно с минимальным покрытием. Идея проста: убрать всё, что и так выводится из остального. Если order_id → client_city выводится транзитивно, в минимальном покрытии её не держат — она избыточна. Минимальное покрытие — это «скелет» правил предметной области, очищенный от производных следствий.

Тривиальные и нетривиальные ФЗ

ФЗ X → Y называется тривиальной, если Y ⊆ X (правая часть содержится в левой). Например, {order_id, product_id} → order_id — тривиальна и выполняется всегда, по определению. Тривиальные ФЗ не несут информации о предметной области. Нетривиальная ФЗ — та, где правая часть не целиком содержится в левой; именно нетривиальные ФЗ интересны для нормализации.

ФЗ и здравый смысл предметной области

Важно не превратить ФЗ в формальную игру в стрелочки. Каждая ФЗ — это утверждение о реальности, и проверять её нужно вопросом «а так ли это в жизни?». index → city верна, потому что почтовый индекс по определению закреплён за населённым пунктом. А вот city → index — ложна: у крупного города множество индексов. isbn → title верна (ISBN однозначно задаёт издание), но title → isbn — нет (одно название могут носить разные книги). Эта проверка «в обе стороны» — обязательная гигиена: направление ФЗ определяется смыслом, а не симметрией. Ошибка в направлении или выдуманная зависимость загрязняют весь дальнейший анализ: неверные ключи, неверная нормализация. Поэтому, выписывая ФЗ, проговаривайте их словами и сверяйтесь с предметной областью — это дешевле, чем ловить последствия потом.

Аксиомы Армстронга

В 1974 году Уильям Армстронг предложил три правила вывода, которые позволяют из заданного набора ФЗ получить все логически следующие из него ФЗ. Эта система правил полна (выводит всё, что следует) и надёжна (не выводит лишнего).

Транзитивность — самая важная для практики: именно она порождает транзитивные зависимости, которые мы будем устранять в 3NF. Если order_id → client_id и client_id → client_city, то order_id → client_city — город зависит от заказа не напрямую, а через клиента.

Производные правила

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

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

Эти правила — не новые аксиомы, а следствия трёх основных. Они экономят рассуждения: например, благодаря декомпозиции мы всегда можем считать, что в правой части ФЗ стоит один атрибут.

Связь ФЗ с ключами

Здесь сходятся две темы: функциональные зависимости и ключи из раздела про реляционную модель. Вспомните: суперключ — это набор атрибутов, уникально идентифицирующий кортеж. На языке ФЗ это звучит точнее: X — суперключ тогда и только тогда, когда X функционально определяет все атрибуты отношения, то есть X → (все атрибуты). А потенциальный ключ — это минимальный такой X. Видите, как понятие ключа, которое раньше мы вводили интуитивно («уникально идентифицирует»), теперь получает строгое определение через ФЗ. Это не просто красиво: благодаря такой формулировке ключи можно вычислять механически, проверяя, определяет ли набор атрибутов всё отношение. Именно этим займётся алгоритм замыкания в следующем уроке, превратив поиск ключей из искусства в процедуру.

Зачем всё это: к замыканию и ключам

Цель — научиться по набору ФЗ вычислять, что чем определяется, и находить ключи. Если из ФЗ выводится, что некий набор атрибутов определяет все атрибуты отношения, — это суперключ. Механизм такого вывода называется замыканием набора атрибутов, и им мы займёмся в следующем уроке, причём с запускаемым кодом.

Типичные ошибки

• Вывод ФЗ из текущих данных. «Сейчас у каждого клиента один город» не доказывает ФЗ — это может быть совпадением; ФЗ диктуется смыслом, а не строками.
• Путают направление. index → city не означает city → index: у города несколько индексов.
• Считают тривиальные ФЗ полезными. X → (часть X) выполняется всегда и для нормализации бесполезна.
• Игнорируют транзитивность. Не замечают цепочку X → Y → Z и оставляют скрытую зависимость, которая позже даст аномалии.

Итог

• ФЗ X → Y: значение X однозначно определяет Y; это формальная запись правил предметной области.
• ФЗ — утверждение о всех состояниях отношения, а не о текущих данных.
• Аксиомы Армстронга (рефлексивность, пополнение, транзитивность) полны и надёжны — выводят все следствия.
• Транзитивность порождает транзитивные зависимости — главную мишень 3NF.