Декомпозиция с соединением без потерь

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

Определение

Декомпозицией схемы отношения R(A₁, A₂, …, A_n) называется замена ее совокупностью подмножеств {R_i} схемы R таких, что R₁ È R₂ È … È R_k = R. При этом не обязательно, чтобы R_i были не пересекающимися.

Вывод: декомпозиция, по сути, представляет собой совокупность проекций отношения. Так, если есть некоторая реализация отношения r(R), то, используя декомпозицию, получим:

r_i = p_Ri(r), i = 1, 2, …, k.

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

s = r₁ r₂ … r_k

Где гарантия, что s º r? Если такой гарантии нет, получив из r_i s, мы не будем знать, достоверна информация или нет.

Рассмотрим пример. Пусть отношение со схемой S(S#, STATUS, CITY) имеет следующую реализацию:

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

Так как декомпозиция представляет собой проекцию отношения, рассмотрим следующие способы декомпозиции:

a)	S1	(S#,	STATUS)		S2	(S#,	CITY)
		S1				S1	N1
		S2				S2	N2

Делаем операцию естественного соединения – восстановление исходного отношения:

s1 s2 = S	(S#,	STATUS,	CITY)
	S1		N1
	S2		N2

Получили отношение, совпадающее с исходным.

b)	S1	(S#,	STATUS)		S2	(STATUS,	CITY)
		S1					N1
		S2					N2

Восстанавливаем:

s1 s2 = S	(S#,	STATUS,	CITY)
	S1		N1
	S1		N2
	S2		N1
	S2		N1

В результате получили лишние строки, отсутствовавшие в исходном отношении.

Таким образом, возникает вопрос: как разбивать исходное отношение, чтобы не потерять информацию? Эта проблема получила название декомпозиции с соединением без потери информации. Вопрос о том, происходит ли потеря информации, тесно связан с функциональными зависимостями.

Определение

Пусть R – схема отношения, в результате декомпозиции которой получены схемы R1, R2, …, Rk, и F – множество функциональных зависимостей для R. Говорят, что эта декомпозиция обладает свойством соединения без потерь относительно F, если каждая реализация r(R), удовлетворяющая F, может быть представлена в виде:

r = p_R1(r) p_R2(r) … p_Rk(r)

Теорема

Пусть 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).

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

S# à CITY

CITY à STATUS

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

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

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

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

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

Проекцией множества функциональных зависимостей F на множество атрибутов Z (p_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, если из объединения всех зависимостей, принадлежащих p_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 независимо от того, какой поставщик в этом городе дислоцирован.