Методические указания По выполнению курсовой работы Для обучающихся по направлению

Декомпозиция с соединением без потерь
При проектировании базы данных может возникнуть ситуация, когда некоторое отношение должно быть разбито на несколько других отношений. Такой процесс разбиения называется декомпозицией отношения. При этом, поскольку отношение характеризуется схемой и имеет некоторую реализацию, декомпозиция отношения затрагивает и схему отношения, и его реализацию.
Определение.Декомпозицией схемы отношения R(A_p А₂, ..., А ) называется замена ее совокупностью подмножеств {R;} схемы R (подсхем) таких, что R, и R₂ и ... и R_k = R. При этом необязательно, чтобы Rj были непересекающимися.
Декомпозиция реализации отношения определяется как совокупность проекций отношения на подсхемы, полученные при декомпозиции схемы отношения. Так, если есть некоторая реализация отношения r(R), то, используя декомпозицию, получим
Г; = 7i_R.(r), i = 1,2, ..., k.
Важно, чтобы декомпозиция была обратимой, т.е. выполнялась без потери информации: по проекциям отношения г можно было бы восстановить исходную реализацию отношения г. Очевидно, что восстановление г из гj реализуется с помощью операции естественного соединения:
s = Г, XI г₂ XI ... xt r_R.
Где гарантия, что s s г? Если такой гарантии нет, получив из г s, мы не будем знать, достоверна информация или нет.
Рассмотрим пример. Пусть отношение со схемой S(sid, status, city) имеет следующую реализацию:
S (sld, status, city)

51 30 N1 52 30 N2 Так как декомпозиция представляет собой проекцию отношения, рассмотрим следующие способы декомпозиции: ^а) SI (sld, status) S2 (sld, city)
SI 30		SI	N1
S2 30		S2	N2
Делаем операцию естественного соединения — восстановление
исходного отношения:
si XI s2 = S (sld,	status,	city)
SI	30	N1
S2	30	N2
Получили отношение, совпадающее с исходным;
б) SI (sld, status)	S2	(status,	city)
SI 30		30	N1
S2 30		30	N2
Восстанавливаем:
si XJ s2 = S (sld,	status,	city)
SI	30	N1
SI	30	N2
S2	30	N1
S2	30	N1

В результате получили лишние строки, отсутствовавшие в исходном отношении.
Таким образом, возникает вопрос: как разбивать исходное отношение, чтобы не потерять информацию? Эта проблема получила название декомпозиции с соединением без потери информации. Вопрос о том, происходит ли потеря информации, тесно связан с функциональными зависимостями.
Определение. Пусть R — схема отношения, в результате декомпозиции которой получены схемы R_p R₂, ..., R_k, и F — множество функциональных зависимостей для R. Говорят, что эта декомпозиция обладает свойством соединения без потерь относительно F, если каждая реализация r(R), удовлетворяющая F, может быть представлена в виде:
r=7t_R1(r) X Tl_R2(r) М ... М 7l_Rk(r).
Теорема. Пусть R(A, В, С) — схема отношения с атрибутами (подмножествами атрибутов) А, В и С. Если данная схема отношения удовлетворяет функциональной зависимости А -Э В, то осуществляется декомпозиция без потери на {R_p R₂}, где R, = {А, В} и R₂ = {А, С}.
Вернемся к приведенному выше примеру: S(sld, status, city}. Так как sld — первичный ключ отношения, то sld -Э city. Отсюда декомпозиция без потери осуществляется на подсхемы S1 (sld, city) и S2(sld, status). Функциональные зависимости status -> sld или status -Э city отсутствуют, поэтому второй пример декомпозиции не сохраняет исходное отношение.
Но здесь может возникнуть еще одна проблема. Предположим, что в условиях данной задачи поставщик дислоцирован в конкретном городе, а каждый город имеет определенный статус. Следовательно, для приведенной схемы отношения имеют место следующие функциональные зависимости:

• 
  • sld -> city;
  
• 
  • city -> status.
  

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

• 
  а) относительно sld -Э city: SI 1 (sld, city) и S12(sld, status);
  
• 
  б) относительно city -> status: S21 (city, sld) (или S21 (sld, city) — порядок задания имен атрибутов никакого значения не имеет) и S22(city, status)
  

Какой из этих двух способов лучше?
Чтобы ответить на этот вопрос, введем еще одно определение.
Определение. Проекцией множества функциональных зависимостей F на множество атрибутов Z (n_z (F)) называется множество зависимостей X Y в F⁺, таких, что XY с Z.
Рассмотрим все тот же пример.
Для исходного отношения определено следующее множество функциональных зависимостей:
F = {sld -> city, city -> status}.
Из них по правилам вывода можно вывести следующие зависимости:

• 
  • sld -> status — правило транзитивности;
  
• 
  • sld -> (city, status) — правило объединения.
  

Отсюда,
F⁺ = {sld -> city, city -> status, sld -> status, sld -> (city, status)}.
Для способа а) декомпозиции определены следующие функциональные зависимости:

• 
  • sld -> status — из схемы отношения SI 1 (sld, status);
  
• 
  • sld city — из схемы отношения S12(sld, city).
  

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

• 
  • sld city — из схемы отношения S21 (sld, city);
  
• 
  • city -> status — из схемы отношения S22(city, status).
  

Определение. Декомпозиция сохраняет множество функциональных зависимостей F, если из объединения всех зависимостей, принадлежащих 7t_Rj (F), для i = 1, 2, ..., к, логически следуют все зависимости, принадлежащие F.
Из функциональных зависимостей, сохранившихся при способе декомпозиции а), нельзя логически вывести зависимость city -> status, т.е. данная декомпозиция не сохраняет функциональные зависимости.
Для способа декомпозиции б) все функциональные зависимости из F сохранены.
Что дает сохранение функциональных зависимостей? Рассмотрим следующий пример.
Пусть дана следующая реализация отношения:

(sld,	status,	city)
S1	30	N1
S2	30	N2
S3	40	N3

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

Sil (sld,	city)	Sl2 (sld,	Status)
S1	NI	Sl	30
S2	N2	S2	30
S3	N3	S3	40

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

S21 (sld,	city)	S22 (city,	Status)
Sl	N1	N1	30
S2	N2	N2	30
S3	N3	N3	40

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