Властивості реляційної алгебри

Розглянемо властивості операцій реляційної алгебри [4].

I. Комутативність:

Унарні операції:

  • 1);
  • 2), есліА1 = А2;
  • 3), якщо Аttr (F1) А1;
  • 4), якщо Attr (F1) A1.

Бінарні операції:

  • 5) JF (R, S) → JF (S, R);
  • 6) U (R, S) → U (S, R);
  • 7) CP (R, S) → CP (S, R).

II. Асоціативність бінарних операцій:

  • 1) U (U (R, S), Т) → U (R, U (S, Т));
  • 2) CP (CP (R, S), Т) → CP (R, CP (S, Т));
  • 3)

III. Ідемпотентність унарних операцій:

  • 1), якщо А = А1, А Í А2;
  • 2), якщо F = F1 Ç F2.

IV. Дистрибутивність бінарних операцій між бінарними:

  • 1) SF (U (R, S)) → U (Sf (R), Sf (S));
  • 2) Sf (DF (R, S)) → DF (Sf (R), SF (S));
  • 3) Sf (CP (R, S)) → CP (Sf (R), S), якщо Attr (F) Í Attr (S);
  • 4) Sf1 (Jf (R, S)) → Jf (Sf (R), SF (S)), якщо Attr (F) Í Attr (S);
  • 5) Pa (U (R, S)) → U (Pa (R), Pa (S));
  • 6) Pa (CP (R, S)) → CP (Pa (R), Pa (S)).

V. Факторизація унарних операцій:

  • 1) U (Sf (R), Sf (S)) → Sf (U (R, S));
  • 2) CP (Sfr (R), Sfs (S)) → Sf (CP (R, S)), де F = FR Ç FS;
  • 3) JF (SF (R), SF (S)) → Sf (Jf (R, S)), де F = FR Ç FS;
  • 4) DF (Sfr (R), Sr (S)) → Sfr (DF (R, S)), де FR → FS;
  • 5) U (Pa (R), Pa (S)) → Pa (U (R, S));
  • 6) CP (Par (R), Pas (S)) → Pa (CP (R, S)), де A = AR u AS.

Реляційна алгебра в процедурі використання БД

Перераховані правила використовуються насамперед при формуванні та оптимізації запитів.

Опис побудови БД

Реляційна алгебра більше призначена для опису процедур запитів (вибірки) та оновлення. Справа в тому, що РА (так само як і РІ, як буде показано пізніше) не зачіпають питання забезпечення цілісності при створенні та відновленні БД. Іншими словами, вони непридатні для того, щоб СУБД могла автоматично перевірити істинність або хибність наслідків із заданих в схемі БД [9] обмежень цілісності.

Знадобився апарат з простіший інтерпретацією та алгоритмічної вирішуваною проблеми виводимості (або логічних наслідків) розумної комбінаторної складності.

Це вдалося зробити за допомогою функціонального підходу (формул однозначних {1: 1, 1: М} F-залежностей і багатозначних {1: М і насамперед - М: М} MV-залежностей) і, як наслідок, шляхом виконання процедури нормалізації.

F-залежності забезпечують перехід до першої (ΙΗΦ), другий (2НФ), третьої (ЗНФ) нормальним формам представлення даних. MV-залежності дозволяють будувати четверту (4НФ) і п'яту (5НФ) нормальні форми.

Докази положень для F- і MV-залежностей базуються на реляційній алгебрі, у зв'язку з чим їх іноді відносять до апарату реляційної алгебри.

Функціональні (однозначні) F-залежності

Функціональні залежності є узагальненням поняття ключа: значення кортежу на одному множині X атрибутів визначають значення на іншій безлічі Y атрибутів; X, Y Î R; R - схема відносини R.

Нехай є r (R) і X, Y Î R.

Ставлення задовольняє функціональної залежності (ФЗ) X → Y, якщо π Y (σх_х (R)) має не більше одного кортежу для будь-якого (V) x Î X. Перевірка проводиться так (рис. 4.1): якщо кортежі t1 (X) = t2 (X), то має задовольнятися умова t1 (Y) = t2 (Y).

Такі однозначні залежності називаються F-залежностями. Безліч F-залежностей також позначається F. Інакше сказане записується у вигляді: F Ì X → Y тягне X → Y або говорять про аксіому виводу.

F-залежність

Рис. 4.1. F-залежність

Аксіома виведення (правило): якщо відношення задовольняє деяким F-залежностям, то воно повинно задовольняти і іншим F-залежностей.

Приклад 4.1. Нехай маємо розклад занять "Розклад" (День, Час, Аудиторія, Викладач, Група). Введено дві ФЗ:

f1: День Час Аудиторія → Викладач Група,

f2: День Час Викладач → Аудиторія Група.

Далі використовуємо наступні ФЗ:

f1: Студент → Курсова робота,

f2: Студент → Викладач,

f3: Викладач → Кафедра,

f4: Кафедра → Факультет,

f5: Студент → Факультет.

Нехай R = {a, ..., А}; X, Y, Z, W Î R. Для будь-якого r (R) справедливі наступні аксіоми виводу.

F1. Рефлексивність: X = X. Проекція від селекції πX (σX = х (r)) має не більше одного кортежу. Наприклад, Студент → Студент.

F2. Транзитивність: якщо X → Υ і Υ → Ζ, то X → Ζ. Якщо t1 (X) = t2 (X), то t1 (Y) = t2 (Y) за визначенням. Якщо t, (Y) = t2 (Y), то і t, (Z) = t2 (Z). Отже, якщо t1 (X) = t2 (X), то t1 (Z) = t2 (Z).

