Еще для многозначных зависимостей существует аналог теоремы Хита о декомпозиции без по-

терь:

Теорема (Фейгин или Фейджин; Fagin). Пусть задана переменная отношения R с заголовком HR и A; B; C — попарно непересекающиеся множества его атрибутов. Тогда критерием декомпозиции

Определение 12. Многозначная зависимость A B переменной отношения R с заголовком HR называется тривиальной, если B Ď A или A Y B HR.

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

7.4. Нормализация

Понятие нормализации и её причины

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

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

•аномалии вставки — добавление лишней информации или возникновение противоречащих значений в некоторых атрибутах при вставке нового кортежа.

•аномалии удаления — удаление лишней информации при удалении кортежа.

•аномалии модификации — появление кортежей с противоречащими значениями в некоторых атрибутах при изменении значений атрибутов одного кортежа.

Первая, вторая и третья нормальные формы

Рис. 2. Иерархия нормальных форм

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

42

Определение 13. Переменная отношения находится в первой нормальной форме (1НФ) тогда и только тогда, когда в любом допустимом значении этой переменной отношения каждый её кортеж содержит только одно значение1 для каждого из атрибутов.

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

Определение 14. Переменная отношения находится во второй нормальной форме (2НФ) тогда и только тогда, когда она находится в 1НФ и каждый неключевой2 атрибут неприводимо зависит от её первичного ключа.

В общем случае, когда отношение имеет несколько потенциальных ключей 2НФ определяется так:

Определение 14’. Переменная отношения находится во второй нормальной форме (2НФ) тогда и только тогда, когда она находится в 1НФ и каждый атрибут, отличный от атрибута первичного ключа, неприводимо зависит от каждого из потенциальных ключей.

Вторая нормальная форма применяется к отношениям с составными ключами. Дело в том, что отношение с простым первичным ключом всегда находится, по крайней мере, в форме 2НФ. Отношение, которое не находится в форме 2НФ, может быть подвержено аномалиям обновления.

Переход от 1НФ к 2НФ состоит в создании проекций по теореме Хита, которые позволяют исключить приводимые функциональные зависимости. А именно: пусть дана переменная отношения R с заголовком HR tA Y B Y C Y Du, где A; B; C; D — попарно непересекающиеся множества атрибутов, причем пусть A Y B является первичным ключом и существует функциональная зависимость A Ñ D. Тогда нормализация заключается в замене этой переменной отношения R на две переменные отношения-проекции R1 и R2:

R1 AYDpRq с первичным ключом A,

R2 AYBYCpRq с первичным ключом A Y B и внешним ключом A, ссылающимся на переменную отношения R1.

Переменная R всегда может быть восстановлена посредством соединения R1 и R2 по внешнему ключу

исоответствующему ему первичному ключу этих переменных отношения.

Каномалиям обновления могут еще привести транзитивные зависимости. Третья нормальная форма требует избавляться от них:

Определение 15. Переменная отношения находится в третьей нормальной форме (3НФ) тогда и только тогда, когда она находится во второй нормальной форме и ни один неключевой атрибут не является транзитивно зависимым от её первичного ключа.

В общем случае, когда отношение имеет несколько потенциальных ключей 2НФ определяется так:

Определение 15’. Переменная отношения находится в третьей нормальной форме (3НФ) тогда и только тогда, когда она находится во второй нормальной форме и ни один атрибут, отличный от атрибутов первичного ключа, не является транзитивно зависимым ни от одного потенциального ключа.

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

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

43

Переход от 2НФ к 3НФ состоит в создании проекций для устранения транзитивных связей. А именно: пусть задана переменная отношения R с заголовком HR tA Y B Y Cu, где A; B; C — попарно непересекающиеся множества атрибутов, причем пусть A является первичным ключом и существует функциональная зависимость B Ñ C. Тогда нормализация заключается в замене этой переменной отношения R на две переменные отношения-проекции R1 и R2:

R1 BYCpRq с первичным ключом B,

R2 AYBpRq с первичным ключом A и внешним ключом B, ссылающимся на переменную отношения R1.

Переменная R всегда может быть восстановлена посредством соединения R1 и R2 по внешнему ключу и соответствующему ему первичному ключу этих переменных отношения.

Следует подчеркнуть, что уровень нормализации переменной отношения определяется семантикой, а не конкретным значением этой переменной в определенный момент времени. Иначе говоря, по конкретному значению некоторой перемен-ной отношения невозможно определить, находится ли она, например, в ЗНФ. Для этого необходимо также знать, какие функциональные зависимости определены в рассматриваемой переменной отношения. Следует также отметить, что даже зная о зависимостях в некоторой переменной отношения, нельзя на основании конкретного ее значения доказать, что она находится в ЗНФ. Самое лучшее, чего можно достичь в подобном случае, — это лишь продемонстрировать, что данное конкретное значение не нарушает никаких зависимостей, и, если это так, высказать предположение о том, что рассматриваемое значение переменной отношения не противоречит гипотезе о ее принадлежности к ЗНФ. Однако сам этот факт не гарантирует, что предложенная гипотеза верна.

