Алгебра відношень

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

Приклад 3.4. Таблиця визначає відношення реляційної моделі даних

або

, (3.9)

де відношення п'ятого ступеня , у якому співмножник – стовпець – є доменом. Його елементами служать значення атрибутів. Порядок стовпців у таблиці фіксований, рядки в загальному випадку можуть розташовуватися довільно (рядки таблиці – кортежі, стовпці – осі або домени).

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

Відповідно до потреб практики вводяться й інші операції: обмін позиціями; подвоєння позицій; згортка, композиція.

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

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

;

.

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

. (3.10)

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

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

. (3.11)

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

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

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

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

Приклад 3.5. Для відношення у формі (3.9) визначити результати виконання таких операцій: – вибір за доменом при значенні ; – проекція за доменом ; – проекція за двома доменами , ; – з'єднання за доменом D1за умовою «дорівнює», для двох таблиць (перші чотири кортежі ) і (другі чотири кортежі ).

Розв’язок. Відповідно до визначення 3.8, результат вибору за доменом являє собою відношенням ступеня 5, що складається з векторів, у яких на 3-й позиції розташовується координата :

.

Результат проектування відношення за доменом відповідно до визначення 3.9 є сукупність елементів, з яких складається стовпець : .

Результат проектування відношення за доменами , відповідно до визначення 3.10 є сукупність упорядкованих пар:

.

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

.

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

3.4 Контрольні запитання

1. Що називається -місцевим відношенням?

2. Які відношення називаються сумісними?

3. Які існують операції над відношеннями?

4. Що таке реляційна алгебра?

5. Для чого призначена алгебра відношень?

6. Для яких операцій над відношеннями умова сумісності є обов'язковою?

7. Для яких операцій над відношеннями умова сумісності не є обов'язковою?

8. Які існують спеціальні операції над відношеннями?

9. З яких елементів складаються відношення?

10. Як визначається об'єднання відношень?

11. Як визначається перетинання відношень?

12. Як визначається різниця відношень?

13. Що таке розширений декартів добуток відношень?

14. Як визначається конкатенація векторів?

15. Чому дорівнює потужність розширеного декартова добутку відношень?

16. Як визначається операція вибору?

17. Як визначається проекція відношення за доменом?

18. Як визначається проекція відношення за декількома доменами?

19. Як визначається операція з'єднання?

20. Чому дорівнює ступінь розширеного декартова добутку відношень?

4 БІНАРНІ ВІДНОШЕННЯ

Бінарні (або двомісні) відношення часто застосовуються на практиці та є добре вивченими.

Визначення 4.1. Бінарним відношенням на множині називається підмножина декартова квадрата множини : .