Функциональная зависимость в базе данных: разбор

Функциональная зависимость - это базовое понятие реляционной теории, от которого зависит почти всё остальное: ключи, нормальные формы, корректность схемы. Если в таблице одно значение однозначно определяет другое, между ними есть функциональная зависимость. Звучит абстрактно, но именно из таких зависимостей выводят, какой набор столбцов может быть ключом и не разваливается ли таблица на аномалии при вставке и удалении. Разберём, как читается запись $X \to Y$, какие бывают виды зависимостей, как работают аксиомы Армстронга и зачем считать замыкание атрибутов. Если нужно проверить конкретное отношение - соберите условие в форме ниже и получите разбор по шагам.

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

Функциональная зависимость (ФЗ, англ. functional dependency) - это утверждение о том, что значения одного набора атрибутов однозначно определяют значения другого набора. Формально: атрибут (или набор атрибутов) $Y$ функционально зависит от $X$, если для любых двух строк отношения совпадение значений по $X$ влечёт совпадение значений по $Y$.

Записывается это стрелкой:

$$X \to Y$$

Читается «X определяет Y» или «Y функционально зависит от X». Левая часть $X$ называется детерминантом (определяющей частью), правая $Y$ - зависимой частью. Ключевое слово - «однозначно»: если у двух студентов один и тот же номер зачётной книжки, то и ФИО, и группа у них обязаны совпадать, иначе зависимость нарушена.

Важно: ФЗ - это свойство не конкретного набора строк, а предметной области. То, что в текущих данных два значения случайно совпали, ещё не делает зависимость истинной. Зависимость задаёт правило, которое должно выполняться всегда, при любых допустимых данных.

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

Как читать запись X → Y на примере

Возьмём таблицу Студенты(Зачётка, ФИО, Группа, Куратор). Здесь номер зачётки уникален для каждого студента, поэтому:

$$\text{Зачётка} \to \text{ФИО}, \quad \text{Зачётка} \to \text{Группа}$$

Это можно объединить: $\text{Зачётка} \to \{\text{ФИО}, \text{Группа}\}$. Зная номер зачётки, мы однозначно восстанавливаем и фамилию, и группу.

А вот зависимость $\text{Группа} \to \text{Куратор}$ работает в другую сторону: у каждой группы один куратор, поэтому группа определяет куратора. Но обратное неверно - один куратор может вести несколько групп, поэтому $\text{Куратор} \to \text{Группа}$ ложна.

Именно эта несимметричность и порождает структуру схемы: из набора истинных ФЗ выводят, какие столбцы достаточны как ключ, а какие зависимости лучше вынести в отдельную таблицу. Подробнее о том, как зависимости управляют разбиением таблиц, - в материале про нормализацию баз данных.

Виды функциональных зависимостей

Зависимости делят на несколько типов, и эта классификация прямо влияет на нормальные формы.

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

Частичная функциональная зависимость. $Y$ зависит от части составного ключа. Если бы в той же таблице хранилось ещё и ФИО, то $\text{Зачётка} \to \text{ФИО}$ - частичная зависимость от ключа $\{\text{Зачётка}, \text{Предмет}\}$. Такие зависимости нарушают вторую нормальную форму.

Транзитивная функциональная зависимость. Если $X \to Y$ и $Y \to Z$, причём $Y$ не ключ, то $X \to Z$ называется транзитивной. Пример: $\text{Зачётка} \to \text{Группа}$ и $\text{Группа} \to \text{Куратор}$ дают транзитивную $\text{Зачётка} \to \text{Куратор}$. Транзитивные зависимости устраняет третья нормальная форма.

Тривиальная зависимость. $X \to Y$ тривиальна, если $Y \subseteq X$ (правая часть содержится в левой). Например $\{\text{Зачётка}, \text{Группа}\} \to \text{Группа}$ - всегда истинна и информации не несёт.

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

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

Чтобы из заданного набора ФЗ выводить все остальные, которые из него логически следуют, используют систему правил вывода - аксиомы Армстронга (1974). Их три основных:

$$\begin{aligned} &\text{1. Рефлексивность:} && \text{если } Y \subseteq X, \text{ то } X \to Y \\ &\text{2. Пополнение:} && \text{если } X \to Y, \text{ то } XZ \to YZ \\ &\text{3. Транзитивность:} && \text{если } X \to Y \text{ и } Y \to Z, \text{ то } X \to Z \end{aligned}$$

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

• Объединение: если $X \to Y$ и $X \to Z$, то $X \to YZ$.
• Декомпозиция: если $X \to YZ$, то $X \to Y$ и $X \to Z$.
• Псевдотранзитивность: если $X \to Y$ и $WY \to Z$, то $WX \to Z$.

Система аксиом Армстронга обладает двумя важными свойствами. Она корректна (sound): любая выведенная зависимость действительно следует из исходных. И она полна (complete): любая логически следующая зависимость может быть выведена этими правилами. Поэтому замыкание набора ФЗ, полученное по Армстронгу, совпадает со множеством всех истинных зависимостей.

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

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

Алгоритм простой и итеративный:

$$\begin{aligned} &X^{+} := X \\ &\textbf{повторять:} \text{ для каждой ФЗ } A \to B, \text{ если } A \subseteq X^{+}, \text{ то } X^{+} := X^{+} \cup B \\ &\textbf{пока } X^{+} \text{ меняется} \end{aligned}$$

Замыкание решает сразу несколько задач. Во-первых, проверка любой зависимости $X \to Y$: она истинна тогда и только тогда, когда $Y \subseteq X^{+}$. Во-вторых, поиск ключа: если $X^{+}$ содержит все атрибуты отношения, то $X$ - суперключ. Замыкание гораздо дешевле полного перебора аксиом и легко программируется.

Функциональные зависимости и ключи

Связь ФЗ с ключами прямая. Суперключ - это набор $X$, для которого $X^{+}$ равно всем атрибутам отношения. Потенциальный (кандидатный) ключ - минимальный суперключ: ни один его атрибут нельзя выбросить, не потеряв определяемость всех остальных.

Поэтому поиск ключей сводится к работе с зависимостями: берут детерминанты, считают их замыкания и отбирают минимальные наборы, покрывающие всё отношение. Атрибут, входящий хотя бы в один потенциальный ключ, называют первичным; не входящий ни в один - непервичным. Эта терминология напрямую используется в определениях 2NF и 3NF: вторая форма запрещает частичную зависимость непервичных атрибутов от ключа, третья - транзитивную.

Связи между сущностями (например, один ко многим) тоже выражаются через зависимости: сторона «многие» функционально определяет сторону «один», и это диктует, где разместить внешний ключ.

Зачем всё это: аномалии и нормализация

Главная практическая ценность ФЗ - они предсказывают аномалии в плохо спроектированной таблице:

• Аномалия вставки: нельзя добавить факт о новой группе, пока в неё не зачислен хотя бы один студент (если куратор группы хранится только в таблице студентов).
• Аномалия обновления: при смене куратора группы придётся править его во всех строках студентов этой группы; пропустишь одну - данные противоречивы.
• Аномалия удаления: удалив последнего студента группы, потеряешь и сведения о кураторе.

Все три проблемы вызваны «лишними» зависимостями вроде транзитивной $\text{Зачётка} \to \text{Куратор}$. Нормализация - это последовательное разбиение отношения так, чтобы каждая неключевая зависимость держалась на ключе целиком и напрямую. То есть нормальные формы - это просто разные требования к тому, как ФЗ соотносятся с ключами.

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

• Путают ФЗ с корреляцией в данных. То, что в текущей выборке два столбца совпадают, не означает зависимости. ФЗ - правило предметной области, оно должно держаться при любых допустимых данных, а не на конкретном снимке.
• Считают зависимость симметричной. $X \to Y$ не влечёт $Y \to X$. Группа определяет куратора, но куратор группу - нет.
• Забывают про минимальность ключа. Суперключом может быть и весь набор столбцов, но ключ - это минимальный суперключ. Без проверки минимальности легко принять избыточный набор за ключ.
• Игнорируют транзитивность. Зависимость $\text{Зачётка} \to \text{Куратор}$ часто не записывают явно, потому что она «и так понятна», и из-за этого не замечают нарушение 3NF.
• Пытаются проверять зависимости перебором строк вместо замыкания. Замыкание $X^{+}$ даёт ответ алгоритмически и не зависит от текущего наполнения таблицы.

FAQ

Чем функциональная зависимость отличается от многозначной? Функциональная зависимость $X \to Y$ говорит, что одному значению $X$ соответствует ровно одно значение $Y$. Многозначная зависимость $X \twoheadrightarrow Y$ допускает целый набор значений $Y$ при фиксированном $X$, независимый от остальных атрибутов; она отвечает за четвёртую нормальную форму (4NF), тогда как функциональные - за 2NF и 3NF.

Как доказать, что зависимость следует из заданного набора? Посчитайте замыкание левой части. Зависимость $X \to Y$ выводима из набора $F$ тогда и только тогда, когда $Y \subseteq X^{+}$ относительно $F$. Это эквивалентно выводу через аксиомы Армстронга, но считается за один проход алгоритма.

Может ли детерминант быть пустым множеством? Формально да: зависимость $\varnothing \to Y$ означает, что атрибут $Y$ принимает одно и то же значение во всех строках (константа). На практике такие зависимости редки и обычно указывают на то, что столбец лишний или это служебная константа.

Коротко

Функциональная зависимость $X \to Y$ означает, что значения набора $X$ однозначно определяют значения $Y$ во всех допустимых данных, а не на конкретном снимке таблицы. Зависимости бывают полные, частичные, транзитивные и тривиальные - и именно эта классификация задаёт нормальные формы. Из набора ФЗ все следствия выводятся аксиомами Армстронга (рефлексивность, пополнение, транзитивность), а на практике удобнее считать замыкание атрибутов $X^{+}$: оно проверяет любую зависимость и находит ключи. Главная польза - предсказание аномалий вставки, обновления и удаления, ради устранения которых и проводят нормализацию.