Теоретико-множинні операції реляційної алгебри

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

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

Реляційна алгебра складається з восьми операторів: чотирьох традиційних операцій над множинами (теоретико-множинних операцій) і чотирьох спеціальних реляційних операцій.

До традиційних операцій ставляться операції:

• об'єднання - повертає відношення, що містить усі кортежі, що належать або одному із двох певних відношень, або обом;

• перетин - повертає відношення, що містить усі кортежі, що належать одночасно двом певним відношенням;

• віднімання - повертає відношення, що містить усі кортежі, які належать першому із двох певних відношень і не належать другому;

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

До спеціальних операцій ставляться:

• вибірка (обмеження) - повертає відношення, що містить усі кортежі з певного відношення, задовольняючі певним умовам;

• проекція - повертає відношення, що містить усі кортежі (називані як підкортежі)

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

• сполучення (природнє) - повертає відношення, кортежі якого - це комбінація двох кортежів (приналежних відповідно двом певним відношенням), що мають загальне значення для одного або декількох атрибутів цих двох відношень (і такі загальні значення в результуючому кортежі з'являються тільки один раз);

• ділення - для двох відношень, бінарного й унарного, повертає відношення, що містить усі значення одного атрибута бінарного відношення, що відповідає (в іншому атрибуті) усім значенням в унарному відношенні.

Замкнутість

Як ми вже відзначали, результат кожної операції над відношенням також є відношенням. Ця реляційна властивість називається властивістю замкнутості. Звідси можна зробити висновок: оскільки результат будь-якої операції має той же тип, що й вихідні об'єкти (відношення), то результат однієї операції може використовуватися в якості вихідних даних для іншої. Інакше кажучи, можна записувати вкладені вирази, тобто вирази, у яких операнди самі представлені виразими замість простих імен відношень.

Сумісність по типу

Операції об'єднання, перетину й віднімання вимагають від операндів сумісності по типу.

Два відношення сумісні по типу, якщо в них еквівалентні схеми, а точніше:

1. якщо кожне їх їх має ту саму множину атрибутів (а значить і однаковий степінь),

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

Приклад: є наступні відношення (Рис. 2-17)

Відношення Продукти1 містить продукти, наявні в магазині,

Відношення Продукти2 містить продукти, що поставляються постачальником Р₂

Відношення Постачальники містить постачальників продуктів,

Відношення ВидПродукта містить види продуктів.

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

Рис. 2-17. База даних продуктів і постачальників (значення для прикладу)

Теоретико-множинні операції реляційної алгебри

Об'єднанням двох сумісних по типу відношень А і В називається відношення з тим же заголовком, як у вихідних відношеннях, і з тілом, що складається із множини всіх кортежів, що належать А або В або обом відношенням (за винятком повторюваних).

Нехай задано два відношення А={а}, В={b}, де а й b -відповідно кортежі відношень А и В, то об'єднання ,

де - кортеж нового відношення, - операція логічного додавання «АБО».

Приклад: Об'єднаємо, наведені на Рис. 2-17, відношення Продукти1 (продукти, наявні в магазині) і Продукти2 (продукти, що поставляються постачальником Р₂). Результатом об'єднання стане відношення R1 (Рис. 0-18), що містить продукти, які або є в магазині або поставляються постачальником Р₂ (або й те й інше).

Зверніть увагу, що дублюючі кортежі виключені з результуючого відношення R1.

Rl = Продукти1 Продукти2

Rl

Рис. 2-18. Приклад об'єднання

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

,

де - операція логічного множення (логічне «і»).

Приклад: Перетином відношень Продукти1 і Продукти2 (Рис. 2-17) стане відношення R2 (Рис. 2-19), що містить продукти, наявні в магазині, і ті що поставляються постачальником Р₂.

R2 = Продукти1 Продукти2

R2

Рис. 2-19. Приклад перетину

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

.

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

Приклад: При відніманні відношення Продукти2 з відношення Продукти1 (Рис. 2-17) вийде відношення R3 (Рис. 2-20), що містить продукти, які наявні в магазині, крім тих продуктів, які поставляє постачальник Р₂.

При відніманні відношення Продукти1 з відношення Продукти2 вийде інше відношення R4 (оскільки операція віднімання не комутативна). Відношення R4 (Рис. 2-20) буде містити продукти, що поставляються постачальником Р₂, крім тих продуктів, які є в магазині.

R3 =Продукти1\Продукти2 R4 = Продукти2\Продукти1

R3 R4

Рис. 2-21. Приклади віднімання

Розширений декартовий добуток

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

Перш ніж визначити саму операцію, уведемо додатково поняття зчеплення кортежів.

Зчепленням кортежів і називається кортеж, отриманий додаванням значень другого в кінець першого. Зчеплення кортежів с и q позначається як (c,q).

де - число елементів у першому кортежі с, m - число елементів у другому кортежі q.

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

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

Тобто якщо А={а}, В={b}, то розширений декартовий добуток

.

Зверніть увагу, що кардинальне число результату дорівнює добутку кардинальних чисел вихідних відношень А і В, а степінь дорівнює сумі їх степенів.

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

Приклад; Декартовим добутком відношень Постачальники й ВидПродукта (Рис. 2-17) буде відношення R5 (Рис. 2-21). Відношення R5 відповідає ситуації, коли всі постачальники поставляють усівиди продуктів.

R5 = Постачальники ВидПродукта

R5

Рис. 2-21. Приклад розширеного декартова добутку

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

Усі теоретико-множинні операції є асоціативними операціями, тобто

Спеціальні реляційні операції

Вибірка (обмеження, горизонтальна підмножина)

Для визначення цієї операції необхідно ввести додаткові позначення.

Нехай - булевский вираз, складений з термів порівняння за допомогою зв'язувань і (), або (), не (-) і, можливо, дужок. У якості термів порівняння допускаються:

1. терм ,

де А - ім'я деякого атрибута, що приймає значення з домена D; а - константа, узята з того ж домена D, ;

- одна із допустимих для даного домена D операцій порівняння ;

2. терм ,

де А, В - імена деяких -порівнянних атрибутів, тобто атрибутів, що приймають значення з того самого домена D.

Тоді

Вибіркою ( -вибіркою), заданої на відношенні А у вигляді булевого виразу, визначеного на атрибутах відношення А, називається відношення, що має той же заголовок, що й відношення А, і тіло, що містить множину усіх кортежів відношення А, для яких дійсна умова вибору або обмеження:

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

Приклад:

• Результатом вибірки продуктів, що поставляються постачальником Р₃, з відношення Продукти1 буде відношення R6 (Рис. а)

a) R6=Продукты1 [КодПостачальника = " Р₃"]

