Операції над відношеннями

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

Визначення 3.2. Відношення і називаються сумісними, якщо вони мають однаковий ступінь, який визначається -арністю відношень: – бінарне відношення (ступінь 2); – n-арне відношення (ступінь n).

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

Визначення 3.3. Об'єднання відношень – множина всіх векторів (кортежів), кожний з яких належить або :

. (3.1)

Визначення 3.4. Перетинання відношень – множина всіх векторів, кожний з яких належить одночасно як , так і :

. (3.2)

Визначення 3.5. Різниця відношень – множина всіх векторів, що належать і не належать :

. (3.3)

Визначення 3.6. Доповнення бінарного відношення до універсального відношення є різниця :

. (3.4)

Формулу (3.5) можна поширити на -місцеве відношення :

. (3.5)

Визначення 3.7. Розширений декартів добуток відношень ( і можуть бути несумісними) – множина всіх векторів таких, що – конкатенація кортежу з кортежем (конкатенація кожного вектора з кожним):

. (3.6)

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

. (3.7)

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

. (3.8)

Приклад 3.1. Дані сумісні тернарні відношення :

, .

Потрібно визначити об'єднання, перетинання, різницю відношень і . Згідно з (3.1) – (3.3) об'єднання дає:

;

;

.

Приклад 3.2. Дані множини , , їх декартові квадрати дорівнюють:

; .

Нехай бінарні відносини й задані таким способом:

– універсальне відношення,

.

Тоді доповнення відношення до універсального відношення визначається за формулою (3.4):

.

Приклад 3.3. Бінарне відношення й тернарне відношення задані так:

, .

Тоді розширений декартів добуток визначається згідно з (3.6) як конкатенація таким чином:

.