Соединение без потерь.

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

R=p_R1(R) ç><çp_R2(R) ç><ç… p_Rk(R),

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

Рассмотрим основные свойства отображения проекция-соединение.

Если r=(R1, R2, ..., Rk), обозначим через Mr отображение, которое определяется соотношением Mr(R)=p_R1(R) ç><çp_R2(R) ç><ç…p_Rk(R). Таким образом, условие соединения без потерь относительно F может быть выражено следующим образом: для всех R, удовлетворяющих F, R=Mr(R).

Для любой декомпозиции выполняются следующие условия:

а) R Í Mr(R);

б) если S=Mr(R), то p_Ri(S)=Ri;

в) Mr(Mr(R))=Mr(R).

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

Для проверки свойства соединения без потерь можно использовать следующий алгоритм.

Пусть заданы схема отношения R = ({А1, А2, ..., An}, F) и декомпозиция r=(R1, R2, ..., Rk), Ri=(Ui), i=1, 2, ..., k.

Строим таблицу с n столбцами и k строками, столбец j соответствует атрибуту Aj, а строка i – схеме отношения Ri. На пересечении строки i и столбца j поместим символ Aj, если AjÎUi. B противном случае поместим туда символ *.

Просматриваем каждую из зависимостей Х¾>Y. Рассматривая зависимость Х—>У, изменяем строки, которые совпадают по всем столбцам, соответствующим атрибутам из X. При обнаружении двух таких строк отождествляем их символы в столбцах, соответствующих атрибутам из Y. Если при этом один из символов в одной из строк равен Aj, а символ другой строки в этом же столбце равен *, то заменяем * на Aj. Повторяем просмотр зависимостей до тех пор пока: либо некоторая строка станет равной А1, А2, ..., Аn; либо больше изменений в таблице провести нельзя. В первом случае декомпозиция r обладает свойством соединения без потерь. Во втором – нет.

Примеры.

Пусть для схемы R=({А1, А2, А3, А4, А5}, {А1¾>А2; А2¾>A3; АЗ,А4¾>А5; А2¾>А4}) получена декомпозиция r = (Rl, R2, R3), где

R1=({А1, А2}), R2=({А2, АЗ, А4}), R3=({АЗ, А4, А5}).

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

1-я (начальная таблица):

2-я таблица:

3-я таблица:

В последней таблице первая строка представляет собой все Aj, следовательно, декомпозиция обладает свойством соединения без потерь.

Теперь пусть для схемы

R=({А1, А2, А3, А4, А5}, {A1¾>A2; A2¾>A3; A3,A5¾>A4}), получена декомпозиция r = (Rl, R2), где R1 = ({A1, A2}); R2 = ({A2, A3, A4, A5}). Построим следующие таблицы:

1-я таблица:

2-я таблица:

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

Справедливо следующее утверждение.

Если r=(R1(U1), R2(U2)) – декомпозиция R=(U, F), то r обладает свойством соединения без потерь относительно F тогда и только тогда, когда ((U1ÇU2)¾>U1\U2)ÎF⁺ или ((UlÇU2)—>U2\Ul)ÎF⁺.

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