Результатом вибірки Владивостоцьких постачальників з відношення Постачальники буде відношення R7 (Рис. б)

б) R7 = Постачальники [Місто = "Владивосток"]

Рис. 2-22. Приклади операцій вибірки

Проекцією відношення А по атрибутах X,Y,..,Z, де кожний з атрибутів належить відношенню

А(А [Х, Y,..., Z]),

називається відношення із заголовком {X,Y,..,Z}і тілом, що містять множину усіх кортежів {Х:х,Y:y,...,Z:z}, таких, для яких у відношенні А значення атрибута Х рівно х, атрибута Y рівне y,..., атрибута Z рівно z.

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

Ніякий атрибут не може бути зазначений у списку атрибутів більше одного разу.

Приклад:

• Проекцією відношення Продукти1 по атрибуту КодПостачальника буде відношення R8 (Рис. а). Зверніть увагу, що дублюючі кортежі виключені з відношення R8.

• Проекцією відношення Постачальники по атрибуту Місто буде відношення R9 (Рис. б)

• Досить часто операція проекції використовується в комбінації з іншими операціями. Наприклад, потрібно вибрати назви постачальників із Владивостоку (на основі відношення Постачальники. Спочатку виконується операція вибірки, а потім - проекції (Рис. в).

а) R8 -Продукти1 [КодПостачальника]

б) R9 = Постачальники [Місто]

с) R 7 — Постачальники [Місто = "Владивосток" ]

R10 = R 7 [Найменування]

або R10 = (Постачальники [Місто = "Владивосток"]) [Найменування]

Рис. 2-23. Приклади операцій проекції

З’єднання (природнє, умовне)

Операція з’єднання має кілька різновидів. Однак найбільш важливим є природнє з’єднання, тому часто для позначення саме природнього з’єднання використовують загальний термін «з’єднання».

