Декомпозиція без втрат

Шаблон:Без джерелДекомпозиція D = {R1, R2,..., Rm} схеми R є безутратно-з'єднуваною декомпозицією (декомпозицією без втрат) стосовно множини функціональних залежностей F на R, якщо для будь-якого відношення r зі схемою R, яке відповідає F, вірно наступне, $*(\pi R_1(r),...,\pi R_m(r))=r$, де $*$ це природне з’єднання всіх відношень в D.

Слово безутратна вживається у зв'язку з можливою втратою даних, в нашому випадку ми не втрачаємо жодного кортежу.

Критерій безутратної-з'єднуваної декомпозиції

Нехай $R$ — схема, а $F$ — множина функціональних залежностей на $R$. Нехай $R_1$ і $R_2$ утворюють декомпозицію $R$.

Декомпозиція буде безутратно-з'єднуваною декомпозицією $R$, якщо хоча б одна з наступних функціональних залежностей знаходиться в $F$⁺ (замиканні $F$):

• $R_1$ ∩ $R_2$ → $R_1$
• $R_1$ ∩ $R_2$ → $R_2$

Приклад

Розглянемо наступне відношення:

Міста

Назва	Держава	Столиця
Київ	Русь	Так
Новгород-Сіверський	Русь	Ні
Константинополь	Візантія	Так

Декомпозиція {Назва}, {Держава, Столиця} має вигляд:

Міста1

Назва
Київ
Новгород-Сіверський
Константинополь

Міста2

Держава	Столиця
Русь	Так
Русь	Ні
Візантія	Так

Результат з'єднання цих відношень:

Міста' = Міста1 NATURAL JOIN Міста2

Назва	Держава	Так
Київ	Русь	Так
Київ	Русь	Ні
Київ	Візантія	Так
Новгород-Сіверський	Русь	Так
Новгород-Сіверський	Русь	Ні
Новгород-Сіверський	Візантія	Так
Константинополь	Русь	Так
Константинополь	Русь	Ні
Константинополь	Візантія	Так

Вочевидь, що Міста' не співпідає з Міста, тобто така декомпозиція не є безутратно-з'єднуваною. Розглянемо варіант {Назва, Держава}, {Назва, Столиця}:

Міста 1

Назва	Держава
Київ	Русь
Новгород-Сіверський	Русь
Константинополь	Візантія

Міста 2

Назва	Столиця
Київ	Так
Новгород-Сіверський	Ні
Константинополь	Так

Ця декомпозиція є безутратно-з'єднуваною.

Не всі декомпозиції приступні для безутратно-з'єднуваної декомпозиції.