Алгебра реляційних операцій

Тема 5.1. Реляційна алгебра.

1. Основи реляційної алгебри

2. Алгебра реляційних операцій

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

Деяка алгебра, взагалі говорячи, складається з набору операторів, що застосовуються до атомарних операндів. Наприклад, в алгебрі арифметики атомарні операнди представляють собою змінні виду Х і константи, а операторами слугують звичайні арифметичні оператори складання, різниці, множення і ділення. Люба алгебра дозволяє створювати вирази шляхом застосування операторів до операндів або до виразів. Для групування операторів і операндів застосовують круглі дужки. Арифметичний вираз, наприклад, може мати наступний вигляд (x+y)*z.

Реляційна алгебра – це різновид алгебри. В ній підтримуються наступні види атомарних операндів:

1) змінні – представляють відношення;

2) константи – представляють результуючі відношення.

Але з метою підвищення ефективності обробки запитів було прийняте рішення розглядати відношення не як множини, а як мультимножини. Іншими словами, дозволяється присутність кортежів-дублікатів.

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

Реляційна алгебра була розроблена Е.Ф.Коддом у вигляді сукупності операторів, що виконуються над множинами кортежів (тобто відношеннями) і що забезпечують можливість опису типових запитів стосовно вмісту відношень. Спочатку сукупність операторів включала п’ять операцій над множинами: об’єднання, різниця, декартовий добуток, вибір і проекцію. Потім до них були додані реляційні операції над мультимножинами, операції з’єднання (join), сортування, агрегування і групування, операції для опису обмежень.

Операції реляційної алгебри можуть бути поділені на такі класи:

Звичайні операції над множинами: об’єднання (union), пересічення (intersection), різниця (difference), які застосовуються до відношень.
Операції видалення частин відношення: операція вибору (selection) призводить до відкидання деяких кортежів (рядків), а операція проекції (projection) – до усунення деяких атрибутів (стовпців).
Операції сполучення кортежів двох відношень: наприклад, операція декартового добутку дозволяє сполучати у межах кортежів результуючого відношення усі можливі комбінації кортежів двох вихідних відношень, а різні різновиди операції з’єднання (join) застосовуються до вибіркового злиття кортежів.
Операція перейменування (renaming) атрибутів або відношення цілком.

Алгебра реляційних операцій

Операція об’єднання – (рис.5.1).

R, S – відношення, які повинні задовольняти вимогам:

мати схеми з однаковими наборами атрибутів, типи (домени) яких повинні попарно співпадати;
атрибути (стовпці) повинні слідувати в однаковому порядку.
назви атрибутів повинні співпадати (якщо не співпадають, то перейменувати).

title	year	length	filmtype	studioName	starName
Star Wаrs			Color	Fox	Carrie Fisher
Wayne’s World			Color	Paramount	Mike Meyers

Відношення R

title	year	length	filmtype	studioName	starName
Star Wаrs			Color	Fox	Carrie Fisher
Mighty Ducks			Color	Disney	Emilio Estevez
Wayne’s World			Color	Paramount	Mike Meyers

Відношення S

title	year	length	filmtype	studioName	starName
Star Wаrs			Color	Fox	Carrie Fisher
Mighty Ducks			Color	Disney	Emilio Estevez
Wayne’s World			Color	Paramount	Mike Meyers

Рис.5.1. Об’єднання відношень R і S

Відмітимо, що два однакові кортежі, що відповідають актрисі Керрі Фішер замінені одним. Аналогічна заміна у результуючому відношенні проведена і для кортежів актора Майка Мейерс

Операція пересічення – R ∩ S. Результуюче відношення приведене на рис.5.2

title	year	length	filmtype	studioName	starName
Star Wаrs			Color	Fox	Carrie Fisher
Wayne’s World			Color	Paramount	Mike Meyers

Рис. 5.2. Пересічення відношень R і S

Операція різниця відношень – S-R. Результуюче відношення приведене на рис.5.3.

title	year	length	filmtype	studioName	starName
Mighty Ducks			Color	Disney	Emilio Estevez

Рис. 5.3. Різниця відношень S і R

Оператор проекції

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

title	year	length	InColor	studioName	producerC#
Star Wаrs			true	Fox
Mighty Ducks			true	Disney
Wayne’s World			true	Paramount

Екземпляр відношення D

title	year	length
Star Wаrs
Mighty Ducks
Wayne’s World

Рис.5.4. Проекція відношення D

Приклад 5.1. Створити на основі операції проекції відношення D нове відношення (рис.5.4), що має містити три перших атрибути. Операція проекції записується у вигляді виразу

p_{title, year, length} (D)

Оператор вибору.

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

