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

Реляці́йна а́лгебра — це формальна процедурна мова запитів.

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

Примітивні операції

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

Операції з множинами

• Декартів добуток,
• Об'єднання множин,
• Різниця множин.

Вибірка (σ)

Докладніше:

Узагальнена вибірка — це унарний оператор, що записується як ${\displaystyle \sigma _{\varphi }(R)}$, де ${\displaystyle \varphi }$ є формулою числення висловлень, що складається з атомів, дозволених у та логічних операторів ${\displaystyle \land }$ (кон'юнкції), ${\displaystyle \lor }$ (диз'юнкції) та ${\displaystyle \lnot }$ (заперечення). Така вибірка вибирає всі кортежі із ${\displaystyle R}$, для яких ${\displaystyle \varphi }$ істина.

Проєкція (π)

Докладніше: Проєкція (реляційна алгебра)

Проєкція — це унарна операція, що записується як ${\displaystyle \pi _{a_{1},...,a_{n}}(R)}$, де ${\displaystyle a_{1},\dots ,a_{n}}$ є множиною назв атрибутів. Результат проєкції визначається як множина, що отримується із всіх кортежів із ${\displaystyle R}$, що обмежуються ${\displaystyle \{a_{1},\dots ,a_{n}\}}$.

Перейменування (ρ)

Докладніше:

Перейменування є унарним оператором, що записується як ${\displaystyle \rho _{a/b}(R)}$. Результат застосування оператора ідентичний ${\displaystyle R}$, за винятком того, що поле ${\displaystyle b}$ в усіх кортежах перейменовується на поле ${\displaystyle a}$. Цей оператор застосовується для простого перейменування атрибута відношення, або самого відношення.

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

Сумісність відношень

Відношення, сумісні з об'єднанням

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

Відношення називаються сумісними по об'єднанню, якщо

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

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

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

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

Операція перейменування атрибутів

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

Синтаксис: R RENAME Atr₁, Atr₂, … AS NewAtr₁, NewAtr₂, … де R — відношення  Atr₁, Atr₂, … — початкові імена атрибутів; NewAtr₁, NewAtr₂, … — нові імена атрибутів.

Операція присвоєння

Операція присвоєння (:=) дозволяє зберегти результат вичислення реляційного вираження у дійсному відношенні.

Теоретико-множинні операції

Об'єднання

Відношення з тим же заголовком, що і у сумісних по типу відношень A і B, і тілом, що складається з кортежів, що належать або A, або B, або обом відношенням. Синтаксис:A UNION B 

Перетин

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

Віднімання

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

Декартовий добуток 

Віднощення (A₁, A₂, …, A_m, B₁, B₂, …, B_m), заголовок якого є зчепленням (конкатенацією) заголовків відношень A (A1, A2, ..., Am) і B (B1, B2, ..., Bm), а тіло складається з кортежів, які є зчепленням кортежів відносин A і B:

(a₁, a₂, …, a_m, b₁, b₂, …, b_m)

таких, що (a₁, a₂, …, a_m)∈ A, (b₁, b₂, …, b_m)∈ B.

Синтаксис:

A TIMES B

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

Вибірка (обмеження)

Відношення з тим же заголовком, що і у відношенню A, і тілом, що складається з кортежів, значення атрибутів яких при підстановці в умову c дають значення ІСТИНА. c являє собою логічне вираження, до якого можуть входити атрибути відношення A і / або скалярні добутки. Синтаксис: A WHERE c

Проєкція

Проєкція в реляційній алгебрі - унарна операція, яка дозволяє отримати «вертикальну» підмножину даного відношення, або таблиці, тобто така підмножина, яка виходить вибором специфікованих атрибутів з наступним виключенням, якщо це необхідно, надлишкових дублікатів кортежів. Нехай дана таблиця T з іменами атрибутів A_ {1}, \; A_ {2}, \; \ ldots, \; A_ {n}, тобто T (A_ {1}, \; A_ {2}, \; \ ldots, \; A_ {n}) і деяку підмножину множини імен атрибутів \ {A _ {{i_ {1}}}, \; A _ {{i_ {2}}}, \; \ ldots, \; A _ {{i_ {k}}} \}. Результатом проєкції таблиці за обраними іменами атрибутів називається нова таблиця T (A _ {{i_ {1}}}, \; A _ {{i_ {2}}}, \; \ ldots, \; A _ {{i_ {k}}} ), отримана з вихідної таблиці викреслюванням атрибутів, що не входять в вибрану множину, з подальшим можливим вилученням надлишкових дублікатів кортежів. 

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

З'єднання

Операція з'єднання є результат послідовного застосування операцій декартового добутку і вибірки. Якщо у відносинах і є атрибути з однаковими найменуваннями, то перед виконанням з'єднання такі атрибути необхідно перейменувати.  Синтаксис: (A TIMES B) WHERE c

Ділення

Відношення з заголовком (X1, X2, ..., Xn) і тілом, що містить безліч кортежів (x1, x2, ..., xn), таких, що для всіх кортежів (y1, y2, ..., ym) ∈ B щодо A (X1 , x2, ..., Xn, Y1, y2, ..., Ym) знайдеться кортеж (x1, x2, ..., xn, y1, y2, ..., ym).  Синтаксис: A DIVIDEBY B

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

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

• Оператор з'єднання

Оператор з'єднання визначається через оператори декартового добуткуі вибірки наступним чином: (A TIMES B) WHERE X = Y де X і Y атрибути відповідно відношення A і B з від початку рівними іменами.

• Оператор перетину

Оператор перетину виражається через віднімання наступним чином: A INTERSECT B = A MINUS (A MINUS B)

• Оператор ділення

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

A DIVIDEBY B = A[X] MINUS ((A[X] TIMES B) MINUS A)[X]

Див. також

• SQL
• База даних

Зноски

1. Silberschatz та Sudarshan, 2011, с. 217.

Література

• Silberschatz, Abraham; Sudarshan, S. (2011). Database system concepts (вид. 6). New York: McGraw-Hill. ISBN . OCLC 436031093.