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

1. Почему не работают «плоские таблицы»?

        Объединение всех атрибутов предметной области в единую широкую таблицу приводит к критическим дефектам архитектуры — аномалиям реляционных баз данных.
      

Аномалия избыточности и обновления

Повторение названий отделов и телефонов в сотнях строк приводит к растрате диска и риску рассогласования при частичном обновлении.

Аномалия вставки (Insertion)

Невозможно добавить новый отдел в систему, пока в него не нанят первый сотрудник с первичным ключом EmpID.

Аномалия удаления (Deletion)

При увольнении последнего сотрудника удаляется вся информация о самом отделе, его бюджете и телефоне.

Решение: Нормализация

Математически доказанная декомпозиция отношения на основе аппарата функциональных зависимостей (ФЗ).

2. Определение функциональной зависимости (ФЗ)

        Пусть R(U) — схема отношения. Зависимость X → Y означает, что атрибуты X однозначно определяют атрибуты Y во всех допустимых состояниях БД.
      

t₁[X] = t₂[X] ⟹ t₁[Y] = t₂[Y] (для любых двух кортежей t₁, t₂ ∈ r(R))

Компоненты зависимости

X (Детерминант / LHS): определяющий набор полей (например, Паспорт, Табельный_номер).
Y (Зависимая часть / RHS): однозначно определяемый набор полей (например, ФИО, Дата_рождения).

Семантический инвариант

ФЗ задается бизнес-логикой предметной области, а не случайным совпадением значений в конкретных 5 строках таблицы!

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

Тип зависимости	Формальное условие	Характеристика и влияние на нормализацию
Тривиальная	`Y ⊆ X`	Истинна всегда (`{ТабНомер, ФИО} → {ФИО}`). Не несет новой информации.
Полная	`X → Y` и `∀ X' ⊂ X: X' ↛ Y`	Зависимость от составного ключа в целом, а не от его фрагмента. База 2-й нормальной формы.
Частичная	`X' → Y`, где `X' ⊂ X`	Зависимость от части составного ключа. Нарушает 2НФ! Вызывает дублирование.
Транзитивная	`X → Y`, `Y → Z`, `Y ↛ X`	Зависимость через промежуточный неключевой атрибут. Нарушает 3НФ!

4. Базовые аксиомы Армстронга (1974)

        Система аксиом Уильяма Армстронга является корректной (выводит только истинные ФЗ) и полной (позволяет вывести любую истинную ФЗ).
      

1. Рефлексивность

Если Y ⊆ X, то X → Y

Любой набор атрибутов однозначно определяет любое свое подмножество: AB → A.

2. Пополнение

Если X → Y, то XZ → YZ

Добавление одинакового набора Z к обеим частям сохраняет однозначность вывода.

3. Транзитивность

X → Y и Y → Z ⟹ X → Z

Цепочка однозначных переходов передает зависимость от первого звена к последнему.

5. Производные правила вывода ФЗ

Объединение (Union)

X → Y и X → Z ⟹ X → YZ

Позволяет сгруппировать независимые следствия одного детерминанта в одну ФЗ.

Декомпозиция

X → YZ ⟹ X → Y и X → Z

Позволяет расщеплять правую часть на атомарные зависимости (Singleton RHS).

Псевдотранзитивность

X → Y и YZ → W ⟹ XZ → W

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

        Внимание: Правило расщепления детерминанта XY → Z ⟹ X → Z ЛОЖНО! Из того, что пара полей определяет результат, не следует, что одно поле способно сделать то же самое.
      

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

        Замыкание X⁺ — это множество ВСЕХ атрибутов схемы, функционально зависимых от X в силу системы правил вывода: X⁺ = { A ∈ U | F ⊢ X → A }.
      

Инициализация: Положить X⁺ := X.
Итерационное расширение: Просматривать каждую зависимость LHS → RHS из F. Если LHS ⊆ X⁺, то добавить X⁺ := X⁺ ∪ RHS.
Критерий останова: Повторять шаг 2 до тех пор, пока множество X⁺ не перестанет изменяться.

Практическая роль X⁺: Позволяет мгновенно проверить любую зависимость X → Y (достаточно проверить Y ⊆ X⁺) и найти ключи отношения.

7. Пошаговый пример трассировки X+

Отношение R(A, B, C, D, E) с ФЗ: F = { A → BC, CD → E, B → D, E → A }. Вычислим {B}⁺:

Шаг	Проверяемая зависимость	Условие LHS ⊆ Текущее X⁺	Результат добавления в X⁺
0	Инициализация	Базовый набор	`{ B }`
1	`B → D`	`{B} ⊆ {B}` (Да)	`{ B, D }`
2	`A → BC`, `CD → E`, `E → A`	Ни один LHS не содержится в `{B, D}`	Изменений нет. Стоп!

