2.5.5. Пятая нормальная форма

Подойдем к обсуждению понятия "многозначная зависимость" с другой стороны. Чисто формально, отношение, представленное на рис. 33, имеет две многозначные зависимости:

Дисциплина Преподаватель и
Дисциплина Вид_работы.

Если же рассмотреть семантику этих многозначных зависимостей, то, она может быть существенно разная.

Любая дисциплина, считается освоенной студентом, если он выполнил все Виды_работ, предписанные для данной дисциплины учебным планом. Например, чтобы "закрыть" дисциплину "Базы данных", необходимо пройти следующие виды занятий и испытаний (Виды_работ): {лекции, практика, зачет, курсовой проект, экзамен}, которые обязательны для этой дисциплины, вне зависимости от преподавателей, ведущих данную дисциплину.
Т.е. зависимость Дисциплина Вид_работы действительно многозначная: чтобы определить значение компоненты, стоящей слева от знака "", требуются одновременно все значения компонент, зафиксированных для нее справа, вне зависимости, от каких либо третьих факторов.

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

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

Поясним сказанное на примере. Пусть имеется отношение ТЕХНОЛОГИЧЕСКАЯ_КАРТА (Деталь, Материал, Технология), состояние которого имеет вид, показанный на рис. 34.

ДетальМатериалТехнология
Д1М1Т1
Д1М2Т3
Д2М3Т1
Д3М1Т2
Д3М4Т2

Рис. 34. Состояние отношения ТЕХНОЛОГИЧЕСКАЯ_КАРТА

Пусть, далее, заданы следующие "вариантные" зависимости (для обозначения таких зависимостей будет использоваться обозначение ):

Деталь Материал,
Деталь Технология,
Материал Технология.

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

Используя эти три "вариантные" зависимости, можно однозначно построить отношение: ТЕХНОЛОГИЧЕСКАЯ_КАРТА (Деталь, Материал, Технология) из следующих его проекций (рис. 35 - 37):

ДетальМатериал
Д1М1
Д1М2
МатериалТехнология
М1Т1
М1Т2
ДетальТехнология
Д1Т1
Д1Т3
Рис.35. ПроекцияРис. 36. ПроекцияРис. 37. Проекция
ДЕТАЛЬ_МАТЕРИАЛМАТЕРИАЛ_ТЕХНОЛОГИЯДЕТАЛЬ_ТЕХНОЛОГИЯ

Следующее предложение реляционной алгебры [30]:

ТЕХНОЛОГИЧЕСКАЯ_КАРТА(Деталь, Материал, Технология) =
(ДЕТАЛЬ_МАТЕРИАЛ [Деталь=Деталь] ДЕТАЛЬ_ТЕХНОЛОГИЯ)
[(Материал=Материал) AND (Технология=Технология)] МАТЕРИАЛ_ТЕХНОЛОГИЯ

восстанавливает исходное отношение ТЕХНОЛОГИЧЕСКАЯ_КАРТА (рис. 34). Следует отметить, что приведенное предложение должно быть зафиксировано в системе (в схеме базы данных), т. к. оно описывает существующее в предметной области ограничение и указывает, каким образом могут быть соединены отношения.

При реализации данного утверждения, система, выполняя соединение ТЕХНОЛОГИЧЕСКАЯ_КАРТА(Деталь, Материал, Технология) = ДЕТАЛЬ_МАТЕРИАЛ [Деталь=Деталь] ДЕТАЛЬ_ТЕХНОЛОГИЯ, получит в промежуточном отношении ТЕХНОЛОГИЧЕСКАЯ_КАРТАR лишние строки t2 и t3 (рис. 38), запрещенные многозначной зависимостью МатериалТехнология (рис. 36).

 ДетальМатериалТехнология
t1Д1М1Т1
t2Д1М2Т1
t3Д1М1Т3
t4Д1М2Т3
t5Д2М3Т1
t6Д3М1Т2
t7Д3М4Т2

Рис. 38. Состояние отношения ТЕХНОЛОГИЧЕСКАЯ_КАРТАR

Строки t2 и t3 из отношения ТЕХНОЛОГИЧЕСКАЯ_КАРТАR исключаются частью предложения:
ТЕХНОЛОГИЧЕСКАЯ_КАРТАR [(Материал=Материал) AND (Технология=Технология)] МАТЕРИАЛ_ТЕХНОЛОГИЯ

Если рассмотренное утверждение реляционной алгебры выполняется всегда (для всех допустимых значений отношения ТЕХНОЛОГИЧЕСКАЯ_КАРТА), то тем самым формируется независимое от времени ограничение, присущее отношению ТЕХНОЛОГИЧЕСКАЯ_КАРТА, которое должно быть отображено в схеме базы данных. К сожалению, стандарт SQL не содержит правил поддержания подобных ограничений.

Отметим, что также явно должно быть указано ограничение для соединения отношений ДЕТАЛЬ_МАТЕРИАЛ(Деталь, Материал) и МАТЕРИАЛ_ТЕХНОЛОГИЯ(Материал, Технология), иначе без такого ограничения из базы данных может быть получена информация, не соответствующая действительности. В частности, результатом запроса

