Нормализация БД: функциональные зависимости

1. Почему проектировщику необходима нормализация?

Создание базы данных без строгого математического анализа часто приводит к объединению множества разнородных атрибутов в одну «универсальную» таблицу. Рассмотрим наивную структуру базы данных компании, где в едином отношении хранятся сведения о сотрудниках, их отделах и проектных ролях:

Такой подход порождает четыре классические аномалии реляционных баз данных:

2. Понятие и классификация функциональных зависимостей (ФЗ)

2.1. Формальное определение

Пусть R(U) — схема отношения, где U — совокупность всех атрибутов. Пусть X и Y — произвольные подмножества атрибутов (X ⊆ U, Y ⊆ U).

Множество X называют детерминантом (определяющим набором), а Y — зависимой частью.

2.2. Классификация функциональных зависимостей

• Тривиальная зависимость: Правая часть полностью содержится в левой: Y ⊆ X.
  Пример: {Паспорт, ФИО} → {ФИО}. Такая зависимость тривиально истинна всегда, так как зная набор данных, мы всегда знаем его составную часть.
• Нетривиальная зависимость: Правая часть содержит хотя бы один атрибут, отсутствующий в детерминанте: Y ⊈ X.
  Пример: {НомерСчета} → {Баланс, Валюта}.
• Полная функциональная зависимость: Атрибут Y зависит от составного детерминанта X в целом, но не зависит ни от одной его части.
  Пример: Оценка студента зависит от пары {СтудентID, ПредметID} → Оценка. Отдельно от СтудентID или от ПредметID оценка не зависит.
• Частичная функциональная зависимость: Атрибут зависит не от всего составного ключа, а лишь от некоторой его части.
  Пример: В отношении с ключом {СтудентID, ПредметID} зависимость СтудентID → НомерГруппы является частичной. Наличие частичных зависимостей неключевых полей от первичного ключа нарушает Вторую нормальную форму (2НФ).
• Транзитивная функциональная зависимость: Зависимость вида X → Z, опосредованная промежуточным набором Y: если X → Y и Y → Z, причем обратной зависимости Y ↛ X не существует, а Z не входит в X ∪ Y.
  Пример: ТабельныйНомер → НомерОтдела, а НомерОтдела → ТелефонОтдела. Зависимость ТабельныйНомер → ТелефонОтдела является транзитивной. Наличие транзитивных зависимостей неключевых полей нарушает Третью нормальную форму (3НФ).

3. Аксиомы Армстронга и матрица применения правил вывода

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

3.1. Базовые аксиомы

1. Рефлексивность (Reflexivity): Если Y ⊆ X, то X → Y. В частности, X → X.
2. Пополнение (Augmentation): Если X → Y, то для любого множества атрибутов Z верно: XZ → YZ (а также XZ → Y).
3. Транзитивность (Transitivity): Если X → Y и Y → Z, то X → Z.

3.2. Матрица применения правил вывода Армстронга на практике

Для ускорения логического анализа проектировщики используют вспомогательные производные правила. Матрица ниже иллюстрирует, когда и какое правило следует применять в инженерных расчетах:

4. Алгоритм нахождения замыкания множества атрибутов X+

Замыканием множества атрибутов X относительно множества зависимостей F (обозначается X⁺) называется совокупность всех атрибутов схемы, которые функционально определяются набором X на основе правил вывода: X⁺ = {A ∈ U | F ⊢ X → A}.

Вычисление замыкания — ключевой алгоритм всей реляционной теории. С его помощью проверяется истинность любой произвольной ФЗ X → Y (достаточно проверить, входит ли Y ⊆ X⁺) и определяются первичные ключи отношений.

Пошаговый псевдокод

Вход: Набор атрибутов X, множество зависимостей F.
Выход: Множество X⁺.

Шаг 1. Инициализировать результат исходным набором:
       X⁺ := X;

