Основы проектирования реляционных баз данных


                


Декомпозиция схем отношений, свойства соединения без потерь и сохранения ФЗ


Одной из целей проектирования реляционной базы данных является построение декомпозиции (разбиения) универсального отношения на совокупность отношений, удовлетворяющих требованиям нормальных форм.

Введем определение декомпозиции схемы отношения.

Определение 1. Декомпозицией схемы отношений

R(A_1, A_2, \dots, A_n)
называется замена ее совокупностью
{R_1, R_2, \dots, R_k}
подмножества R, таких, что
R = R_1 \cup R_2 \cup \dots R_k
.

Прежде чем перейти к изучению метода декомпозиции схем отношений, рассмотрим проблему соединения отношений при разбиении универсального отношения. Когда мы заменяем исходное отношение на два других взаимосвязанных отношения, правомерно предположить, что эти отношения будут представлять собой проекции исходного отношения на соответствующие атрибуты. Единственный способ выяснить, содержат ли полученные проекции ту же информацию, что и исходное отношение, - восстановить ее, выполнив естественное соединение полученных проекций. Если отношение, полученное в результате выполнения соединения, не будет совпадать с исходным отношением, то невозможно сказать, какое из них является первоначальным отношением для данной схемы. Таким образом, проблема заключается в том, что при соединении можно потерять существующие или приобрести ранее не существовавшие ложные кортежи. Рассмотрим пример декомпозиции с потерей информации.

Пример. Декомпозиция с потерей информации

Атрибуты А и В не зависят функционально от атрибута С.


Говорят, что декомпозиция

d = {R_1, R_2, \dots, R_k}
схемы отношения r обладает свойством соединения без потерь относительно множества ФЗ D, если каждое отношение R, удовлетворяющее D, может быть представлено в виде:

 R = \pi_R1 (R) >< \pi_R2 (R) >< \dots >< \pi_Rk (R) = m_d (R).

Пусть

R_i = \pi_Ri (R)
. Тогда для отображений проекции-соединения справедливы следующие свойства:

 R \subseteq m_d (R); \text{ если }s = m_d (R), \text{ то } R_i = \pi_Ri (R); m_d (m_d(R)) = m_d(R).

Эти свойства следуют из определения естественного соединения. Первое свойство используется при проверке, обладает ли декомпозиция свойством соединения без потерь относительно некоторого множества ФЗ.

Рассмотрим алгоритм проверки свойства соединения без потерь.

Алгоритм. Проверка декомпозиции на свойство соединения без потерь

input: схема отношения R(A1, A2, ..., Ak), множество ФЗ F, декомпозиция d={R1, R2, ..., Rk}.


Содержание  Назад  Вперед