Лекция 8

реляционная алгебра (алгебра отношений);
2) реляционное исчисление (исчисление отношений).
Реляционная алгебра

Оба механизма обладают одним важным свойством: они замкнуты относительно понятия отношение. Это означает, что выражения РА и формулы РИ определяются над отношениями РБД и результатом вычисления также являются отношения.
В результате любое выражение и любая формула могут интерпретироваться как отношение, что позволяет использовать их в других выражениях и формулах.

большой выразительной мощностью: очень сложные запросы к БД могут быть

Механизмы РА и РИ эквивалентны, т.е. для любого допустимого выражения РА можно построить эквивалентную (по результату) формулу РИ, и наоборот.

На основе реляционной алгебры и реляционного исчисления строятся языки баз данных.
Конкретный язык манипулирования РБД называется реляционно-полным, если любой запрос, представленный с помощью одного выражения РА или одной формулы РИ, может быть выражен с помощью одного оператора этого языка.

эквивалентны, то для проверки степени реляционности языка РБД можно использовать

Для чего же нужны два эквивалентных формализма? Дело в том, что РА и РИ отличаются уровнем процедурности.

Выражения РА строятся на основе алгебраических операций и имеют процедурную интерпретацию.

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

(аналогично процедурным языкам программирования таким, как Паскаль или Си), описывает

Обычно языки БД основываются на смеси РА и РИ. Здесь учитывается удобство для пользователя – как ему удобней и привычней представлять свои запросы.

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

Расширенный вариант РА, предложенный Коддом, включает
8 основных алгебраических операций и 2 дополнительные.
Весь набор включает два класса – теоретико-множественные операции и специальные реляционные операции.

отношений,
пересечение отношений,
взятие разности отношений,
прямое произведение отношений.

Теоретико-множественные операции обладают свойством ассоциативности

включающее кортежи, входящие хотя бы в одно из отношений-операндов.
2. Пересечение

Результат пересечения двух отношений – это отношение, включающее все кортежи, входящие в оба отношения-операнда одновременно.

кортежи, входящие в отношение-первый операнд, такие что ни один из

Замечание.
При выполнении операций объединения, пересечения и разности отношений отношения-операнды должны быть совместимы по этим операциям, т.е. должны обладать одинаковыми заголовками.
Более точно: в заголовках обоих отношений содержится один и тот же набор имен атрибутов и одноименные атрибуты определены на одном и том же домене. Только в этом случае результатом этих трех операций является отношение с корректно определенным заголовком, совпадающим с заголовком каждого из отношений-операндов.
Если два отношения "почти" совместимы, т.е. совместимы во всем, кроме имен некоторых атрибутов, то перед выполнением операций эти отношения можно сделать совместимыми путем применения операции переименования (см. дальше).

двух множеств A и B (AB) есть множество C =

и своей схемой (заголовком).
В случае прямого произведения отношение должно

Любые два отношения могут быть сделаны совместимыми по взятию расширенного прямого произведения путем применения операции переименования к одному из этих отношений.

ограничение отношений,
проекция отношений,
соединение отношений,
деление отношений.

операндом-отношением и включает простое условие ограничения
A WHERE comp,
где A –

Результатом выполнения операции ОО является отношение, заголовок которого совпадает с заголовком отношения-операнда, а в тело входят те кортежи отношения-операнда, для которых значением условия ограничения является true (истина).

Приведем пример операции ограничения отношений:
НЕСОВЕРШЕННОЛЕТНИЙ = СТУДЕНТ WHERE СТУДЕНТ.ВОЗРАСТ < 18

