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

Кроме функциональных зависимостей, между атрибутами могут существовать многозначные зависисмости (multi-valued dependencies).

Пусть А1 и А2 - два атрибута отношения R. Между этими атрибутами существует многозначная зависимость (МЗ), обозначаемая А1А2, если значению а1 атрибута А1, соответствует множество значений {а21, a22, …, a2k} атрибута А2. Это множество должно быть устойчивым, т.е. сохраняться при любом вхождении многозначной зависимости в отношение.
Следует заметить также, что многозначная зависимость отражает особенности предметной среды и должна быть устойчива (инвариантна) так же, как и функциональная зависимость.

Говорят, что в отношении R(A, B, C) между атрибутами А и В существует многозначная зависимость АB, если оно может быть представлено в виде эквисоединения своих проекций:

R(A, B, C) = R1(A, B) [A=A] R2(A, C).

Т.к. эквисоединение симметрично относительно В и С, то, следовательно, в R имеет место также многозначная зависимость АC.

Для многозначных зависимостей существует аналогичная аксиоматика, как и для ФЗ [1, 13].

Определение МЗ [13]

Пусть R(X, Y, Z) - схема отношения R,  Х, Y, Z - непересекающиеся подмножества атрибутов R, и пусть Z = AR\ (X, Y).

Отношение R удовлетворяет МЗ XY, если для двух любых кортежей t1 и t2 из Ri, таких, что t1(x) = t2(x) (т.е. кортежи t1 и t2 совпадают по значению х) в Ri существует кортеж t3 такой, что t3(x) = t1(x), а t3(у) = t1(у) и t3(z) = t2(z).

Из симметрии определения относительно t1 и t2 (учитывая, что t1(x) = t2(x)) следует, что в Ri существует также кортеж t4, для которого t4(x) = t1(x), t4(y) = t2(y) и t4(z) = t1(z).

Пример:
 
R(X,Y,Z )
t1xy1z1
t2xy2z2
t3xy1z2
t4xy2z1

Т.е. атрибут X многозначно определяет атрибут Y (XY), если при наличии в отношении кортежей t1 и t2, в нем присутствует кортеж t3, значения элементов которого совпадают с элементами кортежей t1 и t2 по следующей табличной функции:

t3=<t1 t1 t2>.

 Тогда R = R1(X, Y) х° R2( X, Z)
  x, y1 x, z1
  x, y2 x, z2,

где - х° - знак операции эквисоединения по множеству атрибута X.

Как показано в [23], для отношения R (X, Y, Z) многозначная зависимость (XY) выполняется только тогда, когда также выполняется многозначная зависимость (XZ). Таким образом, многозначные зависимости всегда образуют связанные пары. Более того, многозначная зависимость является обобщением функциональной зависимости в том смысле, что всякая функциональная зависимость является многозначной.

Также как и функциональная зависимость, многозначная зависимость может быть тривиальной или нетривиальной. Например, для отношения R(X, Y), состоящего из двух атрибутов, всегда справедливо XY. Такую МЗ принято называть тривиальной. Другими словами, если атрибут Y вляется подмножеством атрибута X или XY = AR, то многозначная зависимость тривиальна. Если ни одно из названных условий не выполняется, то многозначная зависимость не явялется тривиальной.

Определение 4НФ. Отношение R(AR) находится в четвертой нормальной форме, если в структуре МЗ, определенной на множестве атрибутов AR, имеются только тривиальные МЗ зависимости и/или такие нетривиальные МЗ, что левая часть любой из них является ключом R.

Фактически определение 4НФ следует из теоремы Фейджина [23]:

Отношение R (A, B, C) можно спроецировать без потерь в отношения R1 (A, B) и R2 (A, C) в том и только в том случае, когда существует MЗ A B | C.

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

Из определения МЗ непосредственно следует, что если R находится в 4НФ, то оно находится и в 3НФ.

Рассмотрим пример отношения, на множестве атрибутов которого определены нетривиальные МЗ [10].

Пусть дано отношение R (Служащий, Дети, Зарплата, Год). Служащий идентифицируется своей фамилией: пусть фамилия для простоты уникальна. Атрибут Дети определяет имена детей служащего, атрибуты Зарплата, Год - показывают "историю" получаемой зарплаты: величину оклада и год назначения нового оклада. Предполагается, что один и тот же оклад не может быть установлен одному и тому же служащему дважды (это в, частности, может означать, что понижение оклада не допускается). Кроме того, допускается изменение оклада более одного раза в год.

В этом примере присутствуют две нетривиальные многозначные зависимости: СлужащийДети и Служащий{Зарплата, Год}. Атрибут Дети считается независимым в контексте от рассматриваемого примера от истории зарплаты. В то же время значения атрибутов Зарплата и Год взаимосвязаны.

