Понятие многозначной зависимости, четвертой нормальной формы (4НФ). Теорема Фейгина

При рассмотрении нормализации от 1НФ до НФБК использовалось понятие функциональной зависимости. Но существуют и другие типы зависимостей. Одними из них являются многозначные зависимости.

Рассмотрим пример схемы отношения, описывающей курсы(C), преподавателей(T) и названия учебников(X): R(#C,#T, #X) Каждый курс могут преподавать несколько преподавателей, в каждом курсе могут быть использованы несколько учебников. Каждый курс может преподаваться любым преподавателем соответствующей группы с использованием всех учебников данного курса. Пусть имеем 2 курса два преподавателя и по два учебника для каждого курса. Для данного отношения допустимо существование всех возможных комбинаций преподавателей и учебников. Между курсом и преподавателями существует связь 1:M, а также между курсами и учебниками.

Схема является полностью ключевой, находится в НФБК, но имеет очевидные недостатки: большую избыточность, трудности обновления. Например, ввод нового учебника, нового преподавателя.

Если заменить R его проекциями R1(C,T) и R2(C, X), то все проблемы будут решены. Обе проекции являются полностью ключевыми и находятся в НФБК. Исходное отношение может быть восстановлено с помощью обратного соединения проекций. Но эта декомпозиция не была выполнена на основе функциональных зависимостей. В рассм. примере существуют 2 многозначные зависимости: 1) C--->>T; 2) C--->>X. (--->> - многозначно определяет). Первая означает, что хотя для каждого курса не существует одного преподавателя, соответствующего данному курсу, т.е. не выполняется функциональная зависимость, C--->T, тем не менее каждый курс имеет вполне определенное множество преподавателей и это множество не зависит от множества учебников (X). Аналогично интерпретируется вторая многозначная зависимость (МЗ).

Определение многозначной зависимости(МЗ). Пусть A,B, C являются произвольными подмножествами атрибутов R. Тогда B многозначно зависит от A, что обозначается как A --->>B и читается, как “A многозначно определяет B”, если при заданных значениях атрибутов из А существует множество, состоящее из 0 или более ассоциированных значений атрибутов из B и это множество В не связано каким-либо образом со значениями других атрибутов (С). Таким образом, в отношении R (A, B, C) существует многозначная зависимость R.A - ->> R.B в том и только в том случае, если множество значений B, соответствующее паре значений A и C, зависит только от A и не зависит от С. Для наличия многозначной зависимости необходимо по крайней мере три атрибута: ключ и два независимых атрибута. В работах Фейгина (Fegin) показывается, что для данного отношения R(A, B, C) многозначная зависимость A--->>B выполняется тогда и только тогда. когда выполняется также и МЗ: A--->>C. Таким образом, многозначные зависимости всегда образуют связанные пары, обозначаемые как A--->>B | C. В нашем примере C--->>T | X.

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

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

Теорема Фейгина. Пусть A, B, C являются мн. атрибутов R(A, B, C). Отношение R будет равно соединению его проекций R1(A,B) и R2(A, C) тогда и только тогда, когда для отношения R выполняется многозначная зависимость A--->>B | C.

Опр. 4НФ 1. Отношение находится в 4НФ, если оно находится в НФБК и в нем отсутствуют многозначные зависимости, которые не являются функциональными.

2. Формальное. Пусть R - схема отношения. Будем считать, что R находится в 4НФ, если всякий раз, когда существует многозначная зависимость X--->> Y, где Y не пусто и не является подмножеством X, и XY состоит не из всех атрибутов, X содержит какой-либо ключ.

Иначе говоря, в отношении R могут находится только нетривиальные зависимости, функциональные или многозначные, вида: K--->X. Если существуют только функциональные зависимости, то R находится в 4НФ, значит и в НФБК.

