Теорема Хеза. Частные случаи декомпозиции без потерь

Последовательное выделение функциональных зависимостей минимального покрытия в отдельное отношение не всегда приводит к нормализации отношения. Чаще всего такие ситуации возникают тогда, когда отношение имеет несколько ключей. Рассмотрим отношение со схемой R={ABC} и множеством функциональных зависимостей на этой схеме {AB®C, C®B}, которое имеет два ключа: AB и AC. При этом один из них AC не является детерминантом (см. Таблица 18). В отношении наблюдается аномалия, обусловленная тем, что атрибут В, являясь основным атрибутом, зависит от собственного подмножества второго ключа AC (следовательно, отношение не находится во второй нормальной форме). Традиционное выделение в отдельное отношение функциональной зависимости не позволяет решить проблему - появляется новое отношение со схемой R={CB}, но при этом сохраняется и исходное отношение. Очевидно, что требуется найти иной способ декомпозиции исходного отношения. Ответ на поставленный вопрос дает приведенная ниже теорема Хеза (см. Определение 39).

Таблица 18

Детерминанты	Ключи
C	AC
AB	AB

Определение 39

Если на схеме отношения r(R)={ AB C} имеет место функциональная зависимость A®C, то отношение декомпозируется без потерь на два отношения r₁={ AB }, r₂={ A C}.

В вышеприведенном примере того, чтобы применить теорему Хеза, придется исключить из рассмотрения функциональную зависимость AB®C. Тогда согласно теореме исходное отношение разбивается на два: R₁={B C }, R₂={ AC }. Функциональная же зависимость AB®C теперь должна поддерживаться программным путем.

Проиллюстрируем этот способ декомпозиции примером.

Таблица 19

Исходное отношение R= (AB C) Fmin={AB®C, C®B}.
A	B	C
a1	b2	c1
a2	b2	c2
a2	b3	с3

Таблица 20

Декомпозиция без потерь.
A	C		B	C
a1	c1		b1	c1
a2	c2		b2	c2
a3	c3		b3	c3

Соединение вновь полученных отношений по общему атрибуту С даст исходное отношение.

Ниже приведена декомпозиция этого же отношения на отношения { C A} и { AB } (см. Таблица 21). Налицо потеря информации, то есть результатом соединения отношений, полученных в результате такой декомпозиции, будет отношение, отличное от исходного (см. Таблица 22).

Таблица 21

Декомпозиция на атрибуты {AB} и {BC} выполняется с потерей информации.
	Отношение r1		Отношение r1
	A	B		B	C
	a1	b2		b2	c1
	a2	b2		b2	c2
	a2	b3		b3	c3

Таблица 22

Результат соединения по общему атрибуту B.
A	B	C
a1	b2	с1
a1[5]	b2	c2
a2	b2	c1
a2	b2	c2
a2	b3	c3

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

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

Рассмотрим элементарное отношение со схемой R={ A BC} и множеством функциональных зависимостей на ней F={A®B, B®C}. Декомпозиция без потерь этого отношения может быть выполнена двумя способами: либо R₁={ A B},R₂={ A C}(cм. Таблица 24), либоR₁={ A B}, R₂={ B C} (см. Таблица 25 ). Однако в первом случае (см. Таблица 24) утеряна функциональная зависимость B®C, которая должна будет поддерживать программнымпутем, второй способ позволяет сохранить все функциональные зависимости (навязать их базе данных) и исключить избыточное дублирование.

Таблица 23

Исходное отношение.
A	B	C
a1	b1	c1
a2	b2	c2
a3	b2	c2

Таблица 24

Декомпозиция с потерей функциональной зависимости B®C:
A	B		A	C
a1	b1		a1	c1
а2	b2		a2	c2
а3	b2		a3	c2

Таблица 25

Наиболее корректный способ декомпозиции – исключается избыточность и сохраняются все функциональные зависимости.
A	B		B	C
a1	b1		b1	c1
a2	b2		b2	c2
a3	b2

Дата добавления: 2014-12-17