Многозначные зависимости

Пусть А, В и С являются произвольными подмножествами множества атрибутов отношения R. Говорить, что В многозначно зависит от А (А–››В или А многозначно определяет В), тогда и только тогда, когда множество значений (множество атрибутов) В зависит от множества значений атрибутов А и не зависит от множества значений атрибута С.

Рассматриваются зависимости, которые выполняются всегда, а не для данного состояния отношения.

Если в отношении R {А, В, С} выполняется многозначная зависимость А–››В, то каждому значению атрибутов А соответствует некоторое множество значений атрибутов В, причем значение атрибутов В не зависит от значения атрибутов С, а зависит только от значений атрибутов А. Таким образом, если зафиксировать значения А получим (a, b₁, c₁), (a, b₂, c₂)…(a, b_n, c_n), но тогда значению а соответствует некоторое множество значений В: {b₁, b₂… b_n}, но а соответственно множество значений С: {с₁, с₂… с_n}, т.е. существует и А–››С.

Этот факт имеет место всегда, т.е. многозначные зависимости существуют парами, что регистрируется как: А–››В|С, для примера КУРС–››ПРЕПОДАВАТЕЛЬ|УЧЕБНИК.

Заметим, что ФЗ является частным случаем многозначной зависимости (МЗ).

3. Теорема Фейгина.

Пусть А, В и С являются множествами атрибутов отношения R{А, В, С}. Отношение R будет равно соединению его проекций {A, B} и {A, C} тогда и только тогда, когда для отношения R выполняется многозначная зависимость А–››В|С.

Эта теорема является обобщенной теоремой ХЕЗА.

Отношение R находится в четвертой нормальной форме (4НФ) тогда и только тогда, когда если существуют такие подмножества А и В атрибутов отношения R, что выполняется (нетривиальная) многозначная зависимость А–››В, то все атрибуты отношения R также функционально зависимы от атрибута А.

В 4НФ могут существовать только нетривиальные зависимости (функциональные или многозначные) вида K→X, где К – потенциальный ключ, Х – любой атрибут.

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

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

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

Алгоритм транзитивной зависимости А→В и В→С можно ввести понятие многозначной функциональной зависимости А–››В и В–››С. В этом случае (наличие многозначной транзитивной зависимости) отношение R (A, B, C) следует также разбить на два отношения {А, В} и {В, С}.

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

Рассмотрим пример:

R

Поставщик	Детали	Проекты
Иванов
Иванов
Петров
Иванов

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

Рассмотрим три проекции этого отношения:

R₁

Поставщик	Детали
Иванов
Иванов
Петров

R₂

Детали	Проекты

R₃

Проекты	Поставщик
	Иванов
	Иванов
	Петров

Соединим R₁ и R₂ по атрибуту детали

R₄

Поставщик	Детали	Проект
Иванов
Иванов
Иванов
Петров

Петров11Соединим R₄ и R₃ по комбинации атрибутов (проект, поставщик)

R₅

Поставщик	Детали	Проект
Иванов
Иванов
Иванов
Петров

Отношение R₅=R

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

Итак получили свойства отношения R:

Отношение R нельзя разбить ни на какие два отношения, которые после соединения будут опять отношения R. Но если разбить R на три отношения, то после их соединения получим исходное отношение R. Такое отношение называется 3-х декомпозируемым отношением. Аналогично можно определить n-декомпозируемые отношения.

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

Свойства 3-х – декомпозируемости рассмотрено на конкретном состоянии отношения (в некоторый момент времени). Это свойство может быть и более фундаментальным и не зависеть от времени. Обозначим R_SPJ {S, P, J}

R_SP {S, P}=П_SPR_SPJ

R_PJ {P, J}=П_PJR_SPJ

R_JS {J, S}=П_JSR_SPJ

(1) (R_SPJ =R_SP join R_PJ join R_JS)~