SELECT *
FROM ДЕТАЛЬ_МАТЕРИАЛ, МАТЕРИАЛ_ТЕХНОЛОГИЯ
WHERE ДЕТАЛЬ_МАТЕРИАЛ.Деталь = МАТЕРИАЛ_ТЕХНОЛОГИЯ.Деталь;

будет отношение, показанное на рис. 39.

 ДетальМатериалТехнология
t1Д1М1Т1
t2Д1М1Т2
t3Д1М2Т3
t4Д2М3Т1
t5Д3М1Т1
t6Д3М1Т2
t7Д3М4Т2

Рис. 39. Ловушка соединения отношений ДЕТАЛЬ_МАТЕРИАЛ и МАТЕРИАЛ_ТЕХНОЛОГИЯ

В полученном отношении присутствуют кортежи t2 и t5, которые отсутствуют в правильном ответе (рис. 34). Заметьте, что запрос на языке SQL синтаксически не противоречит правилам языка. Поэтому пользователь вправе считать, что выданный результат соответствует действительности.

Подобная проблема может возникнуть при запросе к базе данных к отношениям, представленным на рис. 36 и 37.

Таким образом, схема базы данных (определение понятия схемы базы данных см. далее), состоящей из перечисленных отношений (ключи в этих отношениях подчеркнуты) и явно заданных (зафиксированных) правил их совместного использования, будет выглядеть так, как это показано на рис. 40.

Отношения:
ДЕТАЛЬ_МАТЕРИАЛ(Деталь, Материал),
МАТЕРИАЛ_ТЕХНОЛОГИЯ(Материал, Технология),
ДЕТАЛЬ_ТЕХНОЛОГИЯ(Деталь, Технология),

Правила восстановления:
ТЕХНОЛОГИЧЕСКАЯ_КАРТА (Деталь, Материал, Технология)=
(ДЕТАЛЬ_МАТЕРИАЛ [Деталь=Деталь] ДЕТАЛЬ_ТЕХНОЛОГИЯ)
[(Материал=Материал) AND (Технология=Технология)] МАТЕРИАЛ_ТЕХНОЛОГИЯ,

ТЕХНОЛОГИЧЕСКАЯ_КАРТА (Деталь, Материал, Технология)=
(ДЕТАЛЬ_ТЕХНОЛОГИЯ [Технология=Технология] МАТЕРИАЛ_ТЕХНОЛОГИЯ)
[(Деталь=Деталь) AND (Материал=Материал)] ДЕТАЛЬ_МАТЕРИАЛ,

ТЕХНОЛОГИЧЕСКАЯ_КАРТА (Деталь, Материал, Технология)=
(ДЕТАЛЬ_МАТЕРИАЛ [Материал=Материал] МАТЕРИАЛ_ТЕХНОЛОГИЯ)
[(Деталь=Деталь) AND (Технология=Технология)] ДЕТАЛЬ_ТЕХНОЛОГИЯ.

Рис. 40. Схема базы данных и правила восстановления исходного отношения

Заметим, что если исходное отношение ТЕХНОЛОГИЧЕСКАЯ_КАРТА (рис. 34) не разбивать на проекции, то возможны аномалии при модификации отношения. Это несложно доказать, в силу чего такое доказательство оставляется читателю в качестве упражнения.

Рассмотрим еще один случай зависимости соединения.

Пусть имеются три проекции (рис. 41) некоторого исходного отношения R (рис. 42):
 R1(A, B)  R2(A, C) R3(B, C)
1  11  11  1
1  21  22  1
1  32  13  2
2  12  34  3
2  43  44  4
3  4

Рис. 41. Состояния проекций отношения R

Тогда, если правило восстановления исходного отношения R(A, B, C) записано формулой:

R=(R1 [A=A] R2) if [B=B AND C=C] R3,
то в результирующее отношение должны попасть такие кортежи из R1 и R2 по операции эквисоединения на атрибуте A, у которых проекции по атрибутам В и C есть в отношении R3.

Истинный результат R, получаемый после удаления ложных выборок из эквисоединения R' показан на рис. 42.
 R'(A, B, C) R2(A, B, C) 
1   1   11   1   1
1   1   2 -1   2   1
1   2   11   3   2
1   2   2 -2   1   1
1   3   1 -2   4   3
1   3   23   4   4
2   1   1
2   1   3 -
2   4   1 -
2   4   3
3   4   4

Рис. 42. Эквисоединение R' (знак "-" указывает ложные выборки) и истинное отношение R

Истинный результат также будет получен, если использовать правило R = (R2 [C=C] R3) if [B=B AND.C=C] R1 или R = (R1 [B=B] R3) if [A=A AND C=C] R2

Нетрудно заметить, что данное правило исполняется, т.к. в отношении R имеет место ABC (атрибуты AB функционально определяют атрибут С).

