Іі.1.1. Реляційна алгебра Кодда.

Алгебраїчна пара : основна множина і сигнатура. Елементи і результати операцій належать основній множині.

Реляційна алгебра – алгебра в строгому розумінні. Елементи основної множини – реляції.

Сигнатура складається з 8-ми операцій.

Теоретико-множинні операції ,,\ – частково визначені (визначені тільки для сумісних реляцій з однаковою структурою).

Реляції R₁(A₁, … , A_n) і R₂(B₁, … , B_k) називаються сумісними, якщо:

1. у них однакова кількість атрибутів, тобто k = n;

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

S:{1, … , k}  {1, … , k}, що

N(A_i) = N(B_S(i)), i = l  k.

Об’єднання.

R₁R₂: в результуючу реляцію попадають всі кортежі першої і другої реляції без дублів.

Перетин.

R₁R₂: в результуючу реляцію попадають кортежі, присутні і в першій, і в другій реляції.

Різниця.

R₁\R₂: в результуючу реляцію попадають кортежі з R₁, яких немає в R₂.

Відзначимо деякі особливості розглянутих операцій.

1. Деякі домени можуть бути нескінченними, в результаті операції доповнення можна отримати або нескінченну реляцію, або реляцію з дуже великою кількістю кортежів. Тому у реляційній алгебрі на відміну від алгебри множин використовується операція різниці, а не доповнення.

2. Часткова визначеність введених операцій теж зумовлена прагматичним аспектом. Без обмеження сумісності результатом операції об’єднання могли б бути різноструктурні кортежі, а не таблиця.

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

R₁R₂ – визначається для будь-яких реляцій.

R₁R₂ = {(r₁, … , r_k, r_k+1, … , r_k+n) | (r₁, … , r_k) R₁, (r_k+1, … , r_k+n) R₂}.

Ця операція може різко збільшити об’єм результату.

Проекція.

Реляція S(B₁, … , B_n) узгоджена з R(A₁, … , A_k), якщо

 f : _S _R, N(f(B_i)) = N(A_i), i = 1  n.

Відображення f однозначне, але, взагалі кажучи, не взаємно однозначне.

Проекцією реляції R на схему S відносно узгодження f будемо називати реляцію

T = R[S] таку, що

T = {(r[A_i1], r[A_i2], … , r[A_in])}

T = R[A_i1, A_i2, … , A_in,]

Реляція R несе і схему, і дані, а реляція S – тільки схему.

Атрибути реляції S повинні бути підмножиною множини атрибутів реляції R.

Примітка.

При практичному використанні цієї операції замість другої реляції звичайно записують список атрибутів, по яким виконується проектування. З теоретичної точки зору така підміна не є “чистою”, бо список атрибутів не належить основній множині, а тому не може виступати в ролі операнда. Отже, при “чистому” теоретичному підході операцію проекції слід вважати бінарною, а на практиці вона розглядається як унарна з параметрами.

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

Посилаючись на реляцію П (постачальник), запит “знайти прізвища всіх постачальників” може бути виражений так: П[прізв].

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

Операція  - з’єднання ( - join).

Введемо поняття  - порівнюваності для кортежів.

На двох реляціях R(A₁, … , A_k) і S(B₁, … , B_n) візьмемо відповідно два підкортежі:

r₁ = (d₁, d₂, … , d_m), r₂ = (d₁^|, d₂^|, … , d_m^|);

Нехай  = {=, , <, , >, , …}; наповнення цієї множини залежить від того, які бінарні предикати задані на відповідних доменах.

Два кортежі r₁ і r₂  - порівнювані:

r₁r₂  d_i  d_i^|, i = 1,m; (m  k, m  n);

Нехай в реляції R виділений список атрибутів M₁ = {A₁, … , A_m}, а в реляції S список атрибутів M₂ = {B₁, … , B_m}, причому відповідні атрибути співпадають по доменам, тобто

N(A_i) = N(B_i), i = 1,m;

Операція  - з’єднання реляції R з реляцією S по спискам M₁ і M₂ :

R[M₁  M₂]S = {t  R  S | t[M₁]  t[M₂]}.

Операція  - з’єднанняпо порівнянню ‘=’ називається еквіз’єднанням.

Приклад.

R	A1	A2	A3		S	B1	B2
	A	1	1			2	U
	A	2	1			3	V
	B	1	2			4	U
	B	2	5
	C	3	3

1. R₁R[A₃ = B₁]S

R1	A1	A2	A3	B1	B2
	B	1	2	2	U
	C	3	3	3	V

2. R₂R[A₂ > B₁]S

R2	A1	A2	A3	B1	B2
	C	3	3	2	U

Операція еквіз’єднання називається природним з’єднанням(naturaljoin), якщо в результат проходить лише один стовпчик з двох (в обох стовпчиках у кожному рядочку значення повинні співпадати за визначенням операції еквіз’єднання).

