Пусть А, В и С являются произвольными подмножествами множества атрибутов переменной-отношения R. Тогда подмножество В многозначно зависит от подмножества А, что символически выражается записью

(читается как А многозначно определяет В или А двойная стрелка В ), тогда и только тогда, когда множество значений В, соответствуюшее заданной паре (значение А, значение С) переменной-отношения R, зависит от А, но не зависит от С.

Нетрудно показать (это обсуждается в работе Фейгина [12.13]), что для данной переменной-отношения R{A, В, С} многозначная зависимость А -> В выполняется тогда и только тогда, когда также выполняется многозначная зависимость А - С. Таким образом, многозначные зависимости всегда образуют связанные пары, поэтому обычно их представляют вместе в символическом виде.

А В I С

Для рассматриваемого примера такая запись будет иметь следуюший вид. COURSE - TEACHER TEXT

Ранее уже утверждалось, что многозначные зависимости являются обобшениями функциональных зависимостей в том смысле, что всякая функциональная зависимость является многозначной. Точнее говоря, функциональная зависимость - это многозначная зависимость, в которой множество зависимых значений, соответствуюшее заданному значению детерминанта, всегда является одноэлементным множеством. Таким образом, если А В, то А - В.

Теперь, возврашаясь к исходной задаче с переменной-отношением СТХ, можно отметить следуюшее: описанная ранее проблема с переменными-отношениями этого типа возникает из-за того, что они содержат многозначные зависимости, которые не являются функциональными. (Следует отметить совсем неочевидный факт, что именно наличие таких МЗЗ требует вставки двух кортежей, когда необходимо добавить сведения о новом преподавателе физики. Данные два кортежа необходимы для поддержания ограничения целостности, представленного этой МЗЗ.) Проекции СТ и СХ не содержат многозначных зависимостей, а потому они действительно представляют собой некоторое усовершенствование исходной структуры. Поэтому было бы желательно заменить исходную переменную-отношение СТХ двумя рассматриваемыми проекциями. Это действие будет правомочным в соответствии с теоремой Фейгина [12.13], которая приведена ниже.

Теорема Фейгина. Пусть А, В и С являются множествами атрибутов переменной-отношения R{A, В, С}. Переменная-отношение R будет равна соединению ее проекций {А, В} и {А, С} тогда и только тогда, когда для переменной-отношения R выполняется многозначная зависимость А - В С.

(Обратите внимание, что эта теорема является более строгой версией теоремы Хита, описанной в главе 11.) Теперь, следуя работе Фейгина [12.13], можно дать определение четвертой нормальной формы. (Эта нормальная форма получила такое название потому, что в момент ее появления НФБК все еше считалась третьей нормальной формой.)

Переменная-отношение R находится в четвертой нормальной форме (4НФ) тогда и только тогда, когда в случае существования таких подмножеств А и В атрибутов этой переменной-отношения R, для которых выполняется нетривиальная многозначная зависимость А -> В, все атрибуты переменной-отношения R также функционально зависят от атрибута А.

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

Переменная-отношение СТХ не находится в 4НФ, поскольку содержит многозначную зависимость, которая не является функциональной, не говоря уже о том, что последняя должна быть еще и функциональной зависимостью от ключа. Однако обе ее проекции, СТ и СХ, находятся в 4НФ. Следовательно, 4НФ обеспечивает лучшую структуру данных по сравнению с НФБК, поскольку позволяет исключить некоторые нежелательные зависимости. Кроме того, в [12.13] Фейгин показал, что 4НФ всегда является достижимой, т.е. любая переменная-отношение может быть подвергнута декомпозиции без потерь в эквивалентный набор переменных-отношений в 4НФ. Однако, как показано в разделе 11.5 на примере переменной-отношения SJT, такая декомпозиция (или даже декомпозиция до НФБК) не всегда оказывается полезной и нужной.