Схеми результуючого і вихідного відношень співпадають, співпадає і порядок розташування атрибутів. Особливістю виразу С є те, що його операндами являються або константи, або назви атрибутів відношення D. Вираз С розраховується для кожного кортежу t відношення D, шляхом заміни всіх атрибутів, включених у вираз С, значеннями відповідних компонентів кортежу t. Якщо після виконання заміни умова С становиться істиною, тоді t включається до результуючого набору кортежів відношення sс(D); у протилежному випадку кортеж t у результат не потрапляє.

Приклад 5.2. Відношення, що є результатом застосування оператору вибору s_length_³₁₀₀(D), приведене на рис.5.5.

title	year	length	InColor	studioName	producerC#
Star Wаrs			true	Fox
Mighty Ducks			true	Disney

Рис.5.5. Відношення s_length_³100(D)

Як видно із кортежів відношення на рис.5.5., що утворилося шляхом застосування оператору вибірки до кортежів екземпляру відношення D (рис.5.4.) за допомогою перевірки умови відбору кортежів length ³ 100. Перевірка показала, що тільки кортежі 1 і 2 вихідного відношення D задовольняють умові відбору.

Декартовий добуток.

Операція позначається, як R х S.У ролі R і S виступають відношення, елементами яких є кортежі. Результатом операції є також відношення, кортежі якого створюються на основі компонентів обох вихідних відношень. Порядок слідування атрибутів у результуючому відношенні такий: спочатку вказуються атрибути відношення R, а потім – S. Схема відношення –результату R х S являється об’єднанням схем відношень R і S. Але, якщо відношення R і S мають однойменні атрибути, необхідно перейменувати по меншій мірі хоча би один атрибут із кожної пари однакових атрибутів. Для рисунків атрибути А можна перейменовувати за схемою R.А і S.А.

А	В	В	С	D

Відношення R Відношення S

A	R.B	S.B	C	D

Рис.5.6. Відношення R і S та їх декартовий добуток

Натуральне з’єднання.

Операція натурального з’єднання двох відношень R і S (natural join) позначається як R S Вона передбачає включення у результуюче відношення тих кортежів із R і S, які співпадають в атрибутах, загальних для схем R і S.Результатом операції натурального з’єднання двох відношень R і S, відображених на рис. 5.6, буде екземпляр відношення на рис.5.7.

A	B	C	D

Рис.5.7. Результат натурального з’єднання відношень R і S (рис.5.6.)

У загальному випадку спільними можуть бути не один, а декілька атрибутів відношень R і S.

Тета - з’єднання.

Операція тета - з’єднання відношень R і S передбачає такі дії:

розраховується декартовий добуток відношень R і S;
із відношення - добутку вибираються ті кортежі, які задовольняють заданій умові С.

Операція тета - з’єднання позначається як

R S

^С

Приклад 5.3. Виконати тета - операцію над відношеннями R і S.

R S

⁽^A+C)^³^D

Екземпляри відношень R і S і їх декартовий добуток приведені на рис.5.6. Результуюче відношення тета - операції приведене на рис.5.8.

A	R.B	S.B	C	D

Рис.5.8. Результат виконання тета - операції стосовно Прикладу 5.3.

Зверніть увагу, що схема відношення на рис.5.8 містить усі п’ять атрибутів, і назви атрибутів В, спільних для відношень R і S, помічені префіксами “R” і “S”, які дозволяють розрізняти однойменні атрибути вихідних відношень. Таким чином операції натурального і тета - з’єднання розрізняються.

Набори операцій і формування запитів.

Реляційна алгебра дозволяє створювати вирази будь-якого ступеню складності і застосовувати оператори не тільки до первинних відношень, але й до відношень, отриманих у результаті виконання інших операторів.

Вирази реляційної алгебри можуть містити:

оператори часткових виразів;
дужки, які задають порядок групування операндів;
представляти вирази у вигляді дерев часткових виразів;
лінійні записи часткових виразів

Приклад 5.4.

Необхідно визначити назви і дати випуску кінофільмів кіностудії Fox, тривалість показу яких не менше 100 хвилин. Засоби опису алгоритму отримання відповіді:

Описовий

вибрати із відношення Movie ті кортежі, які задовольняють умові length³100
вибрати із відношення Movie ті кортежі, які задовольняють умові

studioName=”Fox”;

розрахувати пересічення множин –відносин, отриманих при виконанні п.п.1,2;
здійснити проекцію результуючого відношення п.3 на атрибути title і year.

2. деревоподібний (рис.5.9), де вершини відображують операції реляційної алгебри і умови їх виконання (π - операція проекції, σ- операція вибору, ∩ - операція пересічення)

Рис.5.9 Дерево часткових виразів реляційної алгебри

3. традиційна лінійна формула із дужками має вид:

p_{title, year} (σ_length_≧₁₀₀ (Movie) ∩ σ_{studioName = “Fox”} (Movie))

можна записати той же вираз за допомогою логічного оператора (AND)

p_{title, year} (σ_length_≧₁₀₀ _ANDσ_{studioName = “Fox”} (Movie))