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

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

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

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

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

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

  •   
  •   

Приклад

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

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

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

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

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

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

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

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

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

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.