Реляционное исчисление

Большинство работающих языков запросов основано на
реляционном исчислении. Реляционные исчисления — непроцедурные
системы. Исчисления выражают только то, каким должен быть результат
вычисления, но не то, каким образом проводить вычисления. Эта
обязанность возлагается на процессор языка запросов данной СУБД.

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

Реляционное исчисление кортежей является, по сути, формализацией
системы обозначений, предназначенной для образования множеств. В
реляционном исчислении используются булевы операции (И, ИЛИ, НЕ)
над условиями, которые могут быть истинными или ложными. В нем
также используются кванторы существования и всеобщности, означающие, соответственно, что элемент определенного типа существует
или что условие истинно для каждого элемента определенного типа.

Рассмотрим отношение:

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

· операцию Выбор над отношением r, результатом ее применения к
отношению r является другое отношение, которое представляет
собой подмножество кортежей отношения r со значением, равным 2
в атрибуте Вес:

· проецирование результата предыдущей операции на атрибут
Назв_дет.Окончательный результат запроса будет выглядеть
следующим образом:

В реляционном же исчислении формулировка этого запроса должна
иметь следующий вид:
{ t.Назв_дет ⎟ t in r and t.Bec = 2},
где t — это переменная, обозначающая произвольную строку.
Отношение, из которого берется t, определяется выражением “ in r”которое
означает, что t— строка отношения.
t.Назв_дет — значение атрибута Назв_детв строке r; символ (|) —
разделяет целевой список и определяющее выражение. В данном случае:
t.Назв_дет — целевой список;
t in r and t.Bec = 2 — определяющее выражение;
t.Bec = 2 означает, что значение атрибута Весв строке t равно 2.

Фигурные скобки "{}", в которые заключено выражение, определяют
результат запроса, как множество значений данных. Что именно входит в
это множество, описывает выражение в скобках. Приведенное здесь решение иллюстрирует почти все элементы реляционного исчисления.

8.2.1. Целевой список и определяющее выражение
Решением каждого запроса в реляционном исчислении является
отношение, которое задается целевым списком и определяющим
выражением. Целевой список определяет атрибуты отношения решения.
Определяющее выражение — это условие, на основании которого
отбираются значения из базы данных, которые войдут в отношение
решения.

В предыдущем примере Назв_детберется из строки и помешается в
строку решения, если строка t удовлетворяет условию
t in r and t. Вес = 2.

Система просматривает строки отношения r одну за другой. Первой
строке временно присваивается имя t и проверяется истинность
определяющего выражения. Поскольку в этом случае t.Вес = 1,
определяющее выражение, ложно, поэтому А — значение атрибута t.Hазв_дет в этой строке не помещается в отношение решения. Затем система переходит к следующей строке, дает ей имя t и снова проверяет истинность определяющего выражения. На этот раз выражение истинно, поэтому Д помещается в отношение решения. Процесс повторяется для каждой строки отношения r. В результате получается следующее
отношение, идентичное полученному ранее:

Целевой список может состоять из нескольких атрибутов,
разделенных запятыми.
{t.Код_дет, t.Назв_дет, t.Вес ⎟ t in r and t.Bec = 2}.
Рассмотрим еще один пример. Пусть даны отношения:

Согласно алгебраическому выражению πНазв_дет(r ∩ s) реляционной
алгебры, содержащему операции пересечения и проецирования, получим
отношение:

В реляционном же исчислении, если t кортеж r, а у кортеж s, этот
запрос может включать в себя следующие компоненты:
t.Назв_дет - целевой список;
t in r and у in s and t.Кoд_дет = у.Код_дет and t.Bec = у.Вес and
t.Hазв_дет = у.Назв_дет — определяющее выражение.
В рассмотренных примерах были использованы операции выбора,
пересечении и проецирования реляционной алгебры. Аналогично можно
получить конструкции реляционного исчисления, соответствующие ряду
других операций: объединению, разности и произведению.

Несколько иначе выглядят аналоги только двух операций
реляционной алгебры — операций соединения и деления. Для построения
аналогов этих операций требуются кванторы: квантор существования для соединения и квантор всеобщности для деления.

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