Шаг 2. В цикле просматривать все зависимости A → B из F:
       ЕСЛИ левая часть A является подмножеством X⁺ (A ⊆ X⁺),
       ТО добавить атрибуты правой части B к результату:
          X⁺ := X⁺ ∪ B;

Шаг 3. Повторять шаг 2 до тех пор, пока на очередной итерации
       множество X⁺ перестанет пополняться новыми атрибутами (достигнута неподвижная точка).

Шаг 4. Вернуть X⁺.

Пошаговый пример трассировки 1

Дано отношение со схемой R(A, B, C, D, E, F) и множеством зависимостей:

Задача: Вычислить замыкание атрибутов {B, E}⁺.

Итог: {B, E}⁺ = {A, B, C, D, E}. Атрибут F в замыкание не вошел, следовательно {B, E} не является суперключом.

5. Определение потенциальных ключей отношения

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

• Суперключ (Superkey): Любой набор атрибутов K, чье замыкание включает все атрибуты отношения: K⁺ = U.
• Потенциальный (кандидатный) ключ (Candidate Key): Минимальный суперключ. Это означает, что K⁺ = U, но если убрать из K хотя бы один атрибут, то замыкание перестанет покрывать всё отношение.
• Первичный ключ (Primary Key): Один из потенциальных ключей, официально назначенный проектировщиком для связывания таблиц через внешние ключи.

Эвристический алгоритм поиска ключей: Метод L-R-B-N

Полный перебор всех 2ⁿ подмножеств атрибутов неэффективен. Профессиональный проектировщик классифицирует атрибуты на 4 группы по их участию в ФЗ F:

6. Каноническое (минимальное) покрытие ФЗ (Minimal Cover)

В реальных проектах множество бизнес-правил может содержать избыточные зависимости и лишние поля в составных ключах. Минимальное покрытие F_c для множества зависимостей F — это эквивалентный набор ФЗ минимального размера без логического балласта.

Три требования к минимальному покрытию:

1. Каноническая правая часть (Singleton RHS): Каждая зависимость имеет ровно один атрибут справа: X → A.
2. Неизбыточность детерминантов (No extraneous LHS attributes): Ни из одной левой части нельзя удалить атрибут без потери выводимости.
3. Неизбыточность зависимостей (No redundant FDs): Ни одну ФЗ нельзя удалить целиком без потери выводимости.

Пошаговый пример минимизации покрытия

Дано отношение R(A, B, C, D) и исходное множество зависимостей:

Шаг 1. Расщепление правых частей (Singleton RHS)

Зависимость AB → CD расщепляем по правилу декомпозиции на AB → C и AB → D:

Удаляем явный дубликат AB → D: F₁ = { AB → C, AB → D, A → B, C → D, D → C }.

Шаг 2. Проверка и устранение посторонних атрибутов слева (LHS)

Проверим составной детерминант AB → C. Можно ли удалить B (проверяем A → C)?
Вычисляем замыкание {A}⁺ во множестве F₁:
{A}⁺: по A → B получаем {A, B}; по AB → C получаем {A, B, C}.
Так как C ∈ {A}⁺, атрибут B в детерминанте AB → C является посторонним (избыточным)! Заменяем AB → C на A → C.
Аналогично для AB → D: D ∈ {A}⁺, заменяем на A → D.
Текущее множество:

Шаг 3. Устранение избыточных зависимостей

Проверяем каждую зависимость на возможность вывода из остальных:

• Проверяем A → D: удалим ее и проверим {A}⁺ в оставшемся множестве {A → C, A → B, C → D, D → C}.
  {A}⁺ = {A} ∪ {C} (из A→C) ∪ {B} (из A→B) ∪ {D} (из C→D) = {A, B, C, D}.
  Атрибут D выводится через транзитивную цепочку A → C и C → D! Следовательно, зависимость A → D избыточна и удаляется.
• Проверяем остальные зависимости (A → C, A → B, C → D, D → C) — ни одна из них не выводится из оставшихся.

7. Вопросы и задания для самопроверки