Цели и средства нормализации

Определение:

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

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

Цели

• Исключение некоторых типов избыточности
• Устранение некоторых аномалий обновления
• Разработка проекта базы данных, который является достаточно "качественным" представлением реального мира, интуитивно понятен и может служить хорошей основой для последующего расширения
• Упрощение процедуры применения необходимых ограничений целостности

Следствия

Полная нормализация приводит к замедлению работы базы т.к. увеличивается количество логически независимых переменных отношения ⇒ увеличивается количество отдельно хранимых физических файлов, что в свою очередь приводит к появлению большего количества операций ввода-вывода, что и замедляет работу.

Средства нормализации

Проекция

Определение:

Проекция отношения R на множество атрибутов X: [math]\pi_X(R) =\{r \cap X|r\in R\}[/math] — это отношение удовлетворяющее свойствам: Его заголовок формируется из заголовка отношения R путем удаления всех атрибутов, не указанных в множестве X Тело состоит из всех кортежей [math]{Х_1 r_1 , X_2 r_2, . . . , X_n r_n }[/math], таких что в отношении R присутствует кортеж со значением [math]r_1[/math] атрибута [math]X_1[/math], [math]r_2[/math] атрибута [math]X_2[/math] и т.д.

Соединение

Операция соединения имеет несколько разных вариантов, но чаще всего рассматривается естественное соединение.

Определение:

Соединение отношений [math]P_1[/math] и [math]P_2[/math]: [math]P_1 ⋈ P_2 = \{r_1 ∪ r_2 | r_1 ∈ P_1, r_2 ∈ P_2 ∧ π_Y(r_1) = π_Y(r_2)\}[/math] — отношение с заголовком { X, Y, Z } и телом, состоящим из всех таких кортежей {[math]Х_i х_i[/math], [math]Y_j y_j[/math], . . . , [math]Z_k z_k[/math]}, что любой из этих кортежей присутствует и в отношении [math]P_1[/math], со значением [math]x_i[/math] атрибута [math]Х_i[/math] и значением [math]y_j[/math] атрибута [math]Y_j[/math], и в отношении [math]P_2[/math], со значением [math]y_i[/math] атрибута [math]Y_i[/math] и значением [math]z_k[/math] атрибута [math]Z_k[/math].

• Можно понимать как соединение по совпадающим атрибутам
• Коммутативно
• Ассоциативно

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

Процедура нормализации предусматривает разбиение, или декомпозицию, данной переменной отношения на другие переменные отношения, причем декомпозиция должна быть обратимой, т.е. выполняться без потерь информации, то есть, соединение отношений, полученных при декомпозиции множества, должно давать исходное отношение Декомпозиция отношения R на множества атрибутов A и B: [math]R(A, B) = \pi_A(R) ⋈ \pi_B(R)[/math]

Пример корректной декомпозиции

Проекции на CId Phone и Lecturer Phone	Соединение CId Lecturer и Lecturer Phone

Пример некорректной декомпозиции

Проекции на CId Phone и Lecturer Phone	Соединение CId Phone и Lecturer Phone

Теорема Хита

Теорема Хита утверждает, что если некоторая декомпозиция выполняется в соответствии с определенной ФЗ, то она будет выполнена без потерь.

Теорема (Хит):

Пусть R(XYZ) является отношением, где X, Y и Z — неперескающиеся множества атрибутов. Если R удовлетворяет функциональной зависимости X → Y, то R равно соединению ее проекций по атрибутам X, Y и Y, Z: [math]R=\pi_XY(R)⋈ \pi_XZ(R)[/math]

Доказательство:

[math]\triangleright[/math]

[math]\subset[/math] [math]∀ r ∈ R: π_{XY}(r) ∈ π_{XY}(R), π_{XZ}(r) ∈ π_{XZ}(R) ⇒ r ∈ π_{XY}(R) ⋈ π_{XZ}(R)[/math] [math]\supset[/math] [math]∀ (x, y, z) ∈ π_{XY}(R) ⋈ π_{XZ}(R) ⇒ (x, y) ∈ π_{XY}, (x, z) ∈ π_{XZ}(R)[/math] [math]Из (x, z) ∈ π_{XZ}(R) ⇒ ∃ y': (x, y', z) ∈ R ⇒ (x, y') ∈ π_{XY}(R)[/math] [math]X → Y ⇒ ∃! y : (x, y) ∈ π_{XY}(R) ⇒ y = y' ⇒ (x, y, z) ∈ R[/math]

[math]\triangleleft[/math]

См. также

• Функциональные зависимости: замыкание, эквивалентность и правила вывода
• Нормальные формы: первая и вторая
• Нормальные формы: третья и Бойса-Кодда
• Многозначные зависимости и четвертая нормальная форма
• Зависимости соединения и пятая нормальная форма

Источники информации

• kgeorgiy.info Тема 4. Нормализация баз данных
• Дейт К.: Введение в системы баз данных (Глава 12)