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

работы с отношениями.
Основная идея РА Кодда состоит в том,

что коль скоро отношения являются множествами, то средства манипулирования отношениями могут бази­роваться на традиционных теоретико-множественных операциях.
Каждая операция этой алгебры использует одну или несколько таблиц (отношений) в качестве ее операндов и получает в результате новую таблицу, т.е. позволяет " разрезать" или " склеивать" таблицы (рис. 1).
В качестве исходных операндов и результатов будут рассматриваться РТ. Они должны удовлетворять основным условиям РТ:
не допускается повторение имен полей;
не допускается дублирование записей.

разделить на два класса:
теоретико-множественные операции;
специальные реляционные операции.
В состав

теоретико-множественных операций входят традиционные операции над множествами:
объединение;
пересечение;
взятия разности (разность);
прямое произведение.

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

они об­ладают некоторыми особенностями.
Реляционные операторы обладают одним важным свойством:

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

и бинарные операции. Унарная операция использует в качестве операнда одну

таблицу, а бинарная – две. В результате операции получаем новую таблицу. Как будет показано позже, результат может сохраняться не только как реальная РТ, но и как виртуальная таблица в виде представления или запроса. Рассмотрим основные реляционные операции на примерах.

Реляционная алгебра. Унарные операции

Сначала рассмотрим унарные операции с одной РТ. В качестве исходной РТ будем оперировать с данными о сотрудниках, которые хранятся в тСотрудники:

Рk
Результатом операции переименования является таблица, тело которой сов­падает с телом

исходной тА, а имена полей изменены.
В приведенном примере поле P1 получит новое имя Pk.

Операция переименования атрибутов, дающая возможность корректно сформировать заголовок (схему) результирующего отношения (A RENAME X AS Y)

Эта операция допускает множественность, а именно
тА RENAME Р1 AS Рk, Р2 AS Рm, Р3 AS Рn
В результате такой операции поля Р1, Р2, Р3 таблицы тА соответственно переименуются в поля Рk, Рm, Рn.

Реляционная алгебра. Унарные операции

Подразделение и Фамилия их сокращенными именами – П и Фам

соответственно:
тСотрудники RENAME Подразделение AS П, Фамилия AS Фам

Результат можно рассматривать как виртуальную таблицу.

данных результаты вычисления алгебраических выражений (A:= B)
Иногда удобнее не изменять

исходные таблицы, которые могут понадо­биться впоследствии, а формировать на их основе новые:
тВ : = тА.
Такая запись означает, что значения таблицы-источника тА полностью за­меняют значения базовой таблицы-приемника тВ. Результатом операции присваивания будет новая тВ, тело которой совпадает с телом исходной тА, имена полей тоже не изменяются. Таким образом, получим две одинаковые таблицы тА и тВ.

сохранять результаты вычисления реляционных выражений в существующей РТ. При наличии

выражений в правой части сначала происходит вычисление значений, а затем эти значения запоминаются в новой таблице. Поэтому присваивание иногда формули­руют следующим образом: “сохранить как”.
Сохраним результаты предыдущей операции переименования в тС:
тС:= тСотрудники RENAME Подразделение AS П, Фамилия AS Фам
Переименование рекомендуется применять при создании интерфейса пользователя на языке, отличном от языка именования объектов БД.

дополненное атрибутом, значения которого получены посредством некоторых скалярных вычислений.
EXTEND

тА ADD <выр> AS Z,
где выр – скалярное выражение.
Результатом операции будет таблица с заголовком, эквивалентным заго­ловку тА, расширенному новым полем Z. Значения этого поля Z рассчитываются вычислением скалярного <выр> для каждой записи тА.
При этом исходная тА не должна иметь поле Z, а <выр> не должно ссы­латься на поле Z. Число записей новой таблицы равно числу записей исходной, а количество полей увеличивается на единицу.
Данная операция обеспечивает возможность построчного вычисления зна­чений нового поля РТ. Это поле можно использовать в дальнейшем при выполнении других операций.

ADD AS Z1, AS Z2…
В этом случае одновременно

добавляется несколько полей. При этом каж­дое последующее выражение может ссылаться на ранее определенное поле, например, <выр2> может содержать поле Z1.
Рассмотрим пример расчета табельного номера (Таб_н)
тE := EXTEND тС ADD П*100+Код AS Таб_н

которой к полям тС добавляется новое поле Таб_н. Значение этого

поля для каждой записи вычисляется по значениям существующих полей.
Операция расширения позволяет проводить вычисления по записям РТ.
Далее преобразуем тЕ, исключим поле Код, а поле Таб_н переместим на первое место. Для этого применим операцию проекции
тСТ := тЕ [ Таб_н, П, Фам, Пол]

