Перейти до вмісту

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

Матеріал з Вікіпедії — вільної енциклопедії.

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

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

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

[ред. | ред. код]

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

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

[ред. | ред. код]

Вибірка (σ)

[ред. | ред. код]

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

Проєкція (π)

[ред. | ред. код]

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

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

[ред. | ред. код]

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

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

[ред. | ред. код]

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

[ред. | ред. код]

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

[ред. | ред. код]

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

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

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

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

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

[ред. | ред. код]

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

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

[ред. | ред. код]

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

Синтаксис: R RENAME Atr1, Atr2, … AS NewAtr1, NewAtr2, … де R — відношення  Atr1, Atr2, … — початкові імена атрибутів; NewAtr1, NewAtr2, … — нові імена атрибутів.

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

[ред. | ред. код]

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

Об'єднання

[ред. | ред. код]

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

Перетин

[ред. | ред. код]

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

Віднімання

[ред. | ред. код]

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

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

[ред. | ред. код]

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

(a1, a2, …, am, b1, b2, …, bm)

таких, що (a1, a2, …, am)A, (b1, b2, …, bm)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]

Див. також

[ред. | ред. код]

Зноски

[ред. | ред. код]
  1. Silberschatz та Sudarshan, 2011, с. 217.

Література

[ред. | ред. код]
  • Silberschatz, Abraham; Sudarshan, S. (2011). Database system concepts (вид. 6). New York: McGraw-Hill. ISBN 9780073523323. OCLC 436031093.