Наприклад: R₁R[A₃B₁]S – в результуючій таблиці не було б атрибутаB₁.

Операція  - обмеження.

В літературі іноді цю операцію називають селекцією або фільтрацією.

Ця операція задається над однією реляцією з двома списками атрибутів; використовується також поняття - порівнюваності.

Нехай задана реляція R(_R), де_R - множина імен атрибутів;

M₁= {A₁, … , A_m}_R; і

M₂ = {B₁, … , B_m} _R - списки атрибутів з властивістю

N(A_i) = N(B_i); i = 1,m;

 - обмеження реляції R по спискам M₁ і M₂ :

R[M₁  M₂] = {r | (r R) &(r[M₁]  r[M₂])}.

3. R₃R[A₂ = A₃]

R3	A1	A2	A3
	A	1	1
	C	3	3

Операція ділення.

Спочатку введемо одне допоміжне поняття.

Нехай задана реляція R(A₁, … , A_k) і два взаємнодоповнюючі списки атрибутів

M₁ = {A₁, … , A_n}; M₂ = {A_n+1, … , A_k}

Нехай є С_{1 =} D₁…D_n; С_{2 =} D_n+1…D_k; де D_i = N(A_i), i = 1,k;

Якщо візьмемо деякий елемент x  С₁, то образом x по реляції R буде називатись множина підкортежів :

im_Rx = {y  С₂ | (x, y)  R}

Розглянемо реляції R(_R), S(_S) і списки атрибутів

{A₁, … , A_n}_R ; {B₁, … , B_n}_S;

Необхідно, щоб реляції R[A₁, … , A_n] і S[B₁, … , B_n] були сумісними, тоді операція R[A B]S називається діленням R на S по спискам {A₁, … , A_n} і {B₁, … , B_n}

Результатом є множина підкортежів по атрибутам, що доповнюють список {A₁, … , A_n}.

R[A B]S = {r[A_n+1, … , A_k] | (r R) & (S[B₁, … , B_n]  im_R(r[A_n+1, … , A_k]))}

Приклад використання операції ділення.

Нехай задана таблиця R з двома атрибутами (мова програмування і прізвище програміста, який цією мовою володіє)

Знайти прізвища програмістів, які знають мови А і Ф одночасно. Для виконання такого запиту утворимо допоміжну реляцію Sз одним атрибутом і двома кортежами з відповідними значеннями кодів мов програмування {А,Ф}.

R[мова мв]S

R	Мова	прізв		S	мв
	А	І			А
	А	П			Ф
	ПЛ	С
	Ф	Ф
	Ф	І
	Ф	С
	ПЛ	П
	П	Ф
	П	І

Образом І буде {А, Ф, П}, що є надмножиною відносно{А, Ф}, тому І проходить у результуючу таблицю; а П, С, Ф – не проходять у результуючу таблицю, бо їх образи не накривають {А, Ф}. Це означає, що програміст І знає мови {А, Ф}(можливо ще щось), а інші не знають цих мов одночасно.

Приклади використання операцій реляційної алгебри у запитах на основі бази даних про поставки.

1. Знайти прізвища постачальників, що живуть в Одесі.

(П[місто = ‘Одеса’])[прізв] П1.

Зауважимо, що використання константи ‘Одеса’ у наведеному прикладі операції  -обмеження є відступом від теоретичної “чистоти” реляційної моделі, але розробники мов на основі реляційної алгебри йшли на подібні відступи задля зручності користувача та практичної ефективності. Ми і надалі будемо використовувати такі відступи. Наведемо також теоретично “чистий” варіант вищезгаданого запиту. Для цього введемо допоміжну реляцію ДОП(місто) з єдиним кортежем ‘Одеса’.

(П[місто = місто]ДОП)[прізв] П1.

2. Знайти ціни поставок деталей з кодом Д1, що виконують постачальники з кодом S1.

(ОПД[КП = ‘S1’ & КД = ‘Д1’])[ціна]  ОП2.

Знову зауваження відносно теоретичної “чистоти”. “Чистий” варіант для такого запиту передбачає введення допоміжної реляції ДОП1(КП1,КД1) з єдиним кортежем <‘S1’,‘Д1’>.

(ОПД[КП,КД = КП1,КД1]ДОП1)[ціна]  ОП2.

Відзначимо ще один “негаразд” у цьому прикладі. У першому варіанті запису (на відміну від другого) елементарні порівняння зв’язані логічною зв’язкою & (можлива також і диз’юнкція ), що синтаксично (і прагматично) підвищує гнучкість використання операцій -з’єднання і -обмеження.

3. Знайти прізвища постачальників, які постачають принаймні одну червону деталь.

(Д[колір = черв])[КД]  Д3

{знайдено коди деталей червоного кольору}

(ОПД[КД = КД]Д3)[КП]  П4

{знайдено коди постачальників, що постачають деталі з Д3}

(П[КП = КП]П4)[прізв]  Res

4. Знайти прізвища постачальників, які постачають хоча б одну деталь з тих, що постачають постачальники, що постачають принаймні одну червону деталь.

((ОПД[КП, КД])[КП ° КП]П4)[КД]  Д4

((ОПД[КП, КД])[КД ° КД]Д4)  П5

(П5[КП ° КП]П)[прізв]  Res1

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

4. Знайти прізвища постачальників, що постачають всі деталі.

(ОПД[КП, КД])[КД  КД]( Д[КД] )  R1

(R1[КП ° КП]П)[прізв]  Res

Зауважимо, що природні мови, зокрема українська, на відміну від формальних мов мають неоднозначності, які необхідно уточнювати. У наведеному запиті словосполучення “всі деталі” може означати всі існуючі деталі (таблиця Д), чи всі деталі, що постачаються (таблиця ОПД). Запис засобами операцій реляційної алгебри орієнтується на таблицю Д, для іншого варіанту виділений курсивом текст Д[КД] потрібно було б замінити на ОПД[КД].

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

((П[прізв = ‘Іванов’])[КП ° КП](ОПД[КП,КД]))[КД]  R1

{знайдено коди деталей, які постачає Іванов}

((ОПД[КП,КД])[КД ° КД]R1)[КП]  R2

(П[КП ° КП]R2)[прізв]  Res

6. Знайти прізвища постачальників, які постачають всі ті деталі, які постачає Іванов.

((П[прізв = ‘Іванов’])[КП ° КП]ОПД[КП,КД])[КД]  R1

(ОПД[КП, КД])[КД  КД]R1  R2

(П[КП ° КП]R2)[прізвище]  Res

7. Знайти прізвища постачальників, які постачають точно ті деталі, які постачає Іванов.

{реляцію R1 взято з попереднього прикладу}

(ОПД[КП, КД])[КД  КД]R1  R2

{знайдено коди постачальників, що постачають принаймні всі деталі з R1}

((ОПД[КП, КД])[КД  КД]R1)[КП]  R3

{знайдено коди постачальників, що постачають хоча б одну деталь не з R1}

R2\R3  R4

8. Знайти номери одержувачів, які не одержують жодної червоної деталі від постачальників з міста N.

Задача розв’язується від супротивного, розбивається на підзадачі. Спочатку знаходимо коди одержувачів, які одержують хоча б одну червону деталь, а потім від всіх кодів одержувачів віднімаємо R3.

(П[місто = ‘N’])[КП]  R1

(Д[колір = черв])[КД]  R2

(((R1[КП ° КП]ОПД)[КД, КО])[КД ° КД]R2)[КО]  R3

(О[КО]\R3)  R4

9. Знайти прізвища постачальників, які постачають принаймні всі червоні та всі зелені деталі.

(Д[колір = черв  колір = зел])[КД]  R1

(ОПД[КП, КД])[КД  КД]R1  R2

(R2[КП  КП]П)[прізв]  R3

10. Знайти прізвища постачальників, які постачають принаймні одну червону та одну зелену деталь.

(Д[колір = черв])[КД]  Д1

(Д[колір = зел])[КД]  Д2

((ОПД[КП, КД])[КД  КД]Д1)[КП]  П1

((ОПД[КП, КД])[КД  КД]Д2)[КП]  П2

П1  П2  П3

11. Знайти прізвища постачальників, які постачають одну і ту ж саму деталь всім одержувачам.

((ОПД[КП, КД, КО])[КО  КО](О[КО]))[КП]  R1

(R1[КП  КП]П)[прізв]  R2

Зауважимо, що у цьому записі дуже важливою є роль атрибута КД (виділено курсивом). У ході виконання операції ділення образ КО формується для підкортежа <КП, КД>, отже створюється ефект “однієї і тієї ж деталі”.

12. До реляції Д внести новий кортеж

Д  {<‘Д7’, ‘чайка’, ‘сірий’, 20, ‘Одеса’>}  Д

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

13. З реляції П вилучити кортеж

П  {<‘S3’, ‘Сидоров’, 7, ‘Донецьк’>}  П

Зауваження аналогічне попередньому пункту, але у випадку відсутності потрібного кортежа в реляції П до виконання операції.

Після розгляду наведених прикладів необхідно зауважити, що можливі і інші способи формування запитів.

Примітка.

Сигнатура операцій, що була запропонована Е.Коддом, не є незалежною, у тому розумінні, що деякі операції можуть бути виражені через інші. Зокрема, об’єднання може бути виражене через перетин та різницю, а перетин – через об’єднання та різницю. Операція з’єднання може бути виражена через декартів добуток та операцію обмеження, а операція ділення -- декартів добуток, різницю та проекцію. Отже, кількість операцій може бути зменшена до 5.