Алгоритм декомпозиции в 4НФ. Если в R существует многозначная зависимость X--->> Y, где X не содержит ключа (нарушение 4НФ), Y не пусто и не является подмножеством X и XY не являются всеми атрибутами R, то R можно заменить двумя схемами отношений: R1=XY и R2=RA-Y (все атрибуты R минус Y). Пример2. Схема отношения, описывающая занятия студентов спортом в спортклубах: R(Студент, Спорт_клуб, Вид_спорта, Год_занятий)

МЗ: Студент--->>Спорт_клуб;

Студент--->>Вид_спорта, Год_занятий

Декомпозиция: R1(#Студент,Спорт_клуб); R2(#Студент,Вид_спорта, Год_занятий).

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

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

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

X. Зависимости соединения и 5НФ

До сих пор предполагалось, что в процессе декомпозиции выполняется замена отношения двумя его проекциями. Соединив проекции, мы получим исходное отношение. Однако, существуют отношения, для которых нельзя выполнить декомпозицию без потерь на две проекции, но которые можно подвергнуть декомпозиции без потерь на 3 и более проекции. Рассмотрим в качестве примера отношение поставок, содержащее информацию о поставщиках (S), деталях (P), проектах (J):

Получим 3 проекции: SP, PJ, SJ. Соединим две из них и получим лишний кортеж в отношении. И только соединив все три, получаем исходное отношение.

Первичным ключем данного отношения является полная совокупность его атрибутов, отсутствуют функциональные и многозначные зависимости. Поэтому отношение находится в 4NF. В отношении мы имеем некоторую циклическую структуру ограничений. Это можно сформулировать следующим образом: если в отношении находятся корткжи <s1, p1, j2>, <s1, p2, j1>, <s2, p1, j1>, то в отношении присутствует также кортеж <s1, p1, j1>. Это приводит к многочисленным аномалиям. Например, удаление кортежа <s1, p1, j1> ведет к удалению трех кортежей. или вставка кортежей. Существовующие аномалии можно устранить путем декомпозиции в три отношения.

Определение: Зависимости соединения

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

Отношение R удовлетворяет зависимости соединения *(A, B,..., Z) т и т т, когда R равносильно соединению своих проекций с подмножествами атрибутов А, В,..., Z.

Рассматриваемое отн. SPJ удовлетворяет зависимостям соединения *(SP, PJ, SJ).

Исходя из теоремы Фейгина, рассмотренной выше, отношение R(A, B, C) будет равно соединению его проекций R1(A,B) и R2(A, C) тогда и только тогда, когда для отношения R выполняется многозначная зависимость A--->>B | C.

Теорема Фейгина для зависимости соединения. Пусть A, B, C являются множествами атрибутов R(A, B, C). Отношение R будет удовлетворять зависимости соединения *(AB, BC) тогда и только тогда, когда для отношения R выполняется многозначная зависимость A--->>B | C.

Многозначная зависимость является частным случаем зависимости соединения.

Опр.: 5НФ Отношение R находится в пятой нормальной форме (нормальной форме проекции-соединения - PJ/NF) тогда и только тогда, когда любая зависимость соединения в отношении R лпределяется возможными ключами R. Рассмотренное отношение не находится в 5НФ. Оно удовлетворяет зависимости соединения проекций *(SP, PJ, SJ). Проекции находятся в 5 НФ, так как для них нет зависимостей соединения.

Например, отношение поставщики POST(Np, Name, Status, City) с двумя возможными ключами Np, Name. Такое отн. удовлетворяет неск. зависимостям соединения:

*((Np, Name, Status), (Np, City)), так как исходное отн. равносильно соединению данных проекций. Сущ. этой зависимости следует из того, что NP явл. возможным ключем.

Аналогично, зависимость соединения *((Np, Name),(Np, Status), (Name, City)).

Эта зависимость следует из того, что NP и Name являются возможными ключами. Если отношение находится в 5НФ, то все зависимости соединения определяются возможными ключами. Т.е. Каждая проекция должна состоять из одного или нескольких потенциальных ключей, а также независимых дополнительных атрибутов.

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

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