Наличие нетривиальных многозначных зависимостей в схеме одного отношения и независимость их правых частей, как уже отмечалось, приводит к комбинаторике значений правых частей. Так возможным состоянием R может быть состояние Ri, показанное на рис. 29. В данном отношении явно присутствует избыточность представления: сведения о том, что Петров имеет ребенка по имени Вася, повторяются дважды, т. к. оклад Петрова изменялся. По этой же причине идет дублирование информации и для сотрудника Серова. Сведения о каждом изменении оклада Серова повторяются дважды.

СлужащийДетиЗарплата Год
ПетровВася8001999
ПетровВася9001999
СеровМиша10001999
СеровМиша12002000
СеровСвета10001999
СеровСвета12002000

Рис. 29. Исходное состоние отношения

Заметим, что отношение R (рис. 29.) находится в 3НФ, поскольку в отношении отсутствуют нетривиальные функциональные зависимости. Ключом в данном отношении является совокупность атрибутов: {Служащий, Дети, Зарплата, Год}, поскольку для предметной области введено правило, что Служащему возможно повышение Зарплаты несколько раз в Год. В отношении R отсутствуют непервичные атрибуты, следовательно, отсутствуют какие-либо транзитивные зависимости между непервичными атрибутами, однако даже наличие всех этих свойств не устраняет избыточность, имеющуюся в отношении (рис. 29).

Чтобы избавится от избыточности необходимо разложить отношение R (рис. 29) на две проекции R1 и R2, представленные на рис. 30 и 31, то есть привести отношение R к 4НФ. Таким образом, 3НФ не определяет все возможные декомпозиции.

Служащий ЗарплатаГод
Петров8001999
Петров9001999
Серов10001999
Серов12001999
СлужащийДети
ПетровВася
СеровМиша
СеровСвета

Рис. 30. Проекция R1 Рис. 31. Проекция R2

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

Исходное отношение R (рис. 29) восстановимо из проекций R2 и R1 с помощью следующего предложения SQL:

SELECT (*)
FROM R1, R2
WHERE R2 .Служащий = R1 .Служащий;

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

Таким образом, для отношения R в базе данных должно быть зафиксировано следующее правило (если имеют место МЗ вида СлужащийДети и Служащий{Зарплата, Год}):

R (Служащий, Дети, Зарплата, Год) = R [Служащий, Зарплата, Год] [Служащий = Служащий] R [Служащий, Дети]

По существу, многозначную зависимость можно трактовать как функциональную, если вместо атрибутов {Дети} и {Зарплата, Год}, стоящих в правых частях зависимостей, рассматривать булеаны (множества всех подмножеств) их доменов: B(Дети), B({Зарплата, Год}). Тогда можно записать следующие функциональные зависимости:

Служащий B(Дети),
Служащий В({Зарплата, Год}).

В этом случае происходит отказ от первой нормальной формы отношений (рис. 32), но многозначные зависимости сводятся к функциональным.

 R(Служащий, B(Дети), B({Зарплата, Год})
  Петров{Вася}{{800, 1999}, {900, 1999}}
  Cеров{Миша, Света}{{1000, 1999}, {1200, 2000}}

Рис. 32. Многозначная зависимость атрибутов

Другой пример отношения, между атрибутами которого существует многозначная зависимость, представлен на рис. 33.

ПРЕДМЕТ (Дисциплина, Преподаватель, Вид_работы),
Дисциплина Преподаватель,
Дисциплина Вид_работы.

Рис. 33. Отношение ПРЕДМЕТ и его МЗ

Пусть отношение ПРЕДМЕТ описывает следующую ситуацию в предметной области. Для каждой Дисциплины указывается список Преподавателей, которые могут ее обслуживать и список Видов_работ закрепленных за каждой дисциплиной. Преподаватель может обслуживать несколько Дисциплин, и разные дисциплины могут иметь одинаковые Виды_ работ (например, зачет, экзамен и т. д.). Каждый кортеж отношения связывает некоторый предмет с преподавателем, который его обслуживает, и видом работ, исполняемым им по данной дисциплине. Пусть отношение должно подчиняться правилу предметной области, согласно которому каждый преподаватель исполняет все виды работ, приписанные к конкретной дисциплине.

Условия, накладываемые на данное отношение, показывают, что единственным возможным реляционным ключом является составной атрибут: {Дисциплина, Преподаватель, Вид_работы}. Следовательно, отношение ПРЕДМЕТ находится в БКНФ.

Если отношение ПРЕДМЕТ будет храниться в физической базе как одно целое, то возможны следующие неприятные моменты:

Поэтому отношение ПРЕДМЕТ (рис. 33), согласно законам теории нормализации, должно быть декомпозировано по многозначным зависимостям на две проекции:

ПРЕДМЕТ_ПРЕПОДАВАТЕЛЬ (Дисциплина, Преподаватель) и
ПРЕДМЕТ_ВИД_РАБОТЫ (Дисциплина, Вид_работы).

Полученные проекции находятся в 4НФ и свободны от отмеченных аномалий.


[ Назад  Начало раздела  Далее  Содержание]