Реляційна алгебра і реляційне числення

3.1. РЕЛЯЦІЙНА АЛГЕБРА

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

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

До основних операцій відносяться наступні: об'єднання відносин; різниця відносин; перетин відносин; декартів добуток відносин; проекція; вибірка; поділ відносин; θ -з'єднання відносин; природне з'єднання; зовнішнє з'єднання відносин; полуз`єднаня відносин.

Розглянемо ці операції докладніше.

Об'єднання. Ця операція майже повністю відповідає операції об'єднання в теорії множин. Об'єднання відношень R і S, що позначається як R ∪ S, являє собою безліч всіх таких кортежів, кожен з яких належить R або S, або обом відразу. Операція об'єднання застосовується тільки до сумісних відносин однією арності, тому всі кортежі в об'єднанні мають однакове число компонентів.

Різниця. Різницею відносин R і S, що позначається R \ S, називається безліч всіх кортежів, що належать R, але не належать S. Тут також вимагається, щоб R і S мали одну і ту ж арність і були сумісні.

Перетин. R ∩ S позначає множину всіх кортежів, що належать одночасно R і S. R і S повинні мати однакову арність і бути сумісні. Очевидно, що R ∩ S = R \ R \ S) = S (S R).

Приклад

Нехай відношення R і S представлені наступними таблицями, тоді результати виконання операцій «об'єднання», «різниця» і «перетин» над цими відносинами можна також представити у вигляді таблиць.

Декартів добуток. Нехай R і S – відносини арності r і s відповідно. Тоді декартовым твором R × S відносин R і S називається безліч всіх кортежів довжини r + s таких, що перші r компонент утворюють кортежі, що належать R, а останні s компонент – кортежі, що належать S.

ПРИКЛАД

Нехай відношення R и S представлені наступними таблицями, тоді результат виконання цієї операції над цими відношеннями можливо також представити в вигляді таблиці.

S=

R=

R x S=

Якщо імена стовпців у відношеннях-сомножниках збігаються, то їх позначають іменами відносин, наприклад замість А, B, С, D, Е, F можна писати R.A, R.B, R.C, S.D, S.E, S.F

Проекція. Сутність цієї операції полягає в тому, що у вихідному відношенні видаляються деякі компоненти (атрибути) і (або) переставляються ті, що залишилися. Нехай R – відношення арності r. Позначимо π _{i1, i2, …., im}(R), де i_j- цілі числа в діапазоні від 1 до r, проекцію R на компоненти i_1, i_{2, ….}i_m, тобто безліч таких кортежів a довжини m, що існує деякий належащий R кортеж b₁, b₂,..., b_r, що задовольняє умові a₁=a₂.

Наприклад, для побудови π _{3, 1}(R) потрібно з кожного кортежу, що належить R, сформувати кортеж довжини 2 з третього і першого його компонентів у зазначеному порядку, тобто виписати 3-й, потім 1-ї компоненти. При цьому з кожної групи однакових кортежів у виводі щодо залишається тільки один кортеж (відношення – це множина кортежів, і воно не може містити однакових, тобто cпівпадати за всіма компонентами кортежів).

Замість номерів компонент (стовпців) часто використовують атрибути.

Вибірка. Нехай F – формула, утворена:

1) операндами, які є константами або номерами компоненту (атрибутами);

2) операціями порівняння: <, =, >, ≤, ≥;

3) логічними операціями Λ (І-кон'юнкція), \/ (ЧИ – диз'юнкція), ⎤ (НЕМАЄ – заперечення).

У цьому випадку σ _f(R) є множина всіх таких кортежів t, належать R, що при підстановці i-го компонента замість всіх входжень i (або відповідного атрибута) у формулу F вона стане істинною.

Наприклад, σ _{2> 3} позначає безліч кортежів, що належать R, другий компонент яких більше третього.

Зауважимо, що константи у формулах повинні бути укладені в лапки, це дозволить відрізнити їх від номерів або імен стовпців.

ПРИКЛАД

Нехай відношення R і S представлені наступними таблицями, тоді результати виконання операцій проекції і вибірки над цими відношеннями можливо також представити у вигляді таблиць.

ДОП.ТАБЛ(СТ.19)!!!!!!!!

Ділення. Нехай R і S – відносини арності r і s відповідно, причому r > s і S ≠ ∅. Припустимо, що R визначено на множині атрибутів A, а S на множині атрибутів B і B ⊆ A. R ÷ S (приватне) є безліч кортежів t довжини r – s, таких, що для всіх кортежів u ∈ S, кортеж tu належить R (тут tu означає кортеж, отриманий приписуванням праворуч до кортежу t компонентів кортежу u).

ПРИКЛАД

Нехай відношення R і S представлені наступними таблицями, тоді результат виконання операції ділення над цими відносинами можна також представити у вигляді таблиці.

R ÷ S =

R =

S =

θ -з'єднання. θ -з'єднання відношень R і S за стовпцями i і j, записуване R| > < |iθ jS, де θ – операція порівняння (=, < тощо), є коротка запис виразу: σ iθ j(R × S). Таким чином, θ -з'єднання R і S являє собою безліч всіх таких кортежів декартовом творі R і S, що i-й атрибут знаходиться у відношенні R θ j-м атрибутом відносини S. Якщо θ є операцією «=», то ця операція називається еквіз’єднанням.

Природне з'єднання. Ця операція відіграє фундаментальну роль в теорії проектування реляційних баз даних. Природне з'єднання (позначається R ⎢ > < ⎢ S) застосовується лише тоді, коли відношення мають один або кілька загальних атрибутів.

Обчислити R ⎢ > < ⎢ S можна наступним чином:

1) обчислити R × S;

2) для кожного атрибута А, який іменує певний стовпець R і будь-який стовпець S, виберемо тільки ті кортежі з R × S, у яких збігаються значення в стовпцях R. A і S. A;

3) для кожного зазначеного вище атрибута А видалимо стовпець R. A.

Формально, якщо A1, A2,..., Ak є загальними атрибутами для R і S, то

R ⎢ > < ⎢ S =π _{i1, i2, …, im} (σ _{R.A=S.A1^…^R.Ak=S.Ak})(R x S),

де i₁, i₂,..., i_m – впорядкований список всіх атрибутів R × S, за винятком атрибутів S. A₁, S. A₂,..., S. A_k.

Розглянемо ряд прикладів, що реалізують вищеописані операції.

Приклади

• Нехай відношення R і S представлені наступними таблицями, тоді результат виконання операції θ -з'єднання над цими відносинами можна також представити у вигляді таблиці.

ДОП.ПРИКЛАДИ і ТАБЛ(СТР.21)

Зовнішнє з'єднання. Лівим зовнішнім з'єднанням R ⊃ < ⎪ S відносин R і S називається відношення, що містить всі кортежі відношення R⎪ > < ⎪ S, а також кортежі R, не мають співпадаючих значень у загальних стовпцях з відношенням S. Для позначення відсутніх значень у другому щодо використовується визначник NULL.

Аналогічно вводиться операція правого зовнішнього з'єднання R⎪ > ⊂ S. Існує також повне зовнішнє з'єднання R ⊃ ⊂ S, в остаточному щодо якого містяться всі кортежі з обох відношення і в якому для позначення незбіжних значень кортежів використовуються визначники NULL.

Напівз’єднання. Цю операцію можна визначити з допомогою операцій «проекція» і «θ -з'єднання». А саме R⎪ > iθ jS = π u(R⎪ > < ⎪ iθ jS). Тут u – це набір всіх атрибутів відношення R. Аналогічно визначаються напівз’єднання за еквівалентності (коли θ є рівність) і природне напівз’єднання R⎪ > S.

Приклади

• Нехай відношення R і S представлені наступними таблицями, тоді результати виконання операцій лівого зовнішнього, правого зовнішнього і повного зовнішнього з'єднання над цими відношеннями можна також представити у вигляді таблиць.

ДОП.ПРИКЛАДИ І ТАБЛ(СТР.22, 23)