Нормальная форма Бойса–Кодда

Теперь будет рассматриваться общий случай — когда переменная отношения может иметь больше одного потенциального ключа.

Дело в том, что первоначальное определение, данное Коддом для ЗНФ, не во всех случаях оказывается удовлетворительным. В частности, оно неадекватно при выполнении следующих условий переменной отношения:

1)переменная отношения имеет два или больше потенциальных ключа, таких, что

2)эти потенциальные ключи являются составными

3)и два или больше потенциальных ключей перекрываются (т. е. имеют по крайней мере один общий атрибут).

Поэтому впоследствии исходное определение ЗНФ было заменено более строгим определением Бойса–Кодда. А поскольку это новое определение фактически задает нормальную форму, которая во всех отношениях сильнее по сравнению со старой ЗНФ, для нее было установлено собственное название — нормальная форма Бойса–Кодда (или НФБК).

Замечание. Комбинация условий 1–3 на практике встречается не часто. Для любой переменной отношения, в которой не выполняются все эти три условия, ЗНФ и НФБК полностью эквивалентны.

Определение 16. Переменная отношения находится в нормальной форме Бойса–Кодда (НФБК; Boyce–Codd normal form, BCNF) тогда и только тогда, когда каждая её нетривиальная и неприводимая слева функциональная зависимость имеет в качестве своего детерминанта некоторый потенциальный ключ.

Иначе говоря, на диаграмме функциональных зависимостей все стрелки должны начинаться только с элементов, представляющих потенциальные ключи.

Приведем алгоритм приведения переменной отношения R к нормальной форме Бойса–Кодда. Под D будем обозначать множество нормализованных отношений, которые будут получаться в результате декомпозиции:

44

1.По началу D состоит лишь из переменной отношения R.

2.Пусть переменная отношения T P D с заголовком HT не находится в НФБК. Если такого отношения нет, то нормализация окончена.

2.1) Пусть X Ñ A — функциональная зависимость, имеющая место в T, где X не является потенциальным ключом отношения T и A Ę X (т. о. зависимость не удовлетворяет условиям НФБК).

2.2) Заменяем в D отношение T на два отношения T1 AYX pTq и T2 HT zApTq1. 2.3) Повторяем п. 2.

Алгоритм завершится, т. к. всегда найдется атрибут C отношения T из п. 2 такой, что C R X Y A, иначе бы в X был ключ отношения T. А значит, |HT1 | ă |HT | и |HT2 | ă |HT |, т.е. количество атрибутов в заголовках всегда уменьшается.

Но не всегда нужно стремиться от 3НФ к нормальной форме Бойса–Кодда, т. к. могут образоваться зависимые проекции. Подробнее об этом можно почитать в [6].

Четвертая нормальная форма

Теорема Фейджина обеспечивает основу для декомпозиции отношений, удаляющей «аномальные» многозначные зависимости, с приведением отношений в четвертую нормальную форму.

Определение 17. Переменная отношения R с заголовком HR находится в четвертой нормальной форме (4НФ, 4NF) тогда и только тогда, когда в случае существования таких подмножеств A Ď HR и B Ď HR атрибутов, для которых выполняется нетривиальная многозначная зависимость A B, все атрибуты переменной отношения R также функционально зависят от множества атрибутов A.

Это можно переформулировать так: переменная отношения R находится в 4НФ тогда и только тогда, когда она находится в НФБК и все многозначные зависимости в переменной отношения R фактически представляют собой функциональные зависимости от ее ключей.

Зависимости соединения и пятая нормальная форма

Приведение отношения к 4НФ предполагает его декомпозицию без потерь на две проекции (как и в случае 2НФ, 3НФ и БКНФ). Однако бывают (хотя и нечасто) случаи, когда декомпозиция без потерь на две проекции невозможна, но можно произвести декомпозицию без потерь на большее число проекций.

Определение 18. Отношение называется n-декомпозируемым, если оно может быть декомпозировано без потерь на n проекций.

Пусть задана переменная отношения R с заголовком HR и Ai Ď HR (i 1; n) — произвольная подмножества его атрибутов.

Определение 19. Переменная отношения R удовлетворяет зависимости проекции-соединения

(без потерь) (Project-Join Dependency, PJD) tA1; : : : ; Anu тогда и только тогда, когда любое до-

пустимое значение переменной отношения R эквивалентно естественному соединению её проекций по A1; : : : ; An, т. е. R A1 pRq ' ' An pRq.

Определение 20. Зависимость проекции-соединения tA1; : : : ; Anu в переменной отношения R с заголовком HR называется тривиальной тогда и только тогда, когда Di P r1 : ns: Ai HR.

Определение 21. Зависимость проекции-соединения tA1; : : : ; Anu в переменной отношения R с за-

головком HR определяется потенциальным ключом (ключами) отношения R тогда и только тогда,

когда @i P r1 : ns множество атрибутов Ai является суперключом.

1 Такое разбиение является декомпозицией без потерь, т. к. удовлетворяет теореме Хита: HT1 X HT2 X

и X Ñ HT1 zHT2 A.

45