Определение. Пусть R(A, B, C) – схема отношения с атрибутами (подмножествами атрибутов) A, B и C

Теорема

Пусть R(A, B, C) – схема отношения с атрибутами (подмножествами атрибутов) A, B и C. Если данная схема отношения удовлетворяет функциональной зависимости A  B, то осуществляется декомпозиция без потери на {R₁, R₂}, где R₁ = {A, B} и R₂ = {A, C}.

Вернемся к приведенному выше примеру: S(S#, STATUS, CITY}. Так как S# – первичный ключ отношения, то S#  CITY. Отсюда, декомпозиция без потери осуществляется на подсхемы S1(S#, CITY) и S2(S#, STATUS). Функциональные зависимости STATUS  S# или STATUS  CITY отсутствуют, поэтому второй пример декомпозиции не сохраняет исходное отношение.

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

S#  CITY

CITY  STATUS

В соответствии с теоремой можно предложить два способа декомпозиции без потери информации:

• относительно S#  CITY: S11(S#, CITY) и S12(S#, STATUS)

• относительно CITY  STATUS: S21(CITY, S#) (или S21(S#, CITY) – порядок задания имен атрибутов никакого значения не имеет) и S22(CITY, STATUS)

Какой из этих двух способов лучше?

Чтобы ответить на этот вопрос, введем еще одно определение:

Проекцией множества функциональных зависимостей F на множество атрибутов Z (π_Z (F)) называется множество зависимостей X  Y в F⁺, таких, что XY ⊆ Z.

Рассмотрим все тот же пример.

Для исходного отношения определено следующее множество функциональных зависимостей:

F = {S#  CITY, CITY  STATUS}

Из них по правилам вывода можно вывести следующие зависимости:

S#  STATUS – правило транзитивности;

S#  (CITY, STATUS) – правило объединения.

Отсюда,

F⁺ = {S#  CITY, CITY  STATUS, S#  STATUS, S#  (CITY, STATUS)}

Для способа a) декомпозиции определены следующие функциональные зависимости:

S#  STATUS, из схемы отношения S11(S#, STATUS)

S#  CITY, из схемы отношения S12(S#, CITY)

Для способа b) декомпозиции определены следующие функциональные зависимости:

S#  CITY, из схемы отношения S21(S#, CITY)

CITY  STATUS, из схемы отношения S22(CITY, STATUS)

Говорят, что декомпозиция сохраняет множество функциональных зависимостей F, если из объединения всех зависимостей, принадлежащих π_Ri (F), для i = 1, 2, …, k, логически следуют все зависимости, принадлежащие F.

Из функциональных зависимостей, сохранившихся при способе декомпозиции a), нельзя логически вывести зависимость CITY  STATUS, т.е. данная декомпозиция не сохраняет функциональные зависимости.

Для способа декомпозиции b) все функциональные зависимости из F сохранены.

Что дает сохранение функциональных зависимостей? Рассмотрим следующий пример.

Пусть дана следующая реализация отношения:

S	(S#,	STATUS,	CITY)
	S1		N1
	S2		N2
	S3		N3

Выполним декомпозицию этого отношения способом a):

	S11	(S#,	CITY)		S12	(S#,	STATUS)
		S1	N1			S1
		S2	N2			S2
		S3	N3			S3

Предположим, что поставщик S2 переехал в город N3. Тогда в отношении S11 появится кортеж <S2, N3>. Но в отношении S12 сохраняется кортеж <S2, 30>, в соответствии с которым город N3 приобретает статус 30, что неправильно. Следовательно, для поддержания достоверного состояния реализаций потребуется изменить не только кортеж в S11, но и кортеж в S12, т.е. требуется зависимое обновление двух отношений.

Если же выполнить декомпозицию отношения способом b):

	S21	(S#,	CITY)		S22	(CITY,	STATUS)
		S1	N1			N1
		S2	N2			N2
		S3	N3			N3

Тогда достаточно изменить кортеж в отношении S21: <S2, N3>; статус города N3 определен в отношении S22 независимо от того, какой поставщик в этом городе дислоцирован.