Нормализация БД: проверка связей

1. Проверка связей: зачем идти дальше 3НФ?

Границы классической нормализации

На предыдущем занятии мы привели таблицы к 3НФ и НФБК. Казалось бы, проект идеален? В реальности декомпозиция может скрывать фатальные дефекты:

  • Появление паразитных кортежей при сборке (Lossy Join).
  • Разрушение контроля бизнес-правил (Dependency Loss).
  • Скрытая избыточность независимых списков (MVD).

Два обязательных инварианта декомпозиции

  1. Соединение без потерь (Lossless-Join): операция R1 ⋈ R2 обязана восстанавливать исходное отношение в точности.
  2. Сохранение зависимостей (Dependency Preservation): все ФЗ должны проверяться локально без внешних JOIN.

Декомпозиция без соединения без потерь — это профессиональная непригодность схемы БД!

2. Ложные кортежи (Spurious Tuples) — анатомия катастрофы

Термин «потеря данных» (Lossy) обманчив. В реляционной алгебре всегда выполняется включение:

R ⊆ π_{R1}(R) ⋈ π_{R2}(R)

В чем суть потери?

Физически строки не пропадают. Теряется точность информации! В базе возникают строки-призраки (Spurious Tuples), комбинации которых никогда не существовало в реальном мире.

Бизнес-риски в продакшене

  • Финансы: привязка чужого платежа или кредитного долга.
  • Склад: фиктивное дублирование остатков номенклатуры.
  • Учет: выставление чужих заказов сторонним клиентам.

3. Контрпример: декомпозиция с потерями

Исходное отношение R(Студент, Факультет, Куратор). Ошибочно разбиваем по неключевому атрибуту Факультет:

Студент Факультет Куратор Результат естественного соединения R1(Студент, Факультет) ⋈ R3(Факультет, Куратор)
Иванов ИТ Петров Истинный факт (исходная запись)
Иванов ИТ Сидоров ЛОЖНЫЙ КОРТЕЖ! Система прикрепила Иванова ко второму куратору!
Смирнов ИТ Петров ЛОЖНЫЙ КОРТЕЖ! Система прикрепила Смирнова к чужому куратору!
Смирнов ИТ Сидоров Истинный факт (исходная запись)

Итог: 2 исходные строки превратились в 4 строки из-за соединения по неключевому полю!

4. Теорема Риссанена для бинарной декомпозиции

Как математически гарантировать отсутствие ложных кортежей при разбиении таблицы на две части?

Формулировка теоремы (Йорма Риссанен, 1977 г.)

Декомпозиция R на {R₁, R₂} является соединением без потерь относительно F ⟺
(R₁ ∩ R₂ → R₁) ∈ F⁺   ИЛИ   (R₁ ∩ R₂ → R₂) ∈ F⁺

Инженерное правило: общий набор столбцов (R₁ ∩ R₂) обязан быть суперключом хотя бы одной из полученных таблиц!

Алгоритм проверки за 3 шага

  1. Выделяем пересечение: X = R₁ ∩ R₂.
  2. Считаем замыкание X⁺ по заданным ФЗ.
  3. Если X⁺ ⊇ R₁ или X⁺ ⊇ R₂ — соединение гарантированно БЕЗ потерь!

5. Алгоритм табло (Tableau Algorithm) для k отношений

Что делать, если отношение декомпозировано на 3, 4 или более таблиц? Теорема Риссанена для бинарных декомпозиций здесь бессильна. Используется метод табло (Ахо, Бири, Ульман):

Структура матрицы табло

  • Строки матрицы соответствуют подсхемам R₁, R₂, …, Rₖ.
  • Столбцы соответствуют атрибутам A₁, A₂, …, Aₙ.
  • Если атрибут Aⱼ ∈ Rᵢ, в ячейку пишется универсальный символ aⱼ.
  • Иначе пишется локальный индексный символ bᵢⱼ.

Критерий завершения

По очереди применяются ФЗ X → Y: строки, совпадающие по столбцам X, уравниваются по столбцам Y (с приоритетом универсального символа aⱼ).

Если хотя бы одна строка матрицы заполнилась целиком символами a₁…aₙ — соединение без потерь доказано!

6. Трассировка алгоритма табло

Схема R(A, B, C, D), зависимости F = {A → B, B → C, C → D}. Подсхемы: R₁(A,B), R₂(B,C), R₃(C,D).

Подсхема A B C D Ход вывода
R₁(A, B) a₁ a₂ a₃ (по B→C) a₄ (по C→D) Строка полностью заполнена символами a!
R₂(B, C) b₂₁ a₂ a₃ a₄ (по C→D) Подтянуто значение a₄
R₃(C, D) b₃₁ b₃₂ a₃ a₄ Исходные значения

Вывод: строка R₁ содержит (a₁, a₂, a₃, a₄) — декомпозиция является соединением без потерь!

7. Сохранение функциональных зависимостей

Математическое условие

(π_{R1}(F) ∪ π_{R2}(F) ∪ …)⁺ = F⁺

Декомпозиция сохраняет ФЗ, если объединение всех локальных зависимостей логически покрывает исходное множество ограничений.