используется дополнительная операция подве­дения итогов, которая дает возможность разбивать множество

кортежей отношения на группы в соответствии с содержимым одного или нескольких атрибутов, и внутри каждой группы применять определенный оператор агрегирования (аналог операции GROUP BY в языке SQL).
Операторы агрегирования предназначены для подведения итогов в определенном столбце таблицы – отношения, например, для нахождения суммарных, средних, минимальных и максимальных значений (SUM, AVG, MIN, MAX, COUNT).

SUMMARIZE <реляционное выражение> BY (атрибуты) ADD <функция агрегирования> AS <новое имя атрибута>

(P#) ADD SUM(QTY) AS TOTAL_QTY
Отношение SP Результат


Рассмотрим пример2
тS := SUMMARIZE тСТ

BY (П) ADD COUNT AS Кол_во

(P#) ADD SUM(QTY) AS TOTAL_QTY
Отношение SP Результат


Рассмотрим пример2
тS := SUMMARIZE тСТ

BY (П) ADD COUNT AS Кол_во

Таблица отражает количество сотрудников, работающих в разных подразделениях, в виде скалярных чисел.

Pi,…,Pк, принадлежащим исходной таблице, называется таблица с заголовком Pi,…,Pк и

телом, содержащим множество соответствующих значений из всех записей ис­ходной тA.
Проекция записывается так:
тА [Pi,…,Pк]
Здесь и далее считаем, что 1<=i<=n, 1<=к<=n.

Тем самым, при выполнении операции проекции получается «вертикальное» подмножество данного отношения, то есть подмножество, получаемое исключением всех атрибутов, отношения-операнда с естественным уничтожением потенциально возникающих кортежей-дубликатов.
Проекция дает возможность получить вертикальное подмножество записей.

.

A [CITY]

полям Код и Фам.
тПр:=тС [Код, Фам]
Видно, что проекция позволяет

отобрать из таблицы требуемые столбцы и исключить ненужные. В примере из тС исключены два поля – П и Пол. Иногда удобно указывать не тот список полей, по которым берется проекция, а те поля, которые исключаются из исходной таблицы. В нашем примере можно сказать так: “тПр – это проекция, исключающая поля П и Пол из тС”.
Определим еще одну проекцию тС по полям Пол и Фам.
тПр2:=тС [Пол,Фам]

ограничение отношения) - создает новое отношение, содержащее только те строки

отношения – операнда, которые удовлетворяют некоторому условию ограничения. Результатом ограничения тА по некоторому условию называется таблица, у которой такой же заголовок, что и у тА, а тело состоит из такого множества всех записей исходной тА, которые удовлетворяют заданному условию.
Операцию ограничения можно записать в виде выражения:
A WHERE X θ Y
где θ – любой скалярный оператор сравнения;
X,Y – операнты.

могут использоваться поля таблицы, один из операндов может заменяться скалярным

или литеральным значением. При этом оба операнда должны быть определены на одном домене, а оператор должен иметь смысл для этого домена.
С помощью ограничения можно отобрать из РТ нужные записи и получить горизонтальное подмножество записей.
Покажем применение ограничения для тС. Отберем сотрудников-мужчин.
тСП := тС WHERE Пол=”М”
Поле Пол может принимать литеральное (текстовое) значение, поэтому значение для условия операции взято в кавычки

θ-выборкой, а условия ограничения – условиями выборки, где θ означает

любой скалярный оператор сравнения ( =, ≠, ≤, ≥ ).

Пример операций выборки

Отношение А

A where CITY = 'Москва' and AGE < 40

A where CITY = 'Москва'

операторы стали применять на практике для выполнения действий над РТ,

а именно обновления данных и удаления записей.

Оператор обновления имеет вид
UPDATE тА Р1:=выр1,…, Pk:=вырK,…, Рn:=вырN,
где значение каждого из полей Рk является результатом вычисления скаляр­ного выражения вырK. Все записи в таблице обновляются в соответствии с указанными операторами присвоения.
Переведем сотрудников из цеха 2 в цех 3.
UPDATE тСТ WHERE П=2 П:=3
Эта операция позволила перевести одного сотрудника из цеха 2 в цех 3.

DELETE тА
Этот оператор позволяет удалить из таблицы те

записи, для которых выполняется заданное выражение <выр>. Удалим записи о сотрудниках, которые работают в цехе 3.
DELETE тСТ WHERE П=3
Этот оператор удалит одну запись о сотруднике, который работал в цехе 3.
В указанных операциях выражение <выр> часто является просто ограничи­вающим условием для таблицы. Нужно также обратить внимание, что данные операторы-действия работают с множеством записей.

оператор вставки.

Эта би­нарная операция имеет вид
INSERT INTO

<получатель>.

Здесь <источник> и <получатель> – выражения, представляющие совмес­тимые по типу таблицы. Значение таблицы <источник> вычисляется по выпажению <выр> и все записи результата вставляются в таблицу <получатель>.
Например, операция
INSERT T2 WHERE Количество<3 INTO T3
позволит перенести из таблицы Т2 записи о студентах, изучивших менее трех дисциплин, в таблицу Т3.
В принципе оператор вставки может быть и унарным, если <источник> и <получатель> – это одна и та же таблица.
 

по типу, если у них одинаковые заголовки, а именно:
каждая

из таблиц имеет одно и то же множество полей;
соответствующие поля определены на одном и том же домене.
Такие таблицы иногда называют совместимыми по объединению или просто совместимыми.
Для проведения операций объединения, пересечения и разности необходимо, чтобы исходные таблицы-операнды были совместимости по типу.
Рассмотрим на примерах основные бинарные операции РА. В качестве исходных рассмотрим две таблицы с конкретной смысловой информацией.
 

таблиц можно утверждать следующее:
они имеют ключ (Код);
они состоят из одинакового

числа полей, равного 4;
три первых поля определены на одних и тех же до­менах соответственно.

тСпецподготовка (тСп)

операции РА с этими таблицами не могут быть проведены, потому

что исходные таблицы-операнды несовместимы. Видно, что в таблицах возникает два вида конфликтов:
конфликт имен полей, так как поля имеют разные имена;
конфликт доменов, так как последние (четвертые) поля определены имеют разный смысл (определены на разных доменах).
Прежде чем рассматривать примеры выполнения бинарных операций РА, необходимо разрешить перечисленные конфликты путем достижения совмести­мости исходных таблиц по типу. Для этого выполним преобразования исходных таблиц.
Любые две таблицы могут быть сделаны совместимыми путем применения преобразования к одной из этих таблиц. При этом операция переименования на­ряду с операциями проекции применяется только к одной из таблиц-операндов. Но часто удобнее с целью симметрии произвести двойное преобразование обеих таблиц.
 

таблицам переименование.
тC2 := тСп RENAME Група AS Гр,

Прізвище AS Фам, Середній бал As Балл
тО2 := тО RENAME Группа AS Гр,
Фамилия AS Фам
Теперь в таблицах тС2 и тО2 частично разрешен конфликт имен полей: три поля имеют одинаковые имена. При этом в таблицах осталось по одному полю с различными именами: Балл (тС2) и Комната (тО2). Это числовые поля, относящиеся к разным доменам. Можно было дать им одинаковые имена, например, переименовать поле Комната в Балл, и рассматривать далее таблицы как совместимые. Однако при этом был бы нарушен смысл доменов.

приведем таблицы к полной совместимости путем исключения полей Балл и

Комната из дальнейшего рассмотрения.
Для этого применим проекцию к таблицам тС2 и тО2
тА:=тС2 [Код, Гр, Фам]
тВ:=тО2 [Код, Гр, Фам]
Теперь тА и тВ совместимы.
С ними без проблем могут быть вы­полнены основные теоретико–множественные операции РА.

А и В (А ∪ В) называется отношение с тем

же заголовком, как в отношениях А и В, и с телом, состоящим из множества кортежей t, принадлежащих А или В или обоим отношениям.
А ∪ В
При выполнении операции объединения двух отношений создается отношение, включающее кортежи, входящие хотя бы в одно из отношений-операндов. Обратите внимание, что повторяющиеся кортежи удаляются по определению отношения
Объединение двух совместимых таблиц тА и тВ – это таблица, у которой такой же заголовок, что и у исходных таблиц-операндов, а тело состоит из таких записей, которые входят хотя бы в одну из исходных таблиц (или в тА или в тВ).
В общем виде объединение записывается так
тA UNION тB
 

иметь вид

тU: =тA UNION тB

Таблица тU представляет информацию о всех

студентах: или обучающихся на военной кафедре, или живущих в общежитии (или, или).
При выполнении объединения существует возможность появления повто­ряющихся записей. Они должны быть исключены.
Из таблицы тU исключена повторяющаяся запись (Андреев).

и В (А ∩ В) называется отношение с тем же

заголовком, как в отношениях А и В, и с телом, состоящим из множества кортежей t, принадлежащих одновременно обоим отношениям А и В. Операция пересечения двух отношений создает отношение, включающее все кортежи, входящие в оба отношения-операнда.

А ∩ В

Отношение А

Отношение В

s - ИЗДЕЛИЕ 2

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

и В (А − В) называется отношение с тем же

заголовком, как в отношениях А и В, и с телом, состоящим из множества кортежей t, принадлежащих отношению А и не принадлежащих отношению В.
Отношение, являющееся разностью двух отношений, включает все кортежи, входящие в первое отношение, такие, что ни один из них не входит во второе отношение.

А - В

Отношение А

Отношение В

s - ВОЗМОЖНОСТИ

Пусть отношение r представляет потребности в некоторых видах деталей, а отношение s — сведения о тех видах деталей, которые фирма может произвести сама, тогда отношение t = r—s содержит сведения о тех видах деталей, которые нужно приобрести.

t= г- s

t = r—s

то и для любых двух таблиц возможно получение прямого произведения.

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

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

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

Декартово произведение двух отношений А и В (А × В), где А и В не имеют общих имен атрибутов, определяется как отношение с заголовком, представляющим собой сцепление двух заголовков исходных отношений А и В, и телом, состоящим из множества кортежей t таких что первым, является любой кортеж отношения А, а вторым – любой кортеж, принадлежащий отношению В. Кардинальное число результирующего отношения равно произведению кардинальных чисел исходных отношений, а степень равняется сумме степеней.

отношение А – содержит имена всех текущих поставщиков, а отношение

В – номера всех текущих деталей. Тогда А × В – это все текущие пары поставщик – деталь и деталь – поставщик.

Отношение В

Отношение А

А × В

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

таблиц обладают свойствами ассоциативности и коммутативности. Если обозначить указанные операции

как ОП, то можно записать следующие эквивалентные выражения:
Для свойства ассоциативности
тA ОП ( тB ОП тF )  тA ОП тB ОП тF (эквиваленты)
Для свойства коммутативности
тA ОП тB  тB ОП тA (эквиваленты )
Если обозначить через s условия выборки, то можно записать тождества, которые верны для выборки:
A WHERE s1 AND s2 = (A WHERE s1) INTERSECT (A WHERE s2)
A WHERE s1 OR s2 = (A WHERE s1) UNION (A WHERE s2)
A WHERE NOT s = A MINUS (A WHERE s)
Эти тождества подтверждают, что условие выборки мо­жет содержать произвольное число логических сочетаний простых сравнений.

новое отношение, каждый кортеж которого является результатом сцепления кортежей операндов

(исходных отношений).
Соединение имеет две разновидности: естественное соединение и соединение по условию (θ - соединение).

Пусть X={X1, X2, …, Xm}, Y={Y1, Y2, …, Yn}, Z={Z1, Z2, …, Zk}.
Естественным соединением отношений A(X,Y) и B(Y,Z) (A JOIN B) называется отношение с заголовком {Х, Y, Z} и с телом, содержащим множество всех кортежей вида <Х:x, Y:y, Z:z> таких, для которых в отношении A значение атрибута Х равно x, а значение атрибута Y равно y, и в отношении В значение атрибута Y равно y, а атрибута Z равно z. При естественном соединении производится сцепление строк операндов соединения по общим атрибутам.

А (поставщики)

Отношение В (детали)

A JOIN B

Пусть отношения А и В не имеют общих имен атрибутов

и определяется так же, как в операции выборки.
θ – соединением(Тета) отношения А по атрибуту X с отношением В по атрибуту Y называется результат выражения (A×B) WHERE X θ Y.
θ - соединение – это отношение с тем же заголовком, что и при декартовом произведении отношений А и В, и с телом, содержащим множество кортежей t ∈ A×B таких, что вычисление условия X и Y дает значение истина для данного кортежа.
Атрибуты X и Y должны быть определены на одном и том же домене, а оператор должен иметь смысл для этого домена.
Таким образом, операция θ -соединение эквивалентна двум операциям: нахождению расширенного декартова произведения двух отношений (при необходимости с переименованием соответствующих атрибутов) и последующему выполнению указанной выборки из полученного результата.

Пример операции θ - соединения.

Отношение А (поставщики)

Отношение В (поставки)
(A×B (RENAME ID_NUM AS AID_NUM) WHERE QTY <200

два операнда - бинарное и унарное отношения. Пусть X={X1, X2,

…, Xm}, Y={Y1, Y2, …, Yn}.
Делением отношений А(Х,Y) на В(Y) (А/В) называется отношение с заголовком {X} и телом, содержащим множество всех кортежей {X:x}, таких что существует кортеж{X:x, Y:y}, который принадлежит отношению А для всех кортежей {Y:y}, принадлежащих отношению В.
Деление отношений создает новое отношение, содержащее атрибуты первого отношения, отсутствующие во втором отношении и кортежи первого отношения, которые совпали с кортежами второго. Для выполнения этой операции второе отношения должно содержать лишь атрибуты, совпадающие с атрибутами первого.
Замечание: Операция деления полезна тогда, когда запрос содержит слово «все».

Отношение В Отношение

В1 Отношение В2