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

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

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

Критерій безутратної-з'єднувості

Нехай ${\displaystyle R}$ — схема, а ${\displaystyle F}$ — множина функціональних залежностей на ${\displaystyle R}$. Нехай ${\displaystyle R_{1}}$ і ${\displaystyle R_{2}}$ утворюють декомпозицію ${\displaystyle R}$.

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

• ${\displaystyle R_{1}}$ ∩ ${\displaystyle R_{2}}$ → ${\displaystyle R_{1}}$
• ${\displaystyle R_{1}}$ ∩ ${\displaystyle R_{2}}$ → ${\displaystyle R_{2}}$

Приклад

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

Міста

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

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

Міста1

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

Міста2

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

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

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

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

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

Міста1

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

Міста2

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

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

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