Цена потери ФЗ в продакшене

Если зависимость разорвана между таблицами, СУБД не может проверить бизнес-правило через индекс PRIMARY / UNIQUE KEY.

Приходится делать дорогостоящие триггеры или межтабличные JOIN на каждую вставку, что обрушивает производительность OLTP.

Теорема: 3НФ гарантирует одновременное сохранение ФЗ и соединение без потерь. Для НФБК сохранение ФЗ гарантировано не всегда!

8. Ограничения аппарата ФЗ: когда НФБК бессильна

Представим отношение R(Преподаватель, Дисциплина, Учебник):

  • Преподаватель ведет несколько независимых курсов (Базы данных, Сети).
  • Преподаватель рекомендует несколько учебников (Дейт, Коннолли).
  • Учебники рекомендуются независимо от курса!

Парадокс первичного ключа

В этом отношении нет нетривиальных функциональных зависимостей! Первичный ключ — все три атрибута: {Преподаватель, Дисциплина, Учебник}.

Отношение формально находится в НФБК, но содержит чудовищное декартово произведение строк: 2 курса × 2 книги = 4 строки. Добавление 1 книги требует вставки 2 строк! Это аномалия обновления.

9. Многозначные зависимости (MVD: X ↠ Y)

X ↠ Y (X многозначно определяет Y) ⟺
множество значений Y, соответствующих паре (X, Z), зависит только от X и не зависит от Z.

Свойство симметрии

Если в отношении R(X, Y, Z) выполняется X ↠ Y, то автоматически выполняется и симметричная многозначная зависимость X ↠ Z.

Пример в предметной области

Преподаватель ↠ Дисциплина

Преподаватель ↠ Учебник

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

10. Четвертая нормальная форма (4NF) и теорема Фейгина

Теорема Рональда Фейгина (1977 г.)

Декомпозиция отношения R(X, Y, Z) на R₁(X, Y) и R₂(X, Z) является соединением без потерь тогда и только тогда, когда в R выполняется X ↠ Y | Z.

Определение 4НФ и решение проблемы

Отношение находится в 4НФ, если оно в НФБК и для любой нетривиальной зависимости X ↠ Y детерминант X является суперключом.

Решение: декомпозируем на 2 независимые таблицы:

R₁(Преподаватель, Дисциплина)  и  R₂(Преподаватель, Учебник)

11. Зависимости соединения (JD) и 5-я нормальная форма (5NF)

Зависимость соединения (Join Dependency)

⋈ [R₁, R₂, …, Rₘ]

Отношение R удовлетворяет JD, если оно равно естественному соединению m своих проекций. Существуют циклические схемы, которые нельзя разбить на 2 таблицы без потерь, но можно без потерь разбить на 3 таблицы!

Пятая нормальная форма (5NF / PJNF)

Проективно-соединительная нормальная форма (Project-Join Normal Form): любая зависимость соединения следует из потенциальных ключей отношения.

5НФ — теоретический предел нормализации без потерь в реляционной модели данных.

12. Контролируемая денормализация в OLAP

OLTP (Транзакции)

  • Нормализация до 3НФ / 4НФ.
  • Быстрая запись, вставка, удаление.
  • Нулевая избыточность, строгая защита от аномалий.

OLAP (Аналитика / DWH)

  • Сознательная денормализация.
  • Минимизация JOIN при агрегациях.
  • Схема «Звезда» (Star Schema), плоские витрины данных, материализованные представления.

Инженерный баланс: в аналитике мы жертвуем дисковым пространством и простотой обновления ради сверхбыстрого чтения терабайтных таблиц.

13. Риски денормализации и компенсирующие механизмы

Денормализация — это не отказ от проектирования, а управляемый архитектурный компромисс. При дублировании полей возникают риски:

Архитектурные риски

  • Рассинхронизация данных (Data Inconsistency).
  • Аномалии при смене наименования сущности.
  • Многократное разрастание объема дискового хранилища.

Компенсирующие механизмы

  • Триггеры СУБД: каскадное обновление дубликатов.
  • CDC (Change Data Capture): потоковая синхронизация (Debezium, Kafka).
  • ETL/ELT сверка: регламентные пакеты ночного аудита целостности.

14. Архитектурная строгость: цена ошибок в связях

xkcd 327: Exploits of a Mom (Little Bobby Tables)
Тематический интернет-мем: «Exploits of a Mom» (культовый веб-комикс про «Little Bobby Tables», xkcd №327).
Автор: Randall Munroe. Первоисточник: xkcd.com/327. Лицензия: Creative Commons Attribution-NonCommercial 2.5 Generic (CC BY-NC 2.5).
Связь с темой занятия: Нормализация и проверка декомпозиции на отсутствие потерь (Lossless-Join) обеспечивают математическую строгость и целостность схемы БД. Если связи между отношениями спроектированы с ошибками, в базе возникают аномалии и ложные кортежи, а небрежное отношение к структуре данных приводит к фатальным сбоям при любых манипуляциях, вплоть до классического Robert'); DROP TABLE Students;--.
1 / 15