Итог: { B }⁺ = { B, D } ≠ U (множество {B} не является ключом отношения R).

8. Суперключ и потенциальный ключ

Суперключ (Superkey)

Любое подмножество атрибутов K, чье замыкание покрывает ВСЮ схему отношения:

K⁺ = U

Суперключ однозначно идентифицирует кортеж, но может содержать «лишние» поля.

Потенциальный ключ (Candidate Key)

Минимальный суперключ. Никакое его строгое подмножество не является суперключом:

K⁺ = U И ∀ K' ⊂ K: (K')⁺ ≠ U

Один из кандидатных ключей выбирается как первичный ключ (PK).

        Атрибуты: Первичный (prime) — входит хотя бы в один кандидатный ключ. Неключевой (non-prime) — не входит ни в один кандидатный ключ.
      

9. Эвристика L-R-B-N: быстрый поиск всех ключей

Класс	Участие атрибута в ФЗ	Правило включения в кандидатный ключ
L (Left)	Только в детерминантах (слева)	ОБЯЗАН входить во ВСЕ кандидатные ключи.
R (Right)	Только в зависимых частях (справа)	НИКОГДА НЕ ВХОДИТ в кандидатные ключи.
N (Neither)	Не участвует ни в одной ФЗ	ОБЯЗАН входить во ВСЕ кандидатные ключи.
B (Both)	Встречается и слева, и справа	Кандидат на дополнение ключа. Перебираются комбинации с `(L ∪ N)`.

        Следствие: Если (L ∪ N)⁺ = U, то L ∪ N — единственный потенциальный ключ отношения!
      

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

        Множество F_c называется минимальным покрытием для F, если F_c ≡ F (эквивалентны) и в F_c отсутствует избыточность.
      

1. Синглтон справа

Все правые части состоят строго из одного атрибута: X → A.

2. Нет лишних полей слева

В составных детерминантах XA → B нет посторонних атрибутов (X → B ∉ F⁺).

3. Нет лишних ФЗ

Ни одну ФЗ нельзя удалить без изменения замыкания: (F \ {f}) ⊬ f.

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

Шаг 1. Расщепление правых частей:
Каждую ФЗ X → {A₁, A₂, ...} заменяем на набор X → A₁, X → A₂...
Шаг 2. Устранение посторонних атрибутов в детерминантах (LHS):
Для XA → B вычисляем {X}⁺. Если B ∈ {X}⁺, атрибут A удаляется: X → B.
Шаг 3. Удаление избыточных зависимостей:
Для каждой f: X → A временно исключаем ее из множества и вычисляем {X}⁺ без f. Если A ∈ {X}⁺, зависимость f удаляется навсегда.

12. Сквозной пример: минимизация покрытия

Дано: F = { X → Y, Y → Z, XZ → W, W → V }.

Шаг 1: Правые части уже атомарны (Y, Z, W, V).
Шаг 2: Проверяем XZ → W. Вычисляем {X}⁺ в F: {X}⁺ = {X, Y, Z, W, V}. Так как Z ∈ {X}⁺, атрибут Z в левой части избыточен! Заменяем XZ → W на X → W.
Шаг 3: Текущее множество: { X → Y, Y → Z, X → W, W → V }. Проверяем каждую ФЗ — ни одна не выводится из остальных.

Минимальное покрытие: F_min = { X → Y, Y → Z, X → W, W → V }

13. Практическая работа и критерии оценки (4 балла)

Обучающиеся выполняют индивидуальный вариант в интерактивном листе zanyatie.html:

Критерий	Баллы	Что проверяется экспертом
Вычисление замыкания X⁺	2 балла	Точность пошаговой трассировки, верность включения всех зависимых атрибутов.
Определение первичных ключей	1 балл	Обоснование через метод L-R-B-N, нахождение минимальных суперключей.
Минимальное покрытие и самопроверка	1 балл	Устранение избыточных полей и ФЗ, аргументированные ответы на вопросы.

xkcd #327: Exploits of a Mom (Bobby Tables)

Культовый интернет-мем: «Exploits of a Mom» (комикс про «Little Bobby Tables», xkcd №327).
Автор: Randall Munroe. Источник: xkcd.com/327. Лицензия: Creative Commons Attribution-NonCommercial 2.5 (CC BY-NC 2.5).
Связь с темой занятия: Пренебрежение математическим моделированием данных, отсутствие нормализации и строгих ограничений первичных/внешних ключей превращает базу данных в уязвимую плоскую свалку. Строгий анализ функциональных зависимостей — основа надежности реляционных схем!