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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Декомпозиція 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_2R_1
  • R_1 ∩ R_2R_2

Приклад[ред.ред. код]

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

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

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

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


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

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

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

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


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

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