Выделяют два теоретических языка обработки реляционных данных —реляционная алгебра и реляционное исчисление.

Реляционная алгебра

Реляционная алгебра —процедурный язык обработки ре­ляционных таблиц. В нем используется пошаговый принцип создания таблиц, содержащих ответы на запросы.

Реляционная алгебра как теоретический язык  запросов, по сравнению с реляционным исчислением, более наглядно описывает выполняемые над отношениями действия. При­мером языка запросов, основанного на реляционной алгебре, является ISBL (Information System Base Language — базовый язык информационных систем). Языки запросов, построенные на основе реляционной ал­гебры,   в  современных СУБД широкого распространения не получили. Однако знакомство с ней полезно для понимания сути реляционных операций, выражаемых другими  используемыми языками.

Вариант реляционной алге­бры, предложенный Э.Ф. Код- дом (E.F. Codd), включает в себя следующие основные операции:  объединение, разность (вычитание), пересечение, де­картово (прямое) произведе­ние (или произведение), вы­борка (селекция, ограничение), проекция, деление и соединение. Упрощенное графическое представление приведено  на рисунке 1.


Рисунок 1 -  Основные операции реляционной алгебры

По справедливому замеча­нию   К.Дж.   Дейта (C.J.  Date), реляционная алгебра Э. Кодда обладает несколькими недо­статками. Во-первых, восемь перечисленных операций по охвату своих функций, с одной стороны, избыточны, так как минимально необходимый набор составляет пять операций: объединение, вычитание, произведение, проекция и выборка. Три другие операции (пересечение, соединение и деление) можно определить через пять минимально необходимых. Так, на­пример, соединение —это проекция выборки произведения.

Во-вторых, этих восьми операций недостаточно для по­строения реальной СУБД на принципах реляционной алгебры. Требуются расширения, включающие операции: переимено­вание атрибутов, образование новых вычисляемых атрибутов, вычисление итоговых функций, построение сложных алгебра­ических выражений, присвоение, сравнение и т. д.

Рассмотрим перечисленные операции более подробно, сначала —операции реляционной алгебры Э. Кодда, а затем —допол­нительные операции, введенные К. Дейтом. Операции реля­ционной алгебры Э. Кодда можно разделить на две группы:

1) базовые теоретико-множественные и специальные ре­ляционные. Первая группа операций включает в себя клас­сические операции теории множеств: объединение, разность, пересечение и произведение.

2) развитие обычных теоретико-множественных операций в направлении к реальным задачам манипулирования данны­ми, в ее состав входят следующие операции: проекция, селек­ция, деление и соединение.

Операции реляционной алгебры могут выполняться над одним отношением (например, проекция) или над двумя отно­шениями (например, объединение). В первом случае операция называется унарной, а во втором —бинарной. При выполне­нии бинарной операции участвующие в операциях отношения должны быть совместимы по структуре.

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

Объединением двух совместимых отношений R1 и R2 оди­наковой размерности (R1 UNION R2) является отношение R, содержащее все элементы исходных отношений (за исключе­ием повторений).

Пример: пусть отношением RI будет множество постав­щиков из Москвы, а отношение R2 —множество поставщиков, которые поставляют деталь P1. Тогда отношение R обозначает поставщиков, находящихся в Москве, или поставщиков, вы­пускающих деталь P1, либо тех и других.

П#

Имя

Статус

Город_П

S1

Сергей

20

Москва

S4

Николай

20

Москва

R2

П#

Имя

Статус

Город_П

S1

Сергей

20

Москва

S2

Иван

10

Киев

R (R1 UNION R2)

П#

Имя

Статус

Город_П

S1

Сергей

20

Москва

S2

Иван

10

Киев

S4

Николай

20

Москва

Вычитание совместимых отношений R1 и R2 одинаковой размерности (R1 MINUS R2) есть отношение, тело которого состоит из множества кортежей, принадлежащих R1, но не принадлежащих  отношению  R2.  Для  тех  же  отношений  R1 и R2 из предыдущего примера отношение R будет  представлять собой множество поставщиков, находящихся в Москве, но не выпускающих деталь Р 1 , т. е. R = {(54, Николай, 20, Москва)}.

Заметим,   что   результат   операции   вычитания   зави­сит от  порядка  следования  операндов,  т.  е.  R1 MINUS R 2 и R 2 MINUS R 1 — не одно и то же.

Пересечение двух совместимых отношений R 1 и R 2 оди­наковой размерности (R1 INTERSECT R 2 ) порождает отноше­ние R с телом, включающим в себя кортежи, одновременно принадлежащие обоим исходным отношениям. Для отноше­ний R1 и R 2 результирующее отношение R будет означать всех производителей из Москвы, выпускающих деталь P1 . Тело от­ношения R состоит из единственного элемента (S1, Сергей, 20, Москва).

Произведение отношения R 1 степени к1 и отношения R 2 степени k2 (R1 TIMES R 2 ) , которые  не  имеют  одинаковых имен атрибутов, есть такое отношение R степени (k1 + k2) , заголовок которого представляет сцепление заголовков отношений R1 и R 2 , а тело — имеет кортежи, такие, что первые k1 элементов кортежей принадлежат  множеству  R1,  а последние к 2 элементов — множеству R2.При необходимости получения произведения двух отношений, имеющих одинаковые имена одного или нескольких атрибутов, применяется операция пе­реименования RENAME, рассматриваемая далее.

