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

1. Детальный поминутный тайминг учебного занятия

Занятие ориентировано на формирование строгой математической культуры проектирования реляционных схем. Теория функциональных зависимостей (ФЗ) переводит интуитивное проектирование («мне кажется, эти поля должны быть вместе») в доказательную инженерную дисциплину.

Сравнительная сетка хронометража (80 и 60 минут)

2. Теоретический фундамент: функциональные зависимости

2.1. Формальное математическое определение

Пусть R(U) — схема отношения над универсальным множеством атрибутов U = {A₁, A₂, ..., Aₙ}, а r(R) — произвольное корректное (допустимое) мгновенное состояние (экземпляр) отношения. Пусть X ⊆ U и Y ⊆ U — подмножества атрибутов.

Множество атрибутов X называется детерминантом (левой частью, Left-Hand Side, LHS), а Y — зависимой частью (правой частью, Right-Hand Side, RHS).

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

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

3. Система логического вывода: аксиомы Армстронга

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

3.1. Базовые аксиомы Армстронга

3.2. Производные правила вывода (Derived Rules)

Базовые аксиомы А1–А3 образуют полный и корректный (sound and complete) базис. Из них строго выводятся удобные вспомогательные правила:

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

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

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

Вход: Множество атрибутов U, множество ФЗ F, целевое подмножество атрибутов X ⊆ U.
Выход: Замыкание X⁺ относительно F.

1. Инициализация:
   X⁺ := X;

2. Цикл расширения:
   REPEAT
      old_X⁺ := X⁺;
      ДЛЯ КАЖДОЙ ФЗ (LHS → RHS) ИЗ F:
         ЕСЛИ LHS ⊆ X⁺ ТОГДА
            X⁺ := X⁺ ∪ RHS;
   UNTIL X⁺ == old_X⁺;

3. ВОЗВРАТ X⁺;

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

5.1. Терминологическая иерархия

• Суперключ (Superkey): Подмножество атрибутов K ⊆ U называется суперключом отношения R(U), если его замыкание покрывает все отношение: K⁺ = U.
• Потенциальный (кандидатный) ключ (Candidate Key): Минимальный суперключ. Подмножество K ⊆ U является потенциальным ключом, если:
  1. K⁺ = U (свойство однозначной идентификации);
  2. Для любого собственного подмножества K' ⊂ K выполняется (K')⁺ ≠ U (свойство неприводимости/минимальности).
• Первичный ключ (Primary Key): Один из потенциальных ключей, официально назначенный проектировщиком в качестве основного идентификатора кортежа.
• Первичные (ключевые) и вторичные (неключевые) атрибуты: Атрибут A ∈ U называется первичным (prime attribute), если он входит в состав хотя бы одного потенциального ключа. В противном случае он является неключевым (non-prime).

5.2. Эвристический алгоритм классификации атрибутов (L, R, B, N)

Для ускорения поиска ключей и отсечения экспоненциального перебора 2^|U| атрибуты отношения разбиваются на 4 непересекающиеся категории по их позиции во множестве ФЗ F:

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

Два множества ФЗ F и G называются эквивалентными (F ≡ G), если их замыкания совпадают: F⁺ = G⁺ (любая зависимость из F выводима из G, и наоборот). Множество F_c называется минимальным (каноническим) покрытием для F, если F_c ≡ F и выполняются три строгих условия:

1. Синглтон в правой части (Singleton RHS): Правая часть каждой ФЗ в F_c состоит ровно из одного атрибута: X → A.
2. Отсутствие посторонних атрибутов слева (No extraneous LHS attributes): Ни в одной ФЗ X → A ∈ F_c нельзя удалить атрибут B ∈ X так, чтобы полученное множество осталось эквивалентным. Формально: для X' = X \ {B} проверяется, выводимо ли X' → A из F_c.
3. Отсутствие избыточных зависимостей (No redundant FDs): Ни одну зависимость f ∈ F_c нельзя удалить из покрытия. Формально: ∀ f ∈ F_c: (F_c \ {f}) ⊬ f.

Алгоритм построения Minimal Cover

Шаг 1. Расщепление правых частей:
       Каждую зависимость X → {A₁, A₂, ..., Aₖ} заменяем на набор X → A₁, X → A₂, ..., X → Aₖ.

Шаг 2. Устранение посторонних атрибутов в детерминантах (LHS):
       Для каждой зависимости X → A, где |X| ≥ 2:
          Для каждого атрибута B ∈ X:
             Пусть X' = X \ {B}.
             Вычисляем замыкание (X')⁺ относительно текущего множества ФЗ.
             Если A ∈ (X')⁺, то атрибут B является посторонним (избыточным) слева.
             Заменяем X → A на X' → A.

Шаг 3. Устранение избыточных зависимостей:
       Для каждой зависимости f: X → A в текущем множестве:
          Пусть F' = F \ {f}.
          Вычисляем замыкание X⁺ относительно F'.
          Если A ∈ X⁺, то зависимость f избыточна (выводится из оставшихся).
          Удаляем f: F := F'.

7. Типовые ошибки обучающихся и педагогические приемы

7.1. Рейтинг когнитивных затруднений студентов

7.2. Рекомендуемые педагогические приемы

• Прием «Аномальный шок»: Начать занятие не с формул, а с таблицы Сотрудники_Проекты(EmpID, ProjID, Dept, Salary, Role), в которой при увольнении сотрудника теряется информация о проекте (аномалия удаления), а для изменения названия отдела требуется переписать 500 строк (аномалия обновления). Показать, что причина бед — в непризнанных ФЗ.
• Инструмент «Трассировочная таблица замыкания»: При вычислении X⁺ рисовать на доске таблицу из трех колонок: «Шаг итерации», «Примененная ФЗ», «Текущее замыкание X⁺». Это исключает пропуск шагов и делает логику прозрачной.
• Прием «Мемори-чек Армстронга»: Запоминание трех базовых правил через мнемонику:
  • Рефлексивность: «Часть целого всегда известна, если известно целое».
  • Пополнение: «Если знаешь ответ, то добавив лишний вопрос к условию и ответу, ответ останется верным».
  • Транзитивность: «Друг моего друга — через цепочку однозначности».