101
Запрос: Перечислить названия деталей, потребности в которых
покрываются деталями, хранящимися на складе.
Очевидно, что решением этой задачи будет отношение, содержащее
названия некоторых деталей. Это отношение состоит из одного столбца,
так что в этом случае целевым списком является:
t.Назв_дет,
где t— строка из отношения ПОТРЕБНОСТИ.
Пусть s — строка отношения СКЛАД.
Формирование определяющего выражения осуществляется, исходя
из следующего. Для того чтобы деталь вошла в отношение решения,
должно удовлетворяться условие, что на складе эта деталь имеется в
достаточном количестве. Другими словами, если Код_детвстречается в
строке отношения СКЛАДс Кол_дет > Количествов строке отношения
ПОТРЕБНОСТИ , то эта деталь должна быть включена в решение. Таким
образом, условие таково: существует хотя бы одна строка в отношении СКЛАД, содержащая требуемый Код_дет и где s.Кол_дет > t.Количество.
Это формируется следующим образом:
exists s in СКЛАД
(s.Код_дет = t.Код_дет and s.Кол дет > t.Количество).
Такое выражение читается: "Существует строка s в отношении
СКЛАДтакая, что s.Код_дет = t.Код_дет и s. Код_дет > t.Количество".
Приведенное выражение определяет строку t. Если оно истинно, то
есть для строки t существует такая строка s, то t.Hазв_дет помещается в
результирующее отношение. Если выражение ложно — то есть такой
строки s не существует — тогда t.Назв_дет не помещается в
результирующее отношение.
Полное решение в реляционном исчислении выглядит следующим
образом:
{t.Назв_дет ⎟ t in ПОТРЕБНОСТИ and exists s in СКЛАД (s.Код_дет =
t.Код_дет and s.Кол_дет > t.Количество )}.

Оно описывает отношение, состоящее из одного столбца и
содержащее названия деталей, взятых из строк отношения
ПОТРЕБНОСТИ. Данное название помещается в отношение решения, если его строка t удовлетворяет условию после знака "⎟".

Рассмотрим подробнее вышеописанный механизм обработки
нескольких строк отношения ПОТРЕБНОСТИ, чтобы понять, как будет
применяться условие.
Первая строка отношения ПОТРЕБНОСТИ(которая обозначена t)
имеет Назв_дет = А, и оно будет помещено в результирующее отношение,
если в отношении СКЛАДсуществует строка, в которой Код_дет= ‘01’, а
Кол_дет > t.Количество. Такая строка действительно существует, и она
обозначена как s. Итак, t удовлетворяет определяющему условию, поэтому
t.Hазв_дет помещается в отношение решения. Этот процесс должен
повториться для каждой строки отношения ПОТРЕБНОСТИ. Когда
закончена обработка первой строки, вторая строка обозначена t, и теперь
уже для нее ищется соответствующая строка s в отношении СКЛАД.
Такой строки не существует, поэтому Д не помещается в результирующее
отношение. Продолжая дальше обработку строк отношений по указанному алгоритму, получим множество решения, которое составит новое
отношение, и будет выглядеть следующим образом:

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

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

Требуется определить фамилии тех студентов, каждый из которых
сдавал все экзамены, перечисленные в отношении RASP. Необходимо
обратить внимание на то, что условие выбора студента содержит
определение каждый. В результирующее отношение нключаются только те
студенты, которые сдавали каждый экзамен. Если взглянуть на
полученный результат, то можно увидеть, что условию запроса
удовлетворяют только два студента.
Полное решение в реляционном исчислении с использованием
квантора всеобщности FORALL таково:
{t.Фамилия | t in VEDOM and s in RASP and
FORALL s {t. Назв_дисц_на = s.Назв_дисц and t.Дата = s.Дата)},
где t — кортеж отношения VEDOM;
s — кортеж отношения RASP.

Имя студента из строки t таблицы VEDOMпомещается в
результирующее отношение, если определяющее выражение истинно для
строки t, а определяющее выражение истинно, если для каждой строки s
отношения RASPдолжна существовать строка t в отношении VEDOM, удовлетворяющая условию, то есть в данном случае для каждой строки s
отношения RASPдолжна существовать строка t в отношении VEDOMс
одной и то же фамилией:
ƒ

· Иванов присутствует в строках t (1) и t (2): t (1) соответствует s (2) и
t (2) соответствует s (1);
ƒ

· Сидоров присутствует в строках t (3) и t (4): t (3) соответствует s (2)
и t (4) соответствует s (1);
ƒ

· Коровин присутствует только в строке t (5): t (5) соответствует s (1),
а для s (2) нет соответствующей строки t.

Полное соответствие всем строкам отношения RASP есть только у
Иванова и Сидорова. Таким образом, они и вошли в результирующее отношение.