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

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

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

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

Следует отметить, что утверждение о том, что «переменная-отношение SPJ равна соединению трех своих проекций SP, PJ и JS» эквивалентно следующему утверждению:

ЕСЛИ пара (s1,p1) присутствует в SP

И пара (p1,j1) присутствует в PJ

И пара (j1,s1) присутствует в JS

ТО тройка (s1,p1,j1) присутствует в SPJ

Таким образом, можно прийти к заключению, что:

ЕСЛИ кортежи (s1,p1,j2), (s2,p1,j1), (s1,p2,j1) присутствуют в SPJ

ТО кортеж (s1,p1,j1) также присутствует в SPJ.

Если это утверждение выполняется всегда, т.е. для всех допустимых значений переменной-отношения SPJ, то будет получено не зависящее от времени ограничение для данной переменной-отношения. Ограничение имеет циклическую структуру: если значение s1 связано с p1 и p1 связано с j1, а j1 связано опять с s1, то s1, p1и j1 должны находиться в одном кортеже. Переменная-отношение будет n-декомпозируемой для n>2 тогда и только тогда, когда она удовлетворяет некоторому циклическому ограничению.

SPJ

S#	P#	J#
S1	P1	J2
S1	P2	J1
S2	P1	J1
S1	P1	J1

SP

S#	P#
S1	P1
S1	P2
S2	P1

PJ

P#	J#
P1	J2
P2	J1
P1	J1

JS

S#	J#
S1	J2
S1	J1
S2	J1

Соединение по атрибуту P#

SPJ

S#	P#	J#
S1	P1	J2
S1	P2	J1
S2	P1	J1
S2	P1	J2
S1	P1	J1

 

Соединение по комбинации атрибутов S#,J#

Исходное состояние SPJ

Рис. 12.4. Переменная-отношение SPJ может быть получена только соединением 3-х проекций

В реальном мире данную ситуацию можно проиллюстрировать следующим образом. Если верны утверждения:

а) Смирнов поставляет гаечные ключи,

б) Гаечные ключи используются в проекте П1,

в) Смирнов является поставщиков для проекта П1,

то

г) Смирнов поставляет гаечные ключи для проекта П1.

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

Пусть R является переменной-отношением, а A,B,…,Z – произвольными подмножествами множества ее атрибутов. Переменная-отношение R удовлетворяет зависимости соединения :

* {A,B,…,Z} (читается «звездочка A,B,…,Z»)

тогда и только тогда, когда любое допустимое значение переменной-отношения R эквивалентно соединению ее проекций по подмножествам атрибутов A,B,…,Z.

В нашем примере это можно было бы записать как *{SP,PJ,JS}, где SP – сокращенная запись для {S#,P#}, аналогично и PJ, JS. Отсюда следует, что переменная-отношение SPJ является 3-декомпозируемой, и необходимо выполнить ее декомпозицию для исключения многочисленных аномалий обновления, возникающих в ней. Некоторые примеры подобных аномалий приведены на рис. 12.5.

Используя понятие зависимости соединения можно переформулировать теорему Фейгина:

Переменная-отношение R{A,B,C} удовлетворяет зависимости соединения *{AB,AC} тогда и только тогда, когда она многозначной зависимости A ®® B | C.

SPJ

 

S#	P#	J#
S1	P1	J2
S1	P2	J1

SPJ

 

S#	P#	J#
S1	P1	J2
S1	P2	J1
S2	P1	J1
S1	P1	J1

Если вставляется кортеж (S2,P1,J1), то также должен быть вставлен кортеж (S1,P1,J1) Обратное утверждение неверно.

Кортеж (S2,P1,J1) может быть удален без побочных эффектов. Если удаляется кортеж (S1,P1,J1), то также должен быть удален еще один кортеж (но какой?)

Рис.12.5. Примеры аномалий обновления в переменной-отношении SPJ

Таким образом, A ®® B | C º *{AB,AC} и многозначная зависимость является частным случаем зависимости соединения. Из всех возможных форм зависимость соединения является наиболее общей формой зависимости, т.е. не существует иной формы зависимости, по отношению к которой зависимость соединения является всего лишь частным случаем.

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

Переменная-отношение R находится в пятой нормальной форме (5НФ), которую иногда иначе называют проекционно-соединительной нормальной формой (ПСНФ), тогда и только тогда, когда каждая нетривиальная зависимость соединения в переменной-отношении R подразумевается ее потенциальными ключами.

Зависимость соединения * {A,B,…,Z} называется тривиальной тогда и только тогда, когда одна из проекций A,B,…,Z является проекцией идентичной R.

Для пояснения вопроса о том, что значит «подразумевается потенциальными ключами» рассмотрим в качестве примера переменную-отношение поставщиков S с потенциальными ключами S# и SNAME. Такая переменная-отношение удовлетворяет следующей зависимости соединения:

* { {S#,SNAME,STATUS}, {S#,CITY} }

Следовательно, переменная-отношение S может быть подвергнута декомпозиции без потерь на указанные проекции. Существование данной ЗС доказывается на основании, что S# - потенциальный ключ и теоремы Хита. Кроме того, так как имеется два потенциальных ключа, то существует и следующая ЗС:

* { {S#,SNAME} {S#,STATUS}, {SNAME,CITY} }

Как следует из приведенного примера зависимость соединения * {A,B,…,Z} подразумевается потенциальными ключами тогда и только тогда, когда каждое подмножество атрибутов A,B,…,Z фактически является суперключом для данной переменной-отношения.

Таким образом, относительно заданной переменной-отношения R можно утверждать, что она находится в 5НФ, только при условии, что известны все ее потенциальные ключи и все зависимости соединения, существующие в ней. Однако, как следует из опыта, подобные переменные-отношения (n-декомпозируемые) достаточно экзотичны и чрезвычайно редко встречаются.

Дата добавления: 2015-05-09