Понятие третьей нормальной формы схемы отношения тесно связано с понятием транзитивной зависимости, которая имеет вид цепочки функциональных зависимостей с определенными ограничениями.
Пусть задана схема отношения R=(U, F), A, CÍU. Функциональная зависимость А—>С называется транзитивной, если существует подмножество атрибутов ВÌU, такое, что
А⊉В, В⊉С, А—>В, В↛А и В¾>С.
Отметим, что наличие или отсутствие зависимости С—>В значения не имеет. Если такой зависимости нет, то транзитивная зависимость называется строгой транзитивной зависимостью. Например, R=({А1, А2, А3, А4, А5}, {А1—>А2; А2—>АЗ; А1¾>А4; А4—>А5; А5—>А1}). Здесь зависимость А1—>АЗ является транзитивной, так как имеем цепочку
А1—>А2—>АЗ и А2↛Al.
В то же время зависимость Al—>А5 не является транзитивной, хотя и есть цепочка А1¾>А4—>А5, но здесь (А4—>Al)ÎF+, что противоречит определению транзитивной зависимости.
Присутствие в схеме транзитивной зависимости А—>В—>С приводит к избыточности данных о связи атрибутов В и С и, следовательно, избыточности значений атрибутов С, что может привести к нарушению целостности базы данных при изменении значений атрибутов из множеств С и В. Избыточность значений С возрастает, если дополнительно В↚С. Замена схемы отношения, в которой есть транзитивная зависимость, декомпозицией, которая не содержит зависимостей такого типа, избавляет базу данных от указанных недостатков. Такая декомпозиция при выполнении определенных условий называется третьей нормальной формой отношения.
Третья нормальная форма (ТНФ) схемы отношения это либо данная схема, если она находится во второй нормальной форме и не содержит транзитивной зависимости непервичных атрибутов от ключей, либо декомпозиция исходной схемы, каждая подсхема которой удовлетворяет этим же требованиям, а сама декомпозиция – свойством соединения без потерь.
Третья нормальная форма существует для любой схемы отношения, причем часто не единственная.
Возможность неоднозначного преобразования к ТНФ, а также желание сохранить в подсхемах более “близкие” взаимосвязи между атрибутами приводит к понятию оптимальной ТНФ, содержащей наименьшее число подсхем, и кроме того, в случае зависимости А—>В—>С подсхемы не должны включать одновременно “несмежные” компоненты А и С.
Получить ТНФ (не всегда оптимальную) можно с помощью модификации алгоритма Хита, применявшегося для получения второй нормальной формы.
Суть алгоритма заключается в следующем. Пусть задана схема отношения R=(U, F), А, В, CÌU, А¾>В¾>С – транзитивная зависимость (С состоит из непервичных атрибутов), тогда переходим к декомпозиции r=(R1=(U1, F1), R2=(U2, F2)), где U1=U\С, U2=BÈC, F1 и F2 – проекции F соответственно на U1 и U2. Затем, если необходимо, производится декомпозиция RI и R2 и так далее до тех пор, пока все подсхемы не окажутся в ТНФ.
Заметим, что задача проверки, находится ли схема отношения в ТНФ, относится к NP-трудным, это связано с задачей выделения всех непервичных атрибутов отношения. В принципе можно выполнять декомпозицию зависимости А—>В—>С, не проверяя находятся первичные атрибуты в С или нет, но это может привести к избытку подсхем, что снижает “качество” декомпозиции.
Пример.
Для схемы R=({A1, A2, ..., А7}, {А1,А2—>АЗ; АЗ¾>А4; А4—>А5; А4¾>А6; А5—>А7; A6—>А7}) требуется получить ТНФ. Первичные атрибуты {А1, А2}, непервичные – {A3, А4, А5, А6, А7}. Транзитивная зависимость: А4—>А5—>А7.
На первом этапе получаем: R1=({A1, A2, A3, А4, А5, А6},
{А1,А2—>A3; АЗ¾>А4; А4—>А5; А4—>А6});
R2=({A5, A6, A7}, {A5¾>A7, A6¾>A7}). R2 находится в ТНФ.
В R1 нежелательная транзитивная зависимость: АЗ—>А4—>А5. Строим декомпозицию, получаем:
R11=({Al, А2, АЗ, А4}, {А1,А2—>A3; АЗ—>А4}),
R12=({A4, A5, A6}, {A4—>A5; А4—>А6}). R12 находится в ТНФ.
В R11 нежелательная транзитивная зависимость: Al,А2—>A3—>А4.
Следует отметить, что простота описанного метода только кажущаяся, основная сложность заключается в выявлении транзитивных зависимостей, которые не обязательно “видны” по системе образующих структуры функциональных зависимостей, например, в случае
транзитивной зависимостью является цепочка А1,А2¾>АЗ,А4¾>А5, которая кажется очевидной только из-за малого количества атрибутов. Во многом процесс выявления транзитивных зависимостей облегчается графовым представлением схем отношений. Ниже приводятся алгоритмы приведения схемы отношения к ТНФ, не требующие выделения транзитивных зависимостей в явном виде, но часто дающие декомпозиции, далекие от оптимальных.
Алгоритм Делобеля-Кейси приведения схемы отношения к ТНФ.
Пусть задана схема отношений R=(U, F).
1) Перейти от F к элементарному функциональному базису F*, то есть к минимальному покрытию, состоящему только из полных зависимостей, причем в правой части каждой зависимости должен находиться только один атрибут.
2) По каждой зависимости (Xi ¾>Yi)ÎF* образовать подсхему Ri= (Ui=XiÈYi), если при этом для некоторых i и j, i¹j, окажется, что UjÍUi, то Rj удаляется.
3) Если хотя бы одна из полученных подсхем содержит ключ исходного отношения (для этого достаточно проверить, выполняется ли хотя бы для одного Ui соотношение Ui+=U), то совокупность полученных Ri является ТНФ отношения R, иначе добавить к полученной декомпозиции еще одну схему, состоящую из произвольного ключа отношения R.
Заметим, что полученная декомпозиция сохраняет также зависимости исходной схемы, алгоритм имеет полиномиальную оценку трудоемкости, поскольку здесь не выделяется множество первичных атрибутов и даже не проверяется, находится ли исходное отношение в ТНФ, но такие упрощения естественно приводят к избытку подсхем в декомпозиции.
Пример.
Для схемы R=({A1, A2, А3, А4, А5}, {А1,А2¾>A3; АЗ¾>А4; АЗ,А4¾>А5}) получить ТНФ.
Переходим к элементарному функциональному базису. В зависимости АЗ,А4—>А5 атрибут А4 избыточный, получим F*={А1,А2¾>АЗ; АЗ¾>А4; АЗ¾>А5). Строим декомпозицию
r=({А1, А2, АЗ}, {АЗ, А4}, {АЗ, А5}).
Поскольку {А1, А2, АЗ}+={А1, А2, А3, А4, A5}=U, значит U1 содержит ключ исходного отношения и r является ТНФ отношения R.
Здесь подсхемы {АЗ, А4} и {АЗ, А5} можно объединить в одну {АЗ, А4, А5}, но в общем случае такие объединения требуют дополнительной проверки, так как подсхема, полученная в результате объединения, может не быть в ТНФ.
Можно модифицировать приведенный алгоритм следующим образом.
1) Шаг 1 предыдущего алгоритма.
2) Найти множество всех первичных атрибутов исходного отношения Up и непервичных U\Up.
3) Просмотреть все зависимости Х¾>Y из F*, если Х не является ключом и Y – непервичный атрибут (если таких зависимостей в F нет, то R в ТНФ), строим декомпозицию Ul=XÈY, U2=U\Y, то eсть такие зависимости выделяются в отдельные отношения.
В отличие от предыдущего алгоритма, здесь получается вообще говоря меньше подсхем, но увеличивается трудоемкость за счет нахождения всех первичных атрибутов и декомпозиция не обязательно сохраняет зависимости.
4.3.3. Усиленная третья нормальная форма схем отношений(нормальная форма Бойса-Кодда).
Если третья нормальная форма схем отношений не содержит неполных и транзитивных зависимостей любых атрибутов от ключей, то она называется третьей усиленной нормальной формой (УТНФ).
Приведенное определение УТНФ эквивалентно следующему определению, в котором не используются такие понятия, как ключ, первичные и непервичные атрибуты, полная и транзитивная зависимость.
Усиленной третьей нормальной формой схемы отношения R=(U, F) называется либо данная схема, если она нормализована и для любого набора атрибутов AÌU верно, что если какой-либо атрибут xÎU\A зависит функционально от А, то и все атрибуты отношения функционально зависят от А; либо декомпозиция схемы R, каждая подсхема которой удовлетворяет этим требованиям, обладающая свойством соединения без потерь.
Таким образом, R находится в УТНФ тогда и только тогда, когда для любой зависимости (X—>Y) и X⊉Y выполняется Х+=U. Очевидно, что если отношение находится в УТНФ, то оно находится и в ТНФ, обратное, вообще говоря, не верно. УТНФ называют также нормальной формой Бойса-Кодда. Любая схема отношения может быть приведена к УТНФ. Следующий алгоритм получения УТНФ основывается на той же теореме Хита.
Пусть задана схема отношения R=(U, F). Требуется получить УТНФ схемы R.
1) Перейти от F к элементарному функциональному базису F*, то есть к минимальному покрытию, состоящему только из полных зависимостей, причем в правой части каждой зависимости должен находиться только один атрибут.
2) Далее декомпозицию r для R строим итеративным методом, при этом r всегда будет обладать свойством соединения без потерь. Первоначально r состоит только из R. Если S – схема из r и в S есть зависимость X—>Y, ХÊY и Х не содержит ключа S, то заменяем S декомпозицией S1=(U1, F1), S2=(U2, F2), где U1=XÈY, U2=U\Y (здесь полагается, что S=(U, F)). Так продолжается до тех пор, пока все подсхемы r не окажутся в УТНФ.
Заметим, что пункт 1) выполнять не обязательно, но тогда сильно возрастет трудоемкость проектирования F на подсхемы.
Пример.
Для схемы R=(U, F)=({A1, A2, ..., А6}, {А1—>А2; А2,А4¾>А1; А2¾>A3; АЗ¾>А4; АЗ,А4¾>А5; А5¾>А6}) требуется получить УТНФ. Перейдя к элементарному функциональному базису, получим F={А1—>А2; А2¾>А1;А2¾>A3; АЗ¾>А4; АЗ¾>А5; А5¾>А6}.
Проверяем зависимости:
Для зависимости А1—>А2 выполняется {Al}+=U, следовательно, зависимость А1—>А2 удовлетворяет УТНФ;
Для зависимостей А2¾>А1 и А2—>A3 выполняется {A2}+=U, следовательно, эти зависимости удовлетворяют УТНФ;
Для зависимостей A3¾>А4 выполняется {A3}+¹U. Следовательно, зависимость A3¾>А4 не удовлетворяет УТНФ. Выделяем зависимость A3—>А4 в отдельную схему, получаем:
R1 находится в УТНФ. Проверяем зависимость A3—>А5; для нее выполняется {А3}+¹U2. Следовательно, она не удовлетворяет УТНФ. Выделяем зависимость A3—>А5 в отдельную схему. Получаем:
R21=({A3, A5), {A3—>А5}),
R22=({A1, A2, A3, A6}, {A1—>A2; А2¾>А1; А2¾>А3; A3¾>А6}). R21 находится в УТНФ. Рассматриваем зависимость A3¾>А6; для нее выполняется {АЗ}+¹U22. Следовательно, она не удовлетворяет УТНФ. Выделяем зависимость A3—>А6 в отдельную схему:
Получаем: R221=({A3, A6}, {A3—>A6}),
R222=({A1, A2, A3), {A1¾>А2; А2¾>А1; А2¾>АЗ}). R221 и R222 находятся в УТНФ.
УТНФ r=(R1, R21, R221, R222) для схемы R.
Дерево декомпозиции имеет вид:
Однако полученная декомпозиция имеет следующие существенные недостатки.
1) R1 и R21 можно объединить в одну схему, получим R1=({A3, A4, A5}, {A3—>А4; АЗ—>А5}). Заметим, что так делать можно не всегда. Так, если бы была зависимость А4¾>А5, то в R1 получили бы транзитивную зависимость A3¾>А4¾>А5.
2) A3 и А6 нецелесообразно объединять в одну подсхему, поскольку в исходной схеме есть транзитивная зависимость A3—>А5¾>А6, где A3 и А6 не смежны, и поэтому такое объединение приведет к избыточности данных в базе. Лучше вместо {АЗ, А6} использовать подсхему {А5, А6}. Легко видеть, что такая замена не нарушает свойства соединения без потерь, попросту функциональные зависимости проверяются в другом порядке. Таким образом, пришли к декомпозиции:
При больших количествах атрибутов, такого рода улучшения требуют значительных затрат. Целесообразно поступать следующим образам.
а) Найти произвольный ключ К.
б) Построив К+, выписать все К(i) (см. алгоритм построения замыканий).
в) Просматривать К(i) в обратном порядке и выделять в отдельные подсхемы зависимости X—>Y, нарушающие УТНФ и такие, что Х и Y принадлежат К(i) с наибольшими номерами i.
Во многих случаях такой подход исключает включение в подсхемы несмежных транзитивных компонент,
Заметим, что не всегда можно преобразовать схему отношения к УТНФ с сохранением зависимостей.
Например: R=({A1, A2, A3}, {A1,A2¾>A3; АЗ¾>Al}).
Схема R находится в ТНФ, но не в УТНФ, поскольку для зависимости A3—>А1 выполняется {A3}+¹{А1, А2, АЗ}. УТНФ дает декомпозиция: R1=({A1, A3), {A3—>A1}), R2=({A2, A3}), но при этом теряется зависимость А1,А2¾>A3, и, следовательно, построить УТНФ с сохранением этой зависимости невозможно.