Пример: пусть отношение R I представляет собой множе­ство номеров  всех текущих поставщиков  {S1,  S2,  S3,  S4,  S5}, а отношение  R 2   — множество  номеров  всех текущих деталей { Р1 ,  Р2 , Р З , Р4, Р5 , P6}. Результатом операции  R 1   TIMES R 2 является множество всех пар типа «поставщик—деталь», т. е. {(S1, Р 1 ) , (S1, Р 2 ) , (S1, P 3 ) , (S1, Р4), (51, Р 5 ) , (51, Р6 ) , (S2, Р 1 ) ... (S5, Р6 ) } .

Заметим, что в теории множеств результатом операции прямого произведения является множество, каждый элемент которого является парой элементов, первый из которых при­надлежит R \ , а второй — R 2 . Поэтому кортежами декартова произведения бинарных отношений будут кортежи вида:  ((а, б), (в, г)), где кортеж (а, б) принадлежит отношению R1, а кортеж (в, г) — отношению R2. В реляционной алгебре при­меняется расширенный вариант прямого произведения, при котором элементы кортежей двух исходных отношений слива­ются, что при записи кортежей результирующего отношения означает удаление лишних скобок, т. е. (а, б, в, г).

Выборка (R WHERE f) отношения R по формуле f пред­ставляет собой новое отношение с таким же заголовком и телом, состоящим из таких кортежей отношения R, которые удовлетворяют истинности логического выражения, заданного формулой f Для записи формулы используются операнды — имена атрибутов (или номера столбцов), константы, логиче­ские операции (AND - И, OR - ИЛИ, NOT - НЕ), операции сравнения и скобки.

Примеры . Выборка.

Р WHERE Вес < 14


Д#

Название

Тип

Вес

Город_Д

Р1

Гайка

Каленый

12

Москва

Р5

Палец

Твердый

12

Киев

SP WHERE П# = "SI" AND Д# = "Р1"

П#

Д#

Количество

S1

Р1

300

Проекция   отношения   А  на  атрибуты   X,    Y,         Z  (А[Х, Y,..., Z]), где множество {X, Y, ..., Z) является подмножеством полного списка атрибутов заголовка отношения А, представ­ляет собой отношение с заголовком X, Y,  ..., Z и телом, со­держащим кортежи отношения А, за исключением повторяю­щихся кортежей. Повторение одинаковых атрибутов в списке X, Y, ..., Z запрещается.

Операция проекции допускает следующие дополнительные варианты записи:

- отсутствие списка атрибутов подразумевает  указание всех атрибутов (операция тождественной проекции);

- выражение вида 7?[ ] означает пустую проекцию, результатом которой является пустое множество;

- операция проекции может применяться к произвольно­му отношению, в том числе и к результату выборки.

Пример.  Проекция

Р [Тип, Город_Д]                                                                                                                                    

Тип

Город_Д

Каленый

Москва

Мягкий

Киев

Твердый

Ростов

Твердый

Киев

(S WHERE Город_П="Киев")

П

Город_П

S2

Киев

S3

Киев

 


Результатом деления отношения R1 с  атрибутами  А  и  В на отношение R2 с атрибутом В (R1 DIVIDEBY R2), где А и В простые или составные атрибуты, причем атрибут В — общий атрибут, определенный на одном и том же домене (множестве доменов составного атрибута), является отношением R с заго­ловком А и телом, состоящим из кортежей r таких, что в отношении R1  имеются  кортежи (r, s),  причем множество значений s включает множество значений атрибута В отношения R2.

R1

П

Д

S1

P1

S1

Р2

S1

РЗ

S1

Р4

S1

Р5

S1

Р6

S2

Р1

S2

Р2

S3

Р2

S4

Р2

S4

Р4

                      

 R2                        

П

S1

S4

Rl DIVIDEBY R2

Д

Р2

Р4

 

 


 


Соединение   Cf(R1,  R2)   отношений  R1  и  R2  по условию, заданному формулой f представляет собой отношение R, ко­торое можно получить путем декартова произведения отноше­ний R 1 и R2 с последующим применением к результату опера­ции выборки по формуле f. Правила записи формулы f такие же, как и для операции селекции.

Важными с практической точки зрения частными слу­чаями соединения являются эквисоединение и естественное соединение.

Операция эквисоединения характеризуется тем, что форму­ла задает равенство операндов. Иногда эквисоединение двух отношений выполняется по таким столбцам, атрибуты кото­ рых в обоих отношениях имеют соответственно одинаковые имена и домены. В этом случае говорят об эквисоединении по общему атрибуту.

Операция естественного соединения (join) применяется к двум отношениям, имеющим общий атрибут. Этот атрибут в отношении имеет одно и то же имя и определен на одном  и том же домене.

Результатом операции естественного соединения является отношение R, которое представляет собой проекцию эквисосдинения отношений R1 и R2 по общему атрибуту на объеди­ненную совокупность атрибутов обоих отношений.