Определение [3]. Пусть R является отношением, а X, Y, ..., Z - произвольные подмножества атрибутов AR отношения R. Отношение R удовлетворяет зависимости соединения:

(X, Y, ..., Z)
в том и только том случае, когда R восстанавливается без потерь, путем соединения своих проекций c подмножествами атрибутов X, Y, ..., Z.

Определение. Пятая нормальная форма.

Отношение R находится в пятой нормальной форме (нормальной форме проекции-соединения - PJ/NF) в том и только том случае, когда любая зависимость соединения в R следует из существования некоторого возможного ключа в R.

Существует и другое определение 5НФ, принадлежащее Фэйджину [3]:
Отношение R находится в 5НФ тогда и только тогда, когда каждая зависимость соединения подразумевается потенциальными ключами отношения.

Пятая нормальная форма - это последняя нормальная форма, которую можно получить путем декомпозиции [3]. Заметим, что зависимость соединения является обобщением, как многозначной зависимости, так и функциональной зависимости и на практике ее выявить достаточно трудно.

В заключение рассмотрения 5НФ проанализируем процесс модификации данных для схемы, представленной на рис. 40. Пусть пользователь решил добавить в отношение RДМ = ДЕТАЛЬ_МАТЕРИАЛ (рис. 35) последнюю строку, такую, что состояние отношения RДМ приняло вид R1ДМ (рис. 43):

ДетальМатериал
Д1М1
Д1М2
Д2М3
Д3М1
Д3М4
Д1М3

Рис. 43. Cостояние R1 ДМ отношения ДЕТАЛЬ_МАТЕРИАЛ (рис. 35)

Правомерно ли появление шестой строки в таблице на рис. 43? Или, другими словами, правомерно ли существование исходного отношения R (рис. 44), дающего такую проекцию?

ДетальМатериалТехнология
Д1М1Т1
Д1М2Т3
Д2М3Т1
Д3М1Т2
Д3М4Т2
Д1М3Т1

Рис. 44. Состояние отношения ТЕХНОЛОГИЧЕСКАЯ_КАРТА, дающее проекцию, представленную на рис. 43

Если описание схемы базы данных (см. ниже), представленное на рис. 40, остается в силе, то первое, что сделает система контроля ввода данных, это проверит, не нарушается реляционный ключ в отношении R1 ДМ (рис. 43) и содержатся ли в соответствующих доменах введенные значения строки (по определению все атрибуты рассматриваемых отношений являются внешними ключами). Считаем, что в нашем примере указанных противоречий нет, т.е. в системе определены базовые таблицы для объектов ДЕТАЛЬ, МАТЕРИАЛ и ТЕХНОЛОГИЯ, где атрибуты Деталь, Материал и Технология объявлены первичными ключами.

Далее необходимо проверить формульные ограничения, указанные на рис. 40, т.е. проанализировать отношения RМТ = МАТЕРИАЛ_ТЕХНОЛОГИЯ (рис. 36) и RДТ = ДЕТАЛЬ_ТЕХНОЛОГИЯ (рис. 37). Нетрудно убедиться, что никаких противоречий система не обнаружит, т.к. значения <Д1, T1> (технология Т1 используется при изготовлении детали Д1) и <М3, Т1> (технология Т1 использует материал М3) уже присутствуют в RМТ (рис. 36) и RДТ (рис. 37).

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

В частности, технологический поцесс Т1 изготовления детали Д1 из материала М3 может нигде и не использоваться, поэтому его присутствие в базе данных может привести к неверным ответам, например на запрос о существовании такой детали.

После введения понятий зависимостей, ключа и нормальных форм можно пополнить понятие схемы R одношения R, определив ее как пятерку, состоящую из имени R отношения R, множества атрибутов AR отношения R, среди которых выделено подмножество KR, составляющее главный ключ отношения, множества зависимостей FR, определенных на булеане B(AR) множества атрибутов и множество правил ограничений соединения PR отношения R, т.е.

R = {R, AR, KR, FR, PR}.

В ряде случаев схему R отношения R упрощенно можно рассматривать и как "пустое" состояние (или R0) этого отношения, т.е. просто, как запись отношения, не содержащего в себе никаких кортежей:

R(A1, A2, . . . , An).
Конечно, такая запись не включает в себя зависимостей и ограничений соединения, хотя ключи в ней могут быть обозначены (подчеркиванием).

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

Пусть R1, R1, . . . , Rn – множество схем нормализованных отношений, образующих базу данных R. Тогда схема R базы данных R будет представлять собой пятерку:

R = {{R1, R2, . . . , Rn}, {AR1, AR2, . . . , ARn}, {KR1, KR2, . . . , KRn}, {FR1, FR2, . . . , FRn} FL, {PR1, PR2, . . . , PRn}},

где FL – множество зависисмостей исходных отношений, которые могут быть "потеряны" при их нормализации (см. выше п. 2.5.3)

Строго говоря, для определения FL необходимо оперировать исходными (возможно, ненормализованными) отношениями.


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