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

2

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

Вступ

В маніпуляційній складовій визначаються два базові механізми маніпулювання реляційними даними: основана на теорії множин реляційна алгебра і реляційне числення, що базується на математичній логіці (вірніше, на численні предикатів першого порядка). Всі ці механізми володіють однією важливою властивістю: вони замкнені відносно поняття відношення. Це означає, що вирази реляційної алгебри і формули реляційного числення визначаються над відношеннями реляційни БД і результатами обчислень також є відношення. Як наслідок, будь-який вираз або формула можуть інтерпретуватися як відношення, що дозволяє використовувати їх в інших виразах або формулах. Як ми побачимо, алгебра і числення володіє значною виразною потужністю: дуже складні запити до бази даних можуть бути виражені за допомогою одного виразу реляційної алгебри або однією формули реляційного числення. З цієї причини саме ці механізми включені до реляційної моделі. Конкретна мова маніпулювання реляційними БД називається реляційно повною, якщо будь-який запит, що виражається за допомогою одного виразу реляційної алгебри або однієї формули реляційного числення, може бути виражений за допомогою одного оператора цієї мови. Відомо, що механізми реляційної алгебри і реляційного числення еквівалентні, тобто для будь-якого допустимого виразу реляційної алгебри можна побудувати еквівалентну (тобто ту, яка дає той самий результат) формулу реляційного числення і навпаки. Через це, в конкретній ситуації для перевірки степені реляційності деякої мови БД можна використовувати будь-який з цих механізмів. Зауважимо, що дуже рідко алгебра або числення приймаються в якості повної основи деякої мови БД. Звичайна (як, наприклад, у випадку мови SQL) мова основана на деякій суміші алгебраічних і логічних конструкцій. Тому, знання алгебраічних і логічних основ мов баз даних часто є корисним на практиці.

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

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

обєднання відношень;

перетин відношень;

взяття різниці відношень;

Декартовий добуток відношень.

Спеціальні реляційні операції включають:

обмеження відношення;

проекція відношення;

зєднання відношень;

ділення відношень.

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

Загальна інтерпретація реляційних операцій

Якщо не вдаватися в деякі тонкощі, майже всі операції з запропонованих вище володіють очевидною і простою інтерпретацією:

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

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

Замкненість реляційної алгебри

Кожне відношення характеризується схемою (або заголовком) і набором кортежів (або тілом). Тому, якщо реалізовувати алгебру, операції якої замкнені відносно поняття відношення, кожна операція повинна породжувати відношення в повній мірі, тобто воно повинно володіти і тілом, і заголовком. Лише в цьому випадку буде можливість будувати вкладені вирази. Заголовок відношення є множиною пар <імя-атрибута, імя-домена>. Якщо зробити загальний огляд реляційних операцій, можна побачити, що домени атрибутів результуючого відношення однозначно визначаються доменами відношень-результатів.

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

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

Хоча в основі теоретико-множинної частини реляційної алгебри лежить класична теорія множин, відповідні операції реляційної алгебри володіють деякими особливостями.

Почнемо з операції об'єднання (вертикальне) (все, що ми говоритимемо з приводу об'єднання переноситься на операції перетину і різниці).

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

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

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

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

SELECT * FROM A UNION SELECT * FROM B,

перетину

SELECT * FROM A INTERSECT SELECT * FROM B,

і взяття різниці

SELECT * FROM A EXCEPT SELECT * FROM B

в мові SQL результатом операції є відношенням є відношення з коректно визначеним заголовком, що співпадає з заголовком кожного з відношень операндівв. Зауважимо, що залучення до складу операцій реляційної алгебри трьох операцій об'єднання, перетину і різниці є надлишковим, оскільки будь-яка з цих операцій виражається через дві інші. Тим не менш, Кодд в свій час вирішив включити всі три операції, виходячи з інтуїтивних потреб потенциального користувача системи реляційних БД, далекого від математики.

Приклад:

SELECT P.P#

FROM P

WHERE P.WEIGHT>16.0

UNION

SELECT SP.P#

FROM SP

WHERE SP.P#='S2';

Операція взяття Декартового (або прямого) добутку двох відношень.

При виконанні прямого добутку двох відношень одержується відношення, кортежі якого є конкатенацією (счепленням) кортежів першого і другого операндів (A CROSS JOIN B).

А В

A TINES B

SELECT A.S#, B.P#

FROM A, B

В реляційній алгебрі виконується спеціалізована форма операції взяття прямого добутку - розширений прямий добуток відношень. При взятті розширеного прямого добутку двох відношень елементом результуючого відношення є кортеж, що є конкатенацією (або злиттям) одного кортежа першого відношення і одного кортежа другого відношення. Для того щоб одержати результуюче відношенням з коректно сформованим заголовком потрібно притримуватись поняття сумісності по взяттю розширеного прямого добутку. Два відношення сумісні при цьому в тому і лише в тому випадку, якщо множини імен атрибутів цих відношень не перетинаються, тобто немає атрибутів з однаковими назвами. Будь-які два відношення можна зробити сумісними по взяттю прямого добутку шляхом застосування операції перейменування до одного з цих відношень. Слід зауважити, що операція взяття прямого добутку не є виправданою на практиці. По-перше, потужність її результату досить велика навіть при допустимих потужностях операндів, а по-друге, результат операції не є більш інформативним, ніж взяті в сукупності операнди.

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

Нехай маємо відношення А з атрибутами Х і У., а символ означає будь-який оператор порівняння (=, , >, >= та ін.), такий що умова Х У при заданих Х та У дає значення істина або хибність. Тоді -вибіркою з відношення А по атрибутам Х та У називається відношення, що має той самий заголовок, що і відношення А і тіло, що містить множину всіх кортежів t відношення А, для яких перевірка умови Х У дає значення істина. Умова найчастіше задається за допомогою ключового слова WHERE.

SELECT *

FROM S

WHERE S#='S1';

З використанням цих визначень можна використовувати операції обмеження, в яких умова обмеження є довільною булевим виразом, складеним з простих умов з використанням логічних зв'язок AND, OR і AND та дужок. На інтуїтивному рівні операцію обмеження краще за все уявити як взяття деякої «горизонтальної» вирізки з відношення-операнда.

SELECT *

FROM P

WHERE P.CITY<>'Paris'

AND P.WEIGHT>10,0;

Проекція.

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

Нехай задане відношення А з атрибутами Х, Y,…, Z. Тоді проекцією відношення А за атрибутами X, Y, …, Z (A {X, Y,…, Z}) називається відношення, що задовольняє наступним вимогам.

- Його заголовок одержується з заголовку А шляхом видалення з нього всіх атрибутів, що не входять до множини A {X, Y,…, Z}.

- Його тіло містить множину всіх кортежів виду {X:х, Y:у,…, Z:z}, таких, що х, у, z у відношенні А є значеннями відповідних атрибутів (SELECT DISINCT X, Y,… Z FROM A).

SELECT S.S#, S.SNAME

FROM S

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

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

Операція зєднання відношень (горизонтальна)

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