(2) ~((s₁, p₁)Î R_SP)^ ((p₁, j₁)Î R_PJ)^ ((j₁, s₁)Î R_JS)→((s₁, p₁, j₁)Î R_SPJ) – обратное выполняется всегда!

(s₁, p₁)Î R_SP) ~(s₁, p₁, j₂)Î R_SPJ

(p₁, j₁)Î R_PJ)~(s₂, p₁, j₁)Î R_SPJ

(j₁, s₁)Î R_JS)~ (s₁, p₂, j₁)Î R_SPJ

(3) ((s₁, p₁, j₂)Î R_SPJ)^((s₂, p₁, j₁)Î R_SPJ)^((s₁, p₁, j₂)Î R_SPJ)→ (s₁, p₁, j₁)Î R_SPJ

Смысл (3): если s₁ связано с p₁ (т.е. находится в одном кортеже (вспомнить прямое произведение)), p₁ связано с j₁, и j₁ связано опять с s₁, то s₁, p₁ и j₁ должны находится в одном кортеже. Это циклическое ограничение!

Отношение будет n-декомпозируемым для n>2 тогда и только тогда, когда оно удовлетворяет некоторому циклическому ограничению.

Кратко 3-декомпозируемое ограничение обозначим 3D ограничение. Вернемся к примеру приведенному выше.

Пусть: деталь 1 – гаечные ключи, деталь 2 – гайки, тогда 3D ограничение для нашего примера означает:

Если Иванов поставляет гаечные ключи и гаечные ключи поставляются по проекту1, и Иванов является поставщиком проекта 1, то Иванов поставляет гаечные ключи по проекту 1.

Замечание: Данное утверждение справедливо не для всех отношений, а только для 3-декомпозируемых отношений, т.е. 3D ограничение должно присутствовать в предметной области.

Вывод (замечание):

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

Зависимость соединения такое же ограничение, как многозначная и функциональная зависимость.

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

Для отношения {S, P, J} обозначим SP={S, P}, PJ={P, J}, SJ={S, J}.

Пусть отношение обладает зависимостью.

Замечание: пусть дано отношение

R:{A, B, C} и есть две Ф.З. А→В и А→С по т. Хеза R можно разбить на два отношения

R₁:{A, B} и R₂:{A, С}

R=R₁ join R₂

Данная декомпозиция определяется (подразумевается) атрибутам(и) А.

По определению зависимости соединения такое соединение является ограничением, т.к. R=AB join AC.

Для отношения {S, P, J} имеет место зависимость соединения *(SP, PJ, JS), но нельзя указать атрибут(ы), которые определяют разбиение на SP, PJ, JS соединения *(SP, PJ, JS).

Аномалии такого отношения: пусть есть состояние:

S	P	J
S1	P1	J2
S1	P2	J1

Добавим кортеж (S₂, P₁, J₁) есть (S₁, P₁, J₂) и (S₂, P₁, J₁) и (S₁, P₂, J₁) тогда должен быть кортеж (S₁, P₁, J₁) т.е. его так же необходимо вставить. Если вставить (S₁, P₁, J₁), то добавить (S₂, P₁, J₁) не нужно.

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

Если удалить (S₂, P₁, J₁) то побочных эффектов нет.

Но если удалить (S₁, P₁, J₁), то необходимо удалить и один из основных 3 ^х кортежей, чтобы разорвать циклическое ограничение.

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

{K, X₁, X₂, …X_n}=>K→X₁, K→X₂, … K→X_n, где K – потенциальный ключ.

Пусть дано отношение {K, X₁, X₂, …X_n}, где К – потенциальный ключ, X₁, X₂, …X_n – прочие атрибуты.

Очевидно имеет место K→X₁, K→X₂, … K→X_n (ФЗ)

По т. Хеза имеет место *(КX₁, КX₂, …КX_n).

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

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

В отношении {S, P, J} есть зависимость соединения *(SP, PJ, JS), но она не определяется потенциальными ключами => необходима декомпозиция. Каждая из проекций

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

Дата добавления: 2014-01-05