Фундаментальный конспект по проверке декомпозиции схемы отношений: свойство соединения без потерь, возникновение ложных кортежей, теорема Риссанена, алгоритм табло, многозначные зависимости (4НФ), зависимости соединения (5НФ) и осознанная денормализация в аналитических системах.
В процессе проектирования реляционной базы данных исходные «плоские» таблицы декомпозируются (расщепляются) на несколько более компактных отношений. Цель нормализации — устранение аномалий вставки, обновления и удаления, обусловленных избыточностью функциональных зависимостей (ФЗ).
Однако произвольное расщепление таблицы может разрушить проект базы данных. Чтобы декомпозиция была корректной, она обязана удовлетворять двум фундаментальным критериям:
Термин «декомпозиция с потерями» (Lossy Decomposition) в теории баз данных означает вовсе не пропажу строк! Напротив, строк становится больше, чем было. «Потеря» заключается в потере точности информации: в таблице возникают ложные кортежи (Spurious Tuples), искажающие реальность.
Рассмотрим конкретное отношение R(Студент, Факультет, Куратор), отражающее назначение куратора студенту в рамках факультета. Исходное отношение содержит 2 реальных кортежа:
| Студент | Факультет | Куратор |
|---|---|---|
| Иванов | ИТ | Петров |
| Смирнов | ИТ | Сидоров |
Разбиваем отношение на две подсхемы: R1(Студент, Факультет) и R2(Студент, Куратор). Общий атрибут — Студент, который является первичным ключом для исходного отношения R.
Проекции содержат:
R1: (Иванов, ИТ), (Смирнов, ИТ).R2: (Иванов, Петров), (Смирнов, Сидоров).Выполняем естественное соединение R1 ⋈ R2 по общему ключу Студент: получаем ровно 2 исходных кортежа. Декомпозиция является соединением без потерь.
Разбиваем отношение на подсхемы: R1(Студент, Факультет) и R3(Факультет, Куратор). Общий атрибут — Факультет. Ни в R1, ни в R3 факультет не является ключом (на одном факультете учится много студентов и работает много кураторов).
Выполняем обратное естественное соединение R1 ⋈ R3 по условию R1.Факультет = R3.Факультет:
| Студент | Факультет | Куратор | Статус кортежа в БД |
|---|---|---|---|
| Иванов | ИТ | Петров | Истинный кортеж (был в исходной БД) |
| Иванов | ИТ | Сидоров | ЛОЖНЫЙ КОРТЕЖ (Spurious Tuple)! У Иванова куратор не Сидоров! |
| Смирнов | ИТ | Петров | ЛОЖНЫЙ КОРТЕЖ (Spurious Tuple)! У Смирнова куратор не Петров! |
| Смирнов | ИТ | Сидоров | Истинный кортеж (был в исходной БД) |
В результате некорректного соединения система сгенерировала ложные факты: теперь Иванов прикреплен сразу к двум кураторам, и Смирнов тоже. В финансовой системе это эквивалентно списанию чужого долга или дублированию транзакций!
Чтобы не моделировать ошибочные соединения вручную, финский ученый Йорма Риссанен в 1977 году доказал фундаментальную теорему:
Практическое правило инженера:
X = R₁ ∩ R₂.X⁺ относительно заданного множества ФЗ F.X⁺ все атрибуты R₁ (то есть X — суперключ R₁) либо все атрибуты R₂ (то есть X — суперключ R₂).Если отношение разбивается на 3 и более подсхем, теорема Риссанена не дает прямого ответа. В этом случае применяется матричный алгоритм табло (Ахо, Бири, Ульман).
Дано отношение R(A, B, C, D) и множество ФЗ F = {A → B, B → C, C → D}.
Предложена декомпозиция на 3 подсхемы: R₁(A, B), R₂(B, C), R₃(C, D). Проверим ее на соединение без потерь.
Строим матрицу: строки — подсхемы, столбцы — атрибуты. Если атрибут входит в подсхему, пишем a_j, иначе b_{ij}:
| Подсхема | A | B | C | D |
|---|---|---|---|---|
| R₁(A, B) | a₁ | a₂ | b₁₃ | b₁₄ |
| R₂(B, C) | b₂₁ | a₂ | a₃ | b₂₄ |
| R₃(C, D) | b₃₁ | b₃₂ | a₃ | a₄ |
Строки R₁ и R₂ имеют одинаковое значение в столбце B (a₂). Следовательно, по зависимости B → C их значения в столбце C должны совпасть. В строке R₂ стоит a₃, заменяем b₁₃ в первой строке на a₃:
| Подсхема | A | B | C | D |
|---|---|---|---|---|
| R₁(A, B) | a₁ | a₂ | a₃ | b₁₄ |
| R₂(B, C) | b₂₁ | a₂ | a₃ | b₂₄ |
| R₃(C, D) | b₃₁ | b₃₂ | a₃ | a₄ |
Теперь строки R₁, R₂ и R₃ имеют одинаковое значение в столбце C (a₃). В строке R₃ в столбце D стоит a₄. Распространяем a₄ на строки R₁ и R₂:
| Подсхема | A | B | C | D |
|---|---|---|---|---|
| R₁(A, B) | a₁ | a₂ | a₃ | a₄ |
| R₂(B, C) | b₂₁ | a₂ | a₃ | a₄ |
| R₃(C, D) | b₃₁ | b₃₂ | a₃ | a₄ |
В строке R₁ получена полная последовательность универсальных символов (a₁, a₂, a₃, a₄). Алгоритм завершается успешно: декомпозиция R₁(A, B), R₂(B, C), R₃(C, D) обладает свойством соединения без потерь!
Декомпозиция D = {R₁, …, Rₖ} отношения R сохраняет функциональные зависимости, если объединение зависимостей, проецируемых на отдельные таблицы, логически эквивалентно полному исходному множеству ФЗ:
Если зависимость разорвана, то при выполнении оператора INSERT в одну из таблиц СУБД не сможет проверить целостность бизнес-правила через обычный индекс PRIMARY KEY / UNIQUE — придется вызывать межтабличный JOIN, что снижает производительность на порядки.
Любая реляционная схема может быть декомпозирована в 3НФ с одновременным сохранением ФЗ и соединением без потерь. Для НФБК (BCNF) соединение без потерь гарантируется всегда, но сохранение зависимостей удается обеспечить не для всех схем отношений!
Что делать, когда функциональных зависимостей нет (все поля входят в первичный ключ), но избыточность все равно колоссальна? Классический пример: отношение R(Преподаватель, Дисциплина, Учебник).
Таблица вынуждена содержать декартово произведение всех дисциплин на все учебники каждого преподавателя:
| Преподаватель | Дисциплина | Учебник |
|---|---|---|
| Кузнецов | Базы данных | Дейт К. |
| Кузнецов | Базы данных | Коннолли Т. |
| Кузнецов | Сети ЭВМ | Дейт К. |
| Кузнецов | Сети ЭВМ | Коннолли Т. |
Если Кузнецов начнет рекомендовать 3-й учебник (Гарсиа-Молина), придется вставить 2 новые строки (по одной на каждую дисциплину). Это аномалия обновления!
Переход к 4НФ: разбиваем отношение на 2 независимые таблицы:
R₁(Преподаватель, Дисциплина)R₂(Преподаватель, Учебник)Избыточность устранена, аномалии исчезли!
В редких практических задачах возникают циклические трехсторонние ограничения, которые невозможно разбить на 2 таблицы без потерь, но можно разбить на 3 таблицы. Это описывается зависимостью соединения (Join Dependency):
Пятая нормальная форма (5NF / PJNF): отношение находится в 5НФ, если любая зависимость соединения в нем является тривиальной либо следует исключительно из потенциальных ключей отношения. 5НФ является теоретическим пределом декомпозиции без потерь в реляционной алгебре.
Хотя нормализация до 3НФ/4НФ защищает транзакционные системы (OLTP) от аномалий, в аналитических системах (хранилища данных, BI, витрины данных) нормализованная структура может вызывать серьезные проблемы производительности:
GROUP BY) по миллиардам строк создают огромную нагрузку на CPU и память.В связи с этим в OLAP применяется осознанная денормализация:
Денормализация допустима только при наличии компенсирующих архитектурных механизмов: триггеров согласования данных, потоков CDC (Change Data Capture) или регулярных регламентных ETL-пакетов сверки целостности.
С гарантией возникнут паразитные ложные кортежи (Spurious Tuples). Результирующая таблица будет содержать больше строк, чем исходная, и в ней появятся несуществующие в реальности комбинации данных (потеря семантической целостности).
При разбиении одной таблицы на две обратное соединение будет точным и без потерь тогда и только тогда, когда общие столбцы этих таблиц однозначно определяют все столбцы первой таблицы ИЛИ все столбцы второй таблицы (то есть общий столбец является ключом хотя бы для одной из них).
При функциональной зависимости X → Y каждому значению X соответствует ровно одно значение Y. При многозначной зависимости X ↠ Y значению X соответствует целое множество независимых значений Y, не зависящих от других атрибутов таблицы.
Для ускорения чтения и построения тяжелых отчетов. Денормализация исключает ресурсоемкие операции соединения (JOIN) десятков таблиц на петабайтных массивах данных.