Замечание, Следует отметить, что хотя идеи Риссанена, изложенные в посвященной независимым проекциям работе [11.6], сформулированы с использованием функциональных зависимостей, они также справедливы в отношении многозначных зависимостей. Напомним, что в соответствии с этими идеями переменную-отношение R{A, В, С}, удовлетворяющую функциональным зависимостям А -> В и В -> С, необходимо разбивать на проекции {А, В} и {В, С}, а не на проекции {А, В} и {А, С}. Это утверждение также будет верно, если вместо функциональных зависимостей использовать многозначные зависимости А -> В и В -¥¥ С.

В заключение вернемся, как было обещано, к вопросу об исключении атрибутов, принимающих в качестве значений отношения, или АО (атрибутов-отношений) для краткости. В частности, рассмотрим процедуру такого исключения, описанную в ответе к упр. 11.3 из предыдущей главы. Суть в том, что на практике для достижения 4НФ достаточно учитывать следующее: если мы имеем дело с переменной-отношением с двумя или более независимыми АО, то прежде всего следует разделить эти АО. Данное правило имеет не только интуитивно понятный смысл. Это именно то, что было сделано в ответе к упр. 11.3! Например, в случае переменной-отношения НСТХ прежде всего следует заменить исходную переменную-отношение двумя ее проекциями HCT{COURSE, TEACHERS} и HCX{COURSE, TEXTS}, где перемен-

МЗЗ А -> В называется тривиальной, если либо А является супермножеством В, либо объединение Аи В образует весь заголовок отношения.

ные-отношения TEACHERS и TEXTS все еше сохраняют АО. Далее эти АО можно будет исключить из двух полученных проекций (с приведением их к НФБК) обычным способом, и тогда проблема , свойственная находящейся в НФБК переменной-отношению СТХ, просто никогда не возникнет. Как видите, понятия многозначных зависимостей и 4НФ предоставляют формальное обоснование тех правил, которые в противном случае остались бы чисто эмпирическими.

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

До сих пор в настояшей главе и на протяжении всей предыдушей главы предполагалось, что единственной необходимой или допустимой операцией в процессе нормализации является замена переменной-отношения по правилам декомпозиции без потерь только двумя ее проекциями. Такое допушение нас вполне устраивало вплоть до достижения 4НФ. Однако, хотя это может показаться удивительным, сушествуют переменные-отношения, для которых нельзя выполнить декомпозицию без потерь на две проекции, но которые можно подвергнуть декомпозиции без потерь на три или более проекций. Подобные переменные-отношения обозначим не очень удачным, но достаточно удобным термином п-декомпозируемая переменная-отношение (для некоторого п > 2). Это значит, что для данной переменной-отношения возможна декомпозиция без потерь на п проекций, но не на m проекций для любого m < п. Таким образом, переменную-отношение, для которой можно выполнить декомпозицию на две проекции, следовало бы называть 2-декомпозируемой.

Замечание. Впервые возможность п-декомпозируемости для п > 2 была упомянута в работе Ахо (Aho), Бери (Beeri) и Ульмана (Ullman) [12.1], а частный случай для п = 3 был описан Николасом (Nicolas) [12.25].

В качестве примера рассмотрим переменную-отношение SPJ из базы данных поставшиков, деталей и проектов, представленную на рис. 12.4 (в целях упрошения изложения атрибут QTY исключен). Обратите внимание, что эта переменная-отношение состоит только из ключевых атрибутов, не содержит нетривиальных функциональных и многозначных зависимостей и потому находится в 4НФ. Заметим также, что на этом рисунке показаны следующие компоненты.

1. Три бинарные проекции, SP, PJ и JS, переменной-отношения SPJ.

2. Результат соединения проекций SP и PJ по атрибуту Р#.

3. Соединение этого результата с проекцией JS по комбинации атрибутов (J#, S#).

Обратите внимание, что в результате первого соединения получается копия исходной переменной-отношения SPJ с одним дополнительным (излишним) кортежем, а в результате второго соединения этот лишний кортеж исключается. Иначе говоря, исходная переменная-отношение SPJ является 3-декомпозируемой.

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