Тогда по определению
(1) A WHERE comp1 AND comp2 эквивалентно (A

(2) A WHERE comp1 OR comp2 эквивалентно (A WHERE comp1)  (A WHERE comp2);

(3) A WHERE NOT comp эквивалентно A \ (A WHERE comp).

Благодаря этому, можно формулировать операции ОО, в которых условием ограничения является любое булево выражение, составленное из простых условий с использованием логических связок AND, OR, NOT и скобок.

некоторой горизонтальной вырезки отношения-операнда

проецируемого отношения A и списка имен атрибутов, входящих в его

Результатом проекции отношения A по списку атрибутов (a1, a2, ... am) является новое отношение B с заголовком, определяемым множеством атрибутов (a1, a2, ... am), и телом, состоящим из кортежей вида < a1 : v1, a2 : v2 , ... am : vm >, таких что в отношении A имеется кортеж, атрибут a1 которого имеет значение v1, a2 – v2, ... am – vm.

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

отношение
СЛУЖ (Номер_Сл, Имя_Сл, Номер_Отд, Зарплата)
оператором
СЛУЖ = П СЛУЖАЩИЙ

Аналогично, отношение
ОТДЕЛ (Номер_Отд, Адрес)

можно получить с помощью оператора
ОТДЕЛ = П СЛУЖАЩИЙ (Номер_Отд, Адрес).

них – соединяемые отношения, третий – простое условие.
Эта операция

A, B WHERE comp,
где A, B – соединяемые отношения,
comp – простое условие вида a  b или a  const, где a, b – имена атрибутов соответственно из A и B, а const – константа.

По определению результатом операции соединения является отношение, получаемое путем выполнения операции ограничения по условию comp прямого произведения отношений A и B.

это соединение, где условие соединения имеет вид (a = b),

Операция естественное соединение применяется к паре отношений A и B, обладающих общим, возможно составным, атрибутом c
(атрибут c имеет одно и то же имя и определен на одном и том же домене).

отношения. Только теперь будет решаться обратная задача: из отношений СЛУЖ

что основный смысл операции естественного соединения – это обеспечение возможности

с заголовком {a1 , a2 ,... an , b1 ,

Назовем множество атрибутов {a1, a2 ,... an} составным атрибутом a, а множество {b1, b2, ... bm} составным атрибутом b. Тогда можно говорить о реляционном делении бинарного отношения A(a ,b) на унарное отношение B(b).

Результатом деления A на B является унарное отношение C(a), состоящее из кортежей , таких что в A имеются кортежи , такие что для каждого w в B есть кортеж .

ИМЕНА (Имя), причем унарное отношение ИМЕНА содержит фамилии всех сотрудников

Тогда в результате деления отношения СОТРУДНИКИ на отношение ИМЕНА получим унарное отношение, содержащее номера отделов, в которых работают сотрудники, чьи фамилии включены в отношение ИМЕНА.

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

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

и правильно построенная формула (далее – ППФ).
В зависимости от

Для определения кортежной переменной используется оператор RANGE, например,
RANGE СОТР IS СОТРУДНИКИ,
где СОТР – переменная, СОТРУДНИКИ – отношение, на котором определена переменная СОТР.

В любой момент переменная СОТР представляет некоторый кортеж отношения СОТРУДНИКИ.

значения атрибутов переменной, например, СОТР.ИМЯ.
Правильно построенная формула служит для выражения

F и Q – формулы, то NOT F, (F AND

О переменных говорят, что они либо свободные, либо связанные. Переменные, входящие в ППФ без кванторов, являются свободными. Только свободные переменные могут входить в результирующее отношение.

Переменные под квантором являются связанными. Это означает, что такая переменная связана с данной ППФ, т.е. не видна за ее пределами. При вычислении значения такой ППФ используется не одно значение связанной переменной, а вся ее область определения.

на отношении СОТРУДНИКИ, тогда ППФ
EXISTS СОТР2 (СОТР1.Сотр_Зарп > СОТР2.Сотр_Зарп)

Формула
FORALL СОТР2 (СОТР1.Сотр_Зарп > СОТР2.Сотр_Зарп)
для текущего кортежа переменной СОТР1 принимает значение true в том и только том случае, если для всех кортежей отношения СОТРУДНИКИ (связанных с переменной СОТР2) значение атрибута Сотр_Зарп удовлетворяет внутреннему условию сравнения.

связанных переменных, а о свободных и связанных вхождениях переменных.
Так,

Рассмотрим следующую формулу:
EXISTS СОТР2 (СОТР1.Сотр_Отд_Ном = СОТР2.Сотр_Отд_Ном) AND FORALL СОТР2 (СОТР1.Сотр_Зарп > СОТР2.Сотр_Зарп).

Здесь мы имеем два связанных вхождения переменной СОТР2 с совершенно разным смыслом.

средства формулирования условий выборки кортежей из отношений БД. Для определения

Целевой список строится из целевых элементов следующего вида:
x.attr, где x – имя свободной переменной из ППФ, а attr – имя атрибута отношения, на котором определена x;
x, что эквивалентно наличию подсписка x.attr1 ... x.attrn, где attr1 ... attrn включает все имена атрибутов определяющего отношения;
new_name = x.attr, где new_name – новое имя соответствующего атрибута результирующего отношения.

Последний элемент требуется, когда в ППФ используется несколько свободных переменных с одинаковой областью определения.

является отношение, тело которого определяется ППФ, а набор атрибутов и

Пример: пусть мы имеем БД со схемой
СОТРУДНИКИ (Сотр_Ном, Сотр_Имя, Сотр_Зарп, Отд_Ном) ОТДЕЛЫ (Отд_Ном, Отд_Кол, Отд_Нач).
Требуется выдать имена и номера сотрудников, являющихся начальниками отделов с количеством сотрудников больше 50.

операций:
выполнить соединение отношений СОТРУДНИКИ и ОТДЕЛЫ по условию Сотр_Ном

Пример: пусть мы имеем БД со схемой
СОТРУДНИКИ (Сотр_Ном, Сотр_Имя, Сотр_Зарп, Отд_Ном) ОТДЕЛЫ (Отд_Ном, Отд_Кол, Отд_Нач).
Требуется выдать имена и номера сотрудников, являющихся начальниками отделов с количеством сотрудников больше 50.

образом:
SELECT СОТР.Сотр_Ном, СОТР.Сотр_Имя WHERE EXISTS ОТД (ОТД.Отд_Нач = СОТР.Сотр_Ном

Пример: пусть мы имеем БД со схемой
СОТРУДНИКИ (Сотр_Ном, Сотр_Имя, Сотр_Зарп, Отд_Ном) ОТДЕЛЫ (Отд_Ном, Отд_Кол, Отд_Нач).
Требуется выдать имена и номера сотрудников, являющихся начальниками отделов с количеством сотрудников больше 50.

являются не отношения, а домены. Например, переменные ИМЯ и НОМ_СОТР

Основным формальным отличием исчисления доменов от исчисления кортежей является наличие в ППФ дополнительных предикатов, позволяющих выражать условия членства. В остальном формулы и выражения исчисления доменов похожи на формулы и выражения исчисления кортежей.

, a2 ,... an , то условие членства имеет вид

Условие членства истинно, если в отношении R существует кортеж, содержащий указанные значения атрибутов.

Исчисление доменов проиллюстрируем на примере следующего запроса: Выдать номера и имена сотрудников, получающих зарплату больше минимальной.

имена которых совпадают с именами атрибутов отношения СОТРУДНИКИ; если требуется

SELECT Сотр_Ном, Сотр_Имя WHERE EXISTS Сотр_Зарп1 ( СОТРУДНИКИ (Сотр_Зарп1) AND СОТРУДНИКИ (Сотр_Ном, Сотр_Имя, Сотр_Зарп) AND Сотр_Зарп > Сотр_Зарп1).

Заметим, что на исчислении доменов базировался известный язык Query-by-Example.