Декомпозиція схем відносин

Декомпозицією схеми відношення R = (U, F) називається заміна її сукупністю ρ = {R₁, R₂,..., R_k), де Ri = (Ui), i = l, 2,..., k, такий, що U₁ ∪ U₂ ∪...∪ U_k = U. При цьому не вимагається, щоб Ui перетиналися. Ri будемо називати підсхемами відношення R.

З'єднання без втрат. Нехай задана схема відношення R = (U, F) та її декомпозиція ρ = (R₁, R₂,..., R_к). Кажуть, що ця декомпозиція володіє властивістю з'єднання без втрат відносно F, якщо кожне від носіння R для R, що задовольняє F, може бути представлено у вигляді

R= π _R1 (R)│ > < │ π _R2(R)│ > < │ …│ > < │ π _Rk(R)

тобто R є природним з'єднанням його проекцій на всі R_i. Ясно, що властивість з'єднання без втрат дуже бажано, оскільки в цьому випадку може бути відновлено початкове відношення.

Розглянемо основні властивості відображення проекція-з'єднання. Якщо ρ = (R₁, R₂,..., R_k), позначимо через Mρ відображення, яке визначається співвідношенням

Mρ (R) = π _R1 (R) │ > < │ π _R2 (R)│ > < │ …│ > < │ π _Rk(R)

Таким чином, умова з'єднання без втрат відносно F може бути виражена наступним чином: для всіх R, які задовольняють F, R = Mρ (R).

Для будь-якої декомпозиції виконуються наступні умови:

а) R ⊆ Mρ (R);

б) якщо S = Mρ (R), то π _i (S) =R_i;

в) Mρ (Mρ (R)) = Mρ (R).

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

Для перевірки властивості з'єднання без втрат можна використовувати наступний алгоритм.

Нехай задано схему відношення R = ({А₁, А₂,..., A_n}, F) і декомпозиція ρ = (R₁, R₂,..., R_k), R_i = (U_i), i = 1, 2,..., k.

Будуємо таблицю з n стовпців і k рядків, стовпець j відповідає атрибуту Aj, а рядок i – схемі відношення Ri. На перетині рядка i та стовпця j помістимо символ Aj, якщо Aj ∈ Ui. B іншому випадку помістимо туди символ *.

Переглядаємо кожну з залежностей Х → Y. Розглядаючи залежність Х → Y, змінюємо рядки, які збігаються за всіма стовпцями, що відповідає атрибутам з X. При виявленні двох таких рядків ототожнюємо їх символи в стовпцях, відповідних атрибутів з Y. Якщо при цьому один з символів в одній з рядків дорівнює Aj, а символ іншого рядка в цьому ж стовпці дорівнює *, то замінюємо * на Aj. Повторюємо перегляд залежностей до тих пір, поки: або деяка рядок стане рівною А₁, А₂,..., А_n, або більше змін у таблиці провести не можна.

У першому випадку декомпозиція ρ володіє властивістю з'єднання без втрат. У другому – немає.

ПPИКЛАДИ

Нехай для схеми R = ({А1, А2, А3, А4, А5}, {А1 → А2; А2 → A3; А3, А4 → А5; А2 → А4}) отримана декомпозиція ρ = (Rl, R2, R3), де

R1 = ({А1, А2}), R2 = ({А2, А3, А4}), R3 = ({А3, А4, А5}). Потрібно перевірити, чи має вона властивістю з'єднання без втрат.

Побудуємо наступні таблиці

1-ша (початкова таблиця)

2-га таблиця:

рядок являє собою всі Aj, отже, декомпозиція володіє властивістю з'єднання без втрат. Тепер нехай для схеми R = ({А1, А2, А3, А4, А5}, {A1 → A2; A2 → A3; A3, A5 → A4}) отримана декомпозиція ρ = (Rl, R2), де R1 = ({A1, A2}); R2 = ({A2, A3, A4, A5}). Побудуємо такі таблиці:

1 табл.

2 табл.

ДОП.ТАБЛ(стр.35)

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

Справедливе наступне твердження.

Якщо ρ = (R₁(U₁), R₂(U₂)) – декомпозиція R = (U, F), то ρ володіє властивістю з'єднання без втрат відносно F тоді і тільки тоді, коли ((U₁ ∩ U₂) → U₁ \ U₂) ∈ F⁺ або ((U₁ ∩ U₂) → U₂ \ U₁) ∈ F⁺.

Це твердження дає досить простий спосіб перевірки властивості з'єднання без втрат при декомпозиції на дві подсхемы.