Інакше кажучи, з Студент-4 Викладач і Викладач -4 Кафедра слід Студент → Кафедра.

F3. Поповнення: якщо X → Y, то XZ → Y.

З X → Y слід (), що πY (σx = x (R)) має не більше одного кортежу для "x Î X. Якщо Z Î R, то σ XZ = xz (R) Í σ X = х (R ) і π Y (σXZ = xz (R)) Í π Y (σX = x (R)) має не більше одного кортежу.

Отже, якщо Студент → Викладач, то Студент Кафедра → Викладач.

Або з А → В слід АС → В і AD → В, АВС → В, ABD → В, ACD → В, ABCD → В.

F4. Псевдотранзітівность: якщо X → Y, YZ → W, то XZ → W.

Якщо t1 (X) = t2 (X), то t1 (Y) - t2 (Y) за визначенням. Якщо t1 (YZ) = t2 (YZ), то і t1 (W) = t2 (W). Отже, з t1 (XZ) = t2 (XZ) маємо t1 (X) = t2 (X) і t1 (Z) = t2 (Z), t1 (Y) = t2 (Y), t1 (YZ) = t2 ( YZ) і t1 (W) = t2 (W). Інакше, якщо Студент → Викладач, Викладач Кафедра → Факультет, то Студент Кафедра → Факультет або з A → В, ВС → D слід АС → D.

F5. Адитивність: якщо X → Y і X → Z, то X → YZ.

За визначенням pY (sx = x (R)) і pz (sx = z (R)) мають не більше одного кортежу. Якщо sYZ (sX = x (R)) має більше одного кортежу, то хоча б одна залежність має більше одного кортежу.

Отже, Студент → Викладач, Студент → Кафедра, то Студент Викладач → Кафедра або з А → В, А → С слід А → Нд

F6. Проективної (певною мірою обратна адитивності): якщо X → ΥΖ, то X → Υ і X → Ζ.

За визначенням pyZ (σX = x (R)) і pz (σX = z (R)) мають не більше одного кортежу. Однак pY (R))) = pY (σX = x (R)) і pY (σx = x (R)) теж має більше одного кортежу, т. E. X → Y.

Отже, Студент → Викладач Кафедра, то Студент → Викладач і Студент → Кафедра або якщо А → Нд, то А → С і А → В.

Система F1-F6 є повною: з її допомогою можна отримати (шляхом багаторазового застосування) будь-яку F-залежність для безлічі F. Аксіоми F2, F5, F6 виводяться з F1, F3, F4. Покажемо лише два висновки.

Транзитивність F2 - окремий випадок аксіоми F4. Аксіома F5: якщо X → Y, X → Z, то з F1 слід YZ → YZ, з F4 слід XZ → YZ, з F4 слід X → YZ.

Аксіоми F1, F3, F4 іноді називають аксіомами Армстронга.

Замиканням множини F називається безліч функцій F +, що містить всі ті залежності, які можуть бути отримані застосуванням до F аксіом Армстронга.

Замикання використовується для визначення Бієкція та ліквідації надмірності безлічі функціональних залежностей, що можна сформулювати у вигляді леми.

Лемма. Функціональна залежність X → Y виведена з аксіом Армстронга, якщо Y з Х +.

Доказ наводиться в [4].

Обчислення F + досить складна процедура. Наприклад, якщо F = (Аt → Вt, ..., Аn → Вп), то F + включає А → Y, де Y - підмножини множин {В1, ..., Bn} і їх кількість становить 2n.

Більш того, якщо F-безліч F-залежностей над R і X Í R, то в F + існує залежність X → Y така, що підмножина Y максимально, т. E. Z Ì Y для будь-якої іншої F-залежності X → Z в F +.

Якщо F = {А → D, АВ → DE, РЄ → G, Е → Н}, то можна показати, що (АВ) + = ABCDEH.

Для F = {АВ → С, АЕ → G, нд → D, D → Е, В → AЕ, EG → До} (АВ) + = ABCDEGK.

Складність алгоритму в часі залежить від розміру вхідного безлічі F-залежностей. Отже, треба прагнути до мінімізації F-множини. Це сприяє узгодженості та цілісності БД (менше перевірок при модифікації).

Дійсно, безліч F = {А → В, В → С, А → С, АВ → С, А → Нд} виводиться з безлічі G = {А → В, В → С}. Кажуть, що безліч G покриває безліч F (G еквівалентно F або G Î F).

На шляху мінімізації виникає дві проблеми: ненадмірність; усунення стороннього атрибута (редукування).

Безліч F-залежностей F називається неізбиточним, якщо немає F 'з F такого, що F' º F. У неізбиточное безлічі можуть бути сторонні атрибути, які можуть бути видалені (безліч може бути зредуковано).

Нехай є безліч F-залежностей F = {Xi → Yi, i = 1, n}. Безліч атрибутів Zi Ì Υi називається стороннім в Xi, якщо (ΧiΖi) → ji. може бути отримано в замиканні F + i.

Безліч F-залежностей F називається канонічним, якщо будь F-залежність з F має вигляд X → A, a F - зредуковано і неізбиточное.

Безліч F-залежностей F мінімально, якщо вона містить не більше F-залежностей, ніж будь-яке еквівалентне безліч F-залежностей.

Теорія F-залежностей використовується при нормалізації (1НФ - ЗНФ), проте, крім F-залежностей, можуть існувати MV-залежності. Для них використовуються дещо інші правила.

 
< Попер   ЗМІСТ   Наст >