Навігація
Головна
 
Головна arrow Інформатика arrow Бази даних
< Попередня   ЗМІСТ   Наступна >

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

Розглянемо властивості операцій реляційної алгебри [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-залежності. Для них використовуються дещо інші правила.

 
Якщо Ви помітили помилку в тексті позначте слово та натисніть Shift + Enter
< Попередня   ЗМІСТ   Наступна >
 
Дисципліни
Агропромисловість
Аудит та Бухоблік
Банківська справа
БЖД
Географія
Документознавство
Екологія
Економіка
Етика та Естетика
Журналістика
Інвестування
Інформатика
Історія
Культурологія
Література
Логіка
Логістика
Маркетинг
Медицина
Нерухомість
Менеджмент
Педагогіка
Політологія
Політекономія
Право
Природознавство
Психологія
Релігієзнавство
Риторика
Соціологія
Статистика
Техніка
Страхова справа
Товарознавство
Туризм
Філософія
Фінанси
Пошук