Проектирование баз данных и реляционная теория: Нормальные формы и все такое

Введение в теорию проектирования баз данных

Теория проектирования является научной основой для создания надежных, гибких и точных баз данных. К. Дж. Дейт подчеркивает, что без понимания теории практика проектирования превращается в гадание на кофейной гуще. Основным инструментом этой теории является нормализация, однако она охватывает гораздо более широкий круг вопросов, включая зависимости соединений (JD), многозначные зависимости (MVD) и ортогональность.

Ключевым примером в обучении служит база данных «Поставщики и детали» (Suppliers-and-Parts). Она состоит из трех переменных отношений (relvars): S (поставщики), P (детали) и SP (поставки). Поставщики характеризуются уникальным номером (SNO), именем (SNAME), статусом (STATUS) и городом (CITY). Детали имеют номер (PNO), название (PNAME), цвет (COLOR), вес (WEIGHT) и город хранения (CITY). Поставки связывают SNO, PNO и количество (QTY).

Логические основы: отношения и переменные отношений

В теории реляционных баз данных крайне важно различать значения отношений (relation values) и переменные отношений (relation variables или relvars). Значение отношения — это неизменяемое множество кортежей в конкретный момент времени. Relvar — это контейнер, значением которого может быть любое отношение, соответствующее заданному заголовку (heading) и законам целостности.

Заголовок отношения — это зафиксированное множество пар «имя атрибута / имя типа». Тело отношения — это множество кортежей, соответствующих заголовку. Степень (degree) — это количество атрибутов, а кардинальность (cardinality) — количество кортежей. На логическом уровне база данных общается с пользователем через предикаты и пропозиции. Предикат — это утверждение с параметрами (например, «Поставщик SNO находится в городе CITY»), а кортеж в переменной отношения представляет собой истинную пропозицию (конкретное утверждение, например: «Поставщик S1 находится в Лондоне»).

Согласно допущению о замкнутости мира (Closed World Assumption, CWA), переменная отношения содержит все те и только те кортежи, которые соответствуют истинным пропозициям в данный момент времени. Если кортеж отсутствует в базе, соответствующее утверждение считается ложным.

Функциональные зависимости (FD) и ключи

Функциональная зависимость $X ightarrow Y$ означает, что для любых двух кортежей в отношении, если они совпадают в атрибутах $X$ , они обязаны совпадать в атрибутах $Y$ .

Важным подвидом ограничений являются ключи. Кандидатный ключ (candidate key) — это подмножество атрибутов заголовка, обладающее свойствами:

Универсальность (Uniqueness): нет двух кортежей с одинаковым значением ключа.
Неприводимость (Irreducibility): ни одно собственное подмножество ключа не обладает свойством уникальности.

Понятие суперключа (superkey) отличается от ключа тем, что суперключ уникален, но может быть приводимым (содержать избыточные атрибуты). К. Дж. Дейт отмечает, что хотя традиционно выделяют первичный ключ (primary key) и альтернативные ключи, с теоретической точки зрения все кандидатные ключи равноправны.

Иерархия нормальных форм: от 1NF до BCNF

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

Первая нормальная форма (1NF): Отношение находится в 1NF по определению. Это означает, что в каждой позиции атрибута находится ровно одно значение соответствующего типа. Дейт опровергает мифы о том, что атрибуты обязаны быть «атомарными»; значениями могут быть даже другие отношения (Relation-Valued Attributes, RVA).

Вторая нормальная форма (2NF) и Третья нормальная форма (3NF): Эти формы борются с частичными и транзитивными зависимостями неключевых атрибутов от ключей. Однако они считаются промежуточными и представляют скорее исторический интерес.

Нормальная форма Бойса-Кодда (BCNF): Relvar находится в BCNF тогда и только тогда, когда для каждой его нетривиальной функциональной зависимости $X ightarrow Y$ , детерминант $X$ является суперключом. Это «окончательная» нормальная форма в контексте функциональных зависимостей. Нарушение BCNF приводит к избыточности и аномалиям: сложностям при вставке фактов, потере информации при удалении и необходимости обновлять данные во многих местах.

