Проверка декомпозиции

Результат декомпозиции универсального отношения проверяют на свойство "соединение без потерь". Пусть универсальное отношение, имеющее схему R=(A₁, A₂, ...,A_n), разложено на k отношений со схемами (R₁, R₂, ... ,R_k), использующих множество F функциональных зависимостей. Алгоритм проверки на свойство "соединение без потерь" заключается в следующем.

Строится таблица с n столбцами и  k строками, причем j-й столбец сопоставляется j-му атрибуту A_j , а i-я строка i-й схеме отношения R_i . На пересечении i-й строки и j-го столбца записывается символ  a_j , если атрибут A_j входит в схему отношения R_i ; в противном случае записывается символ b_ij . После составления таблицы перебираем поочередно функциональные зависимости X -> Y из множества F . В таблице выделяем столбцы  с атрибутами из агрегата  X и проходим по строкам. В случае обнаружения одинаковых в пределах агрегата X строк преобразуем столбцы из агрегата Y по следующему правилу: если в столбцах из агрегата Y один из символов a_j , то и другие делаем равными a_j; если же ни один из символов не равен a_j ,  то другие символы делаем одинаковыми, а именно равными одному из b_ij .

Если после преобразований образуется хотя бы одна строка только из a_j , то свойство соединения без потерь присутствует.

Пример. Пусть исходное отношение R=(A, B, C, D, E) было разложено на пять отношений

R1=(A, D) , R2=(A, B) , R3=(B, E) , R4=(C, D, E) , R5=(A, E)

и было создано множество функциональных зависимостей F:

A -> C ,  B -> C ,  C -> D ,  (D, E) -> C ,  (C, E) -> A.

Создаем исходную таблицу по схемам R:

Обрабатываем зависимости A -> C и B -> C:

Обрабатываем зависимости C -> D и (D, E) -> C:

Обрабатываем зависимость (C, E) -> A:

Строка 3 состоит только из символов a_j, а это означает, что  свойство соединения без потерь имеет место и, следовательно,  декомпозиция отношения была выполнена без ошибок.