70. Четвертая нормальная форма. Примеры.

Переход от НФБК к более высшей НФ очевидно может рассматриваться как следующий этап процедуры нормализации, состояний в том, чтобы отыскать МЗ не являющиеся ФЗ с целью избавления от них.

Действительно, теорема Фейгина позволяет формализовать данный этап процедуры нормализации.

1. Отношение R(A,B,C) – подмножества атрибутов, тогда отношение R будет эквивалентно соединению ее проекций R1(AB), R2(AC), тогда и только тогда когда в этом отношении выполняется МЗ А –>–>B/C.

Вот почему согласно т. Фейгина и вводится определение 4 НФ.

Отношение R находится в 4 НФ тогда и только тогда, когда существует такие подмножества атрибутов {AB}, что выполняется не тривиальное МЗ А –>–> B, причем все остальные атрибуты отношения R функционально зависят от А. Другими словами: отношение R, находящееся в 4 НФ должно содержать только не тривиальные зависимости типа ФЗ и МЗ, причем вида k –> x. Отсюда можно вывести более простое определение:

Отношение – атрибуты находятся в 4 НФ если оно находится в НФБК и все МЗ отношения R являются ФЗ с детерминантами в виде потенциальных ключей.

Например, отношение CTX не смотря на то, что находится в НФБК в 4 НФ не находится, поскольку содержит МЗ, которая не только не является ФЗ, но и не может быть ФЗ от потенциального ключа.

Напротив, обе проекции CT и СХ находятся в 4 НФ, которая по сравнению НФБК избавила нас от аномалий, а значит, позволила получить более высокую форму нормализации.

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

71. Зависимости соединения.

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

Отношения будем называть n–декомпозируемым если для него не существует такого эквивалентного набора из n–1 проекций и существует эквивалентный набор из n проекций.

Рассмотрим в качестве примера отношение SPJ (S#,P#,J#).

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

Рассмотрим тела отношений:

Рассмотрим соединение проекций SP и PJ по атрибуту P#

SPJ1

Очевидно, что отношение SPJ1 не эквивалентно отношению SPJ, т.к. мы получили избыточность.

Аналогично если рассмотреть соединение других пар проекций. Соединение других пар так же приведет к не эквивалентному. Однако если дополнительно провести соединение отношений SPJ1 и JS по (S#,J#), то мы в точности получим SPJ, это означает, что SPJ является тридекомпозируемым.

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

Это сложное ограничение истинно, т.к. тройка S1, P1, J1 действительно находится в соединение проекций SP, PJ, JS, исходя из этого, можно сделать вывод:

Любая пара {S1P1} должна присутствовать в отношении SP тогда и только тогда когда кортеж {S1P1Jk}присутствует в отношении SPJ для некоторого отношения Jk. Аналогичное утверждение можно сделать для пар вида {P8,J8}и т.д. Это позволяет записать более простое ограничение: Если кортеж {S1P1J2}, {S2P1J1} и {S1P2J1} принадлежат SPJ то кортеж {S1P1J1} тоже принадлежит SPJ. Последнее ограничение, очевидно, выполняется для любых допустимых значений отношения SPJ, а это значит что приведенное выше ограничение является новым типом зависимости – циклическая. Действительно, если S1 связано с P1, а P1 с J1, а J1 с S1, то кортеж {S1P1J1} принадлежит SPJ. Поэтому имеет место утверждение, что отношение будет n–декомпозируемым, тогда и только тогда когда оно будет удовлетворять некоторому циклическому ограничению. Осталось выяснить какова практическая ценность циклического ограничения. Ответ содержится в следующем этапе процедуры нормализации. Зависимость соединения – елси отношение удовлетворяет циклическим ограничения, это означает что данное отношение равносильно соединению нескольких его проекций (больше двух). Другими словами это ограничение называется зависимость соединения, т.е. ЗС является таким же ограничением на структуру данных отношения как МЗ и ФЗ. Рассмотрим формальное определение ЗС: Пусть R является отношение с атрибутам A1,A2,...An, а A,B,...,Z – подмножество атрибутов. Тогда говорят, что отношение R удовлетворяет ЗС и обозначается *(A,B,...,Z) тогда и только тогда когда отношение R равносильно соединению соответствующих проекций по подмножествам атрибутов R(A1,A2,...An)= .

Например, если вернутся к отношению SPJ то можно утверждать что это отношение удовлетворяет *(SP,PJ,JS) или, что тоже самое – отношение SPJ является тридекомпозируемым. Как и с 4 НФ возникает следующий вопрос, а следует вообще проводить подобные декомпозиции?

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

Отношение R(A,B,C) удовлетворяет ЗС *(AB,AC) тогда и только тогда когда это отношение удовлетворяет МЗ A –>–> B/C, данную теорему можно рассматривать как еще одно определение МЗ. Отсюда следует, что МЗ частный случай ЗС. Либо PC – обобщение МЗ.