Декомпозиция в BCNF основывается на теореме Хита (Heath's Theorem). Если в отношении $R(X, Y, Z)$ выполняется $X ightarrow Y$ , то $R$ равно соединению своих проекций на $X, Y$ и $X, Z$ . Такая декомпозиция называется неискажающей (nonloss).

Сохранение зависимостей и аксиоматика FD

При декомпозиции отношения на несколько проекций возникает проблема сохранения зависимостей. Если зависимость $X ightarrow Y$ «разрывается» между разными переменными отношений, ее становится трудно контролировать программно. Дейт вводит алгоритм проверки сохранения зависимостей и обсуждает случаи, когда достижение BCNF и сохранение всех FD вступают в конфликт. В таких ситуациях приоритет обычно отдается нормализации до BCNF.

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

Рефлексивность: если $Y ext{ подмножество } X$ , то $X ightarrow Y$ .
Дополнение: если $X ightarrow Y$ , то $XZ ightarrow YZ$ .
Транзитивность: если $X ightarrow Y$ и $Y ightarrow Z$ , то $X ightarrow Z$ .
Замыкание множества зависимостей $F^+$ включает все зависимости, логически вытекающие из исходных.

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

Существуют ситуации, когда отношение нельзя разложить на две проекции без потери данных, но можно на три и более. Это описывается через зависимости соединения (Join Dependencies). Зависимость соединения $ext{R*} {X_1, X_2, ext{…}, X_n}$ гласит, что значение relvar всегда равно соединению своих проекций на указанные подмножества атрибутов.

Пятая нормальная форма (5NF) (также называемая проекционно-соединительной нормальной формой, PJ/NF): Relvar находится в 5NF тогда и только тогда, когда каждая его зависимость соединения подразумевается его ключами. Это означает, что вся избыточность, которую можно устранить путем проекций, устранена. Несмотря на то что 5NF кажется экзотичной, она важна для структур с циклическими правилами бизнеса (например, «если поставщик S поставляет деталь P, а деталь P используется в проекте J, и поставщик S работает с проектом J, то этот поставщик обязан поставлять эту деталь для этого проекта»).

Четвертая нормальная форма (4NF) и многозначные зависимости (MVD)

Многозначная зависимость $X ightarrow ightarrow Y$ — это частный случай зависимости соединения, имеющий ровно два компонента. Она возникает, когда один атрибут определяет независимые наборы значений для других атрибутов (например, у курса есть список преподавателей и список учебников, которые никак не связаны между собой). Декомпозиция таких отношений ведет к 4NF. Любое отношение в 5NF автоматически находится в 4NF, а то, в свою очередь, в BCNF.

Принцип ортогонального проектирования

Ортогональность — это концепция, дополняющая нормализацию. Если нормализация устраняет избыточность внутри одного отношения, то ортогональность запрещает избыточность между отношениями. Принцип гласит: не допускайте ситуации, когда один и тот же факт (пропозиция) может быть представлен в разных переменных отношений одинаковыми кортежами.

Пример нарушения: разделение таблицы деталей на «легкие» и «тяжелые» с перекрывающимся условием по весу. Если деталь весом 17 кг удовлетворяет обоим предикатам, она обязана присутствовать в обеих таблицах, что создает избыточность. Ортогональность требует, чтобы смыслы (предикаты) отношений не пересекались.

Иерархия нормальных форм и финальные цели

Помимо 1NF-5NF и BCNF, существуют дополнительные формы:

Шестая нормальная форма (6NF): Отношение находится в 6NF, если оно не поддерживает никаких нетривиальных JD (даже тех, что вытекают из ключей). Это предел декомпозиции, часто применяемый в темпоральных базах данных.
Доменно-ключевая нормальная форма (DK/NF): Гипотетический идеал, в котором все ограничения базы данных следуют из доменных ограничений и ограничений ключей.
Redundancy-Free Normal Form (RFNF): Форма, которая гарантирует полное отсутствие избыточности кортежей.

Денормализация и производительность

Денормализация — это процесс намеренного снижения уровня нормализации (увеличения избыточности) во имя производительности. Дейт критикует эту практику на логическом уровне, утверждая, что:

Она усложняет логику обновлений и вводит риск нарушения целостности.
Она часто замедляет запросы, не предусмотренные «оптимизацией».
Она смешивает физический уровень хранения с логическим уровнем представления. Правильный подход — нормализовать логическую схему и использовать средства СУБД (индексы, материализованные представления/снэпшоты) в качестве инструментов физической оптимизации.