Нехай відношення А і В мають заголовки:

{Xl,X2,...,Xm,Yl,Y2,...,Yn} і {Yl, Y2,..., Yn, Zl, Z2,..., Zp} відповідно;

тобто атрибути Yl, Y2,..., Yn (і тільки вони) - загальні для двох відношень;

XI, Х2,..., Xm - інші атрибути відношення A; Zl, Z2,..., Zp - інші атрибути відношення В. Припустимо також, що відповідні атрибути (тобто атрибути з однаковими іменами) визначені на тому самому домені. Будемо розглядати вирази {XI, Х2,..., Xm}, {Yl, Y2,..., Yn}, {Zl, Z2,..., Zp} як три складових атрибута X, Y, Z відповідно.

Тоді природнім з’єднанням відношень А і В називається відношення із заголовком {X,Y, Z} і тілом, що містить множину усіх кортежів {Х:х, Y:y, Z:z}таких, для яких у відношенні А значення атрибутів рівно х, а атрибута Y рівне у, і у відношенні В значення атрибута Y рівне у, а атрибута Z рівне z.

Природнє з’єднання має властивості комутативності й асоціативності.

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

Приклад: Розглянемо відношення Продукти1 і Постачальники (Рис. 2-17). Атрибути КодПостачальника й КодП визначені на тому самому домені кодів постачальників. Оскільки при природньому з'єднанні також потрібно, щоб загальні атрибути відношень, що з'єднуються, мали однакові імена, перейменуємо атрибут КодП відношення Постачальники в КодПостачальника. Тоді природнім з’єднанням відношень Продукти1 і Постачальники по атрибуту КодПостачальника буде відношення R11 (Рис, 2-24).

R11 = Продукти1 [Продукти1.КодПостачальника = Постачальники.КодПостачальника] Постачальники

Рис. 2-24. Приклад природнього з’єднання

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

Нехай відношення А і В не мають загальних імен атрибутів, і визначається як в операції вибірки. Тоді умовним з’єднанням відношення А по атрибуту X з відношенням В по атрибуту Y називається відношення із заголовком, який являє собою зчеплення двох заголовків вихідних відношень А і В (як і при операції декартового добутку), і з тілом, що містить множина кортежів t, таких що t належить цьому декартову добутку й обчислення умови "X Y " дає значення «істина» для цього кортежу. Атрибути X і Y повинні бути визначені на тому самому домені, а операція повинна мати сенс для цього домена.

Приклад: Одержати назви продуктів (відношення Продукти1 - Рис. 2-17), що поставляються постачальниками із Владивостока (відношення Постачальники - Рис. 2-17). По суті, у цьому прикладу необхідно використовувати дві операції: умовного з’єднання - для одержання безпосередньо списку продуктів, що поставляються Владивостоцькими постачальниками (R12); і проекції - для одержання тільки назв продуктів (R13) (Рис. 2-25).

R12 = Продукти 1 [(Продукти1.КодПостачальника = Постачальники.КодП)

Постачальники.Місто = "Владивосток"] Постачальники

R13 = R12 [Продукт]

або

R13 = (Продукти1 [(Продукти 1.КодПостачальника = Постачальники.КодП)

Постачальники.Місто = "Владивосток"] Постачальники) [Продукт]

Рис. 2-25 П риклад умовного з’єднання

Ділення

Нехай відношення А і В мають заголовки: {Xl,X2,...,Xm,Yl,Y2,...,Yn} і {Y1,Y2,...,Yn} відповідно; тобто атрибути Y1, Y2,..., Yn - загальні для двох відношень, і відношення А має додаткові атрибути Xl,X2,...,Xm, а відношення В не має додаткових атрибутів. (Відношення А і В представляють відповідно ділене й дільник). Припустимо також, що відповідні атрибути (тобто атрибути з однаковими іменами) визначені на тому самому домені. Нехай вирази { Xl,X2,...,Xm}і { Yl,Y2,...,Yn}позначають два складових атрибута X і Y відповідно.

Тоді діленням відношень А і В називається відношення із заголовком {X} і тілом, що містить множину усіх кортежів {Х:х} таких, що існує кортеж {Х:х, Y:y}, який належить відношенню А для всіх кортежів {Y:y}, що належать відношенню В.

Нестрого це можна сформулювати так: результат містить такі Х-значення з відношення А, для яких відповідні Y-значення (з А) включають усі Y-значення з відношення В.

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

Приклад: Нехай відношення R14 містить постачальників і види продуктів, що поставляються ними, а відношення ВидПродукта містить види продуктів (Рис. 2-26). Тоді, щоб одержати постачальників, що поставляють УСІ види продуктів, необхідно відношення R14 розділити на відношення ВидПродукта по атрибуту КодВиду (Рис. 2-26).

R15 = R14 [КодВида КодВида] ВидПродукта

Рис. 2-26. Приклад операції ділення

Отже, ми розглянули операції реляційної алгебри. Ці вісім операцій (об'єднання, перетин, віднімання, декартовий добуток, вибірка, проекція, з’єднання, ділення) не являють собою мінімальний набір операцій. Тобто деякі операції можна виразити через інші операції, а саме - з’єднання, перетин й ділення. Наприклад, з’єднання - це проекція вибірки декартового добутку. Таким чином, примітивними операціями, тобто які не можна виразити через інші операції, є інші п'ять операцій: об'єднання, віднімання, вибірка, проекція, декартовий добуток. Ці п'ять примітивних операцій будуть становити мінімальний набір операцій реляційної алгебри.

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

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

Розглянемо кілька прикладів для демонстрації можливостей операцій реляційної алгебри.

I. Нехай дано три відношення з еквівалентними схемами: (ПІП, Посада, Відділ). Відношення R1 містить список співробітників підприємства, що працюють над проектом P1, R2 - список співробітників, що працюють над проектом Р2, R3 - список співробітників, що живуть у Владивостоці. Співробітники можуть працювати над декількома проектами.

Скласти формули для наступних запитів:

1. Список співробітників, що живуть не у Владивостоці, тобто це такі співробітники, які можуть міститися у відношенні R1 або R2 або обох відношеннях, але не входять у відношення R3

R1 R2 \ R3 або (Rl\R3) (R2\R3).

Цей приклад показує, що один і той запит можна сформулювати декількома способами.

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

R1 R2 R3.

3. Список співробітників, що працюють тільки над одним із проектів

(R1 R2)\(R1 R2).

4. Список співробітників, що працюють тільки над одним із проектів, і таких що живуть у Владивостокові

(R1 R2) \ (R1 R2) R3 або (R1 R3) (R2 R3) \ (R1 R2).

II. Дані наступні відношення:

Rl (Taб№, ПІП, Посада, Відділ) - список співробітників по відділах

R2 (Посада, Оклад) - посадові оклади

РЗ(Посада, Відділ) - штатні посади по відділах, тобто які посади повинні бути в кожному відділі.

Співробітник може займати кілька посад у тому самому або різних відділах. Скласти формули для наступних запитів:

1. Табельні номери й ПІП співробітників відділу "Бухгалтерія"

(R1[Відділ = "Бухгалтерія"]) [Таб№, ПІП ]

2. ПІП співробітників з окладом більше 3000 грн

(R1[R1.Посада = R2.Посада R2.Оклад> 3000]R2) [ПІП].

3. Список вакантних посад у відділах

R3 \ (R1 [Посада, Оклад])

4. Відділи, що не мають по штату посаду "Майстер"

R3 \ R3[Посада = "Майстер"]

5. ПІП співробітників, що займають більше однієї посади

(R1[R1.ПІП = R1’.ПІП R1.Посада R1’.Посада]R1’) [ПІП].

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

6. ПІП співробітників, що займають тільки одну посаду, для цього спочатку знайдемо співробітників, що займають більше однієї посади

R4 = (R1[R1.ПІП = R1’.ПІП R1.Посада R1’.Посада]R1’) [ПІП].

віднімемо із проекції R1 по ПІП отримане відношення R4

(Rl[ПІП])\R4

7. Відділи, що мають у штаті, принаймні, усі ті посади, що й у відділі "Цех 1" знайдемо всі посади по штату у відділі "Цех1"

R4=(R3[Відділ="Цех 1"])[Посада]

відповідь на поставлене питання

R3 [Посада Посада] R4.