6 Манипуляционная составляющая реляционной модели

6.1 Механизмы манипулирования реляционными данными

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

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

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

Но эти два механизма различаются уровнем процедурности:

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

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

Крайне редко алгебра или исчисление принимаются в качестве полной основы какого-либо языка БД. Обычно (как, например, в случае языка SQL) язык основывается на некоторой смеси алгебраических и логических конструкций.

6.2 Введение в реляционную алгебру

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

Опишем начальный вариант алгебры, который был предложен Коддом. В этом варианте набор основных алгебраических операций состоит из восьми операций, которые делятся на два класса - теоретико-множественные операции и специальные реляционные операции. В состав теоретико-множественных операций входят операции: объединения отношений;  пересечения отношений;  взятия разности отношений;  прямого произведения отношений.

Специальные реляционные операции включают:  ограничение отношения;  проекцию отношения;  соединение отношений;  деление отношений.

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

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

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

Отношения будем называть совместимыми по типу, если они имеют идентичные заголовки, а именно:

- отношения имеют одно и то же множество имен атрибутов, т.е. для любого атрибута в одном отношении найдется атрибут с таким же наименованием в другом отношении;

- атрибуты с одинаковыми именами определены на одних и тех же доменах.

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

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

6.3 Общая интерпретация реляционных операций

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

Синтаксис операции объединения: A UNION B.

Замечание. Объединение, как и любое отношение, не может содержать одинаковых кортежей. Поэтому если некоторый кортеж входит и в отношение A, и отношение B, то в объединение он входит только один раз.

Пример. Пусть даны два отношения A и B с информацией о сотрудниках.

Таблица 6.1 - Отношение A
Табельный номер	Фамилия	Зарплата
1	Иванов	1000
2	Петров	2000
3	Сидоров	3000

Таблица 6.2 - Отношение B
Табельный номер	Фамилия	Зарплата
1	Иванов	1000
2	Пушников	2500
4	Сидоров	3000

Объединение отношений A  и B будет иметь вид, представленный в таблице 6.3.

Таблица 6.3 - Отношение A UNION B
Табельный номер	Фамилия	Зарплата
1	Иванов	1000
2	Петров	2000
3	Сидоров	3000
2	Пушников	2500
4	Сидоров	3000

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

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

Синтаксис операции пересечения: A INSERSECT B.

Пример. Для тех же отношений A и B, что и в предыдущем примере пересечение имеет вид, представленный в таблице 6.4.

Таблица 6.4 - Отношение A INTERSECT B
Табельный номер	Фамилия	Зарплата
1	Иванов	1000

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

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

Синтаксис операции вычитания: A MINUS B.

Пример. Для тех же отношений A и B, что и в предыдущем примере вычитание имеет вид, представленный в таблице 6.5.

Таблица 6.5 - Отношение A MINUS B
Табельный номер	Фамилия	Зарплата
2	Петров	2000
3	Сидоров	3000

Декартовым произведением двух отношений A(A₁, A₂,...A_n) и  B(B₁, B₂,...B_n) называется отношение, заголовок которого является сцеплением заголовков отношений A и B: (A₁,A₂,...,A_n,B₁,B₂,...B_n) ,  а тело состоит из строк (кортежей), являющихся сцеплением кортежей отношений  A и B:  (a₁,a₂,...,a_n,b₁,b₂,...,b_n) , таких, что  (a₁,a₂,...,a_n) Î A, (b₁,b₂,...,b_n) Î B.

Синтаксис операции декартового произведения: A TIMES B.

Замечание. Мощность произведения  A TIMES B равна произведению мощностей отношений A и B, т.к. каждая строка отношения  A соединяется с каждой строкой отношения B.

Если в отношения A и B имеются атрибуты с одинаковыми наименованиями, то перед выполнением операции декартового произведения такие атрибуты необходимо переименовать.

Перемножать можно любые два отношения, совместимость по типу при этом не требуется.

Пример. Пусть даны два отношения A и B с информацией о поставщиках и деталях.

Таблица 6.6 - Отношение A (Поставщики)
Номер поставщика	Наименование поставщика
1	Завод 1
2	Завод 2
3	Завод 3

Таблица 6.7 - Отношение B (Детали)
Номер детали	Наименование детали
1	Болт
2	Гайка
3	Винт

Декартово произведение отношений  A и B будет иметь вид, представленный в таблице 6.8.

Таблица 6.8 - Отношение A TIMES B
Номер поставщика	Наименование поставщика	Номер детали	Наименование детали
1	Завод 1	1	Болт
1	Завод 1	2	Гайка
1	Завод 1	3	Винт
2	Завод 2	1	Болт
2	Завод 2	2	Гайка
2	Завод 2	3	Винт
3	Завод 3	1	Болт
3	Завод 3	2	Гайка
3	Завод_3	3	Винт

Замечание. Сама по себе операция декартового произведения для реальных запросов почти никогда не используется. Однако операция декартового произведения важна для выполнения специальных реляционных операций, о которых речь пойдет ниже.

Выборкой (ограничением, селекцией) на отношении A с условием z называется отношение с тем же заголовком, что и у отношения A, и телом, состоящем из строк (кортежей), значения атрибутов которых при подстановке в условие z дают значение ИСТИНА. «Z» представляет собой логическое выражение, в которое могут входить атрибуты отношения A и (или) скалярные выражения.

В простейшем случае условие  c имеет вид XQY, где Q - один из операторов сравнения ( и т.д.), а  X и  Y - атрибуты отношения  A или скалярные значения. Такие выборки называются Q-выборки (тэта-выборки) или Q-ограничения, Q-селекции.

Синтаксис операции выборки: A WHERE z или     A WHERE XQY

Пример. Пусть дано отношение A с информацией о сотрудниках.

Таблица 6.9 - Отношение A
Табельный номер	Фамилия	Зарплата
1	Иванов	1000
2	Петров	2000
3	Сидоров	3000

Результат выборки A WHERE Зарплата <3000 будет иметь вид.

Таблица 6.10 - Отношение A WHERE Зарплата<3000
Табельный номер	Фамилия	Зарплата
1	Иванов	1000
2	Петров	2000

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

Проекция. Результатом проекции отношения A по списку атрибутов a₁, a₂, ..., a_n является отношение, с заголовком, определяемым множеством атрибутов a₁, a₂, ..., a_n, и с телом, состоящим из кортежей вида <a₁:v₁, a₂:v₂, ..., a_n:v_n> таких, что в отношении A имеется кортеж, атрибут a₁ которого имеет значение v₁, атрибут a₂ имеет значение v₂, ..., атрибут a_n имеет значение v_n. Тем самым, при выполнении операции проекции выделяется "вертикальная" вырезка отношения-операнда с естественным уничтожением потенциально возникающих кортежей-дубликатов.

Синтаксис операции проекции: A[X,Y,...,Z].

Пример. Пусть дано отношение A с информацией о поставщиках, включающих их наименование и месторасположение.

Таблица 6.11 - Отношение A (Поставщики)
Номер поставщика	Наименование поставщика	Город поставщика
1	Завод_1	Уфа
2	Завод_2	Москва
3	Завод_3	Москва
4	Завод_4	Челябинск

Проекция А [Город поставщика] будет иметь вид, представленный в таблице 6.12.

Таблица 6.12 - Отношение A[Город поставщика]

Город поставщика

Уфа

Москва

Челябинск

Замечание. Операция проекции дает "вертикальный срез" отношения, в котором удалены все возникшие при таком срезе дубликаты кортежей.

Соединением отношений  A и  B по условию  z называется отношение (A TIMES B) WHERE z, где z представляет собой логическое выражение, в которое могут входить атрибуты отношений  A и B и (или) скалярные выражения.

Таким образом, операция соединения есть результат последовательного применения операций декартового произведения и выборки. Если в отношениях A и B имеются атрибуты с одинаковыми наименованиями, то перед выполнением соединения такие атрибуты необходимо переименовать. Чтобы сделать различными.

Пример. Пусть даны два отношения A и B с информацией о поставщиках и деталях.

Таблица 6.13 - Отношение A (Поставщики)

Номер поставщика	Наименование поставщика
1	Иванов
2	Петров
3	Сидоров

Таблица 6.14 -  Отношение B (Детали)

Номер детали	Наименование детали
1	Болт
2	Гайка
3	Винт

Декартово произведение отношений A и B будет иметь вид.

Таблица 6.15 - Отношение A TIMES B

Номер поставщика	Наименование поставщика	Номер детали	Наименование детали
1	Иванов	1	Болт
1	Иванов	2	Гайка
1	Иванов	3	Винт
2	Петров	1	Болт
2	Петров	2	Гайка
2	Петров	3	Винт
3	Сидоров	1	Болт
3	Сидоров	2	Гайка
3	Сидоров	3	Винт

Если к нему приложить условие «Какие поставщики поставляют болты» то есть  «Какие поставщики поставляют детали с номером 1», то в результате получим отношение.

Таблица 6.16 - Отношение A TIMES B WHERE Номер детали = 1

Номер поставщика	Наименование поставщика	Номер детали	Наименование детали
1	Иванов	1	Болт
2	Петров	1	Болт
3	Сидоров	1	Болт

На практике используются несколько разновидностей операции соединения, отличающиеся немного друг от друга:

- Q-соединение (тэта-соединение);

- экви-соединение  (эквивалентное соединение, частный случай тэта-соединения);

- естественное соединение.

Тэта-соединение

Пусть отношение A содержит атрибут X, отношение  B содержит атрибут Y, а Q - один из операторов сравнения ( и т.д.). Тогда Q-соединением отношения A по атрибуту X с отношением B по атрибуту Y называют отношение (A TIMES B) WHERE XQY.

Иногда для операции Q-соединения применяют следующий, более короткий синтаксис:  A [XQY] B.

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

Таблица 6.17 - Отношение A (Поставщики)

Номер поставщика	Наименование поставщика	Статус поставщика (X)
1	Иванов	4
2	Петров	1
3	Сидоров	2

Таблица 6.18 -  Отношение B (Детали)

Номер детали	Наименование детали	Статус детали (Y)
1	Болт	3
2	Гайка	2
3	Винт	1

Ответ на вопрос "какие поставщики имеют право поставлять какие детали?" дает Q-соединение A [X>=Y].

Таблица 6.19 - Отношение A [X>=Y] B

Номер поставщика	Наименование поставщика	X (Статус поставщика)	Номер детали	Наименование детали	Y  (Статус детали)
1	Иванов	4	1	Болт	3
1	Иванов	4	2	Гайка	2
1	Иванов	4	3	Винт	1
2	Петров	1	3	Винт	1
3	Сидоров	2	2	Гайка	2
3	Сидоров	2	3	Винт	1

Экви-соединение. Наиболее важным частным случаем Q-соединения является случай, когда Q есть просто равенство. То есть если условие соединения имеет вид (X = Y), где X и Y - атрибуты разных операндов соединения.

Синтаксис экви-соединения: A[X=Y]B.

Таблица 6.20 - Отношение A (Поставщики)

Номер поставщика	Наименование поставщика	Статус изделия (X)
1	Иванов	4
2	Петров	1
3	Сидоров	2

Таблица 6.21 - Отношение B (Детали)

Номер детали	Наименование детали	Статус изделия (Y)
1	Болт	3
2	Гайка	2
3	Винт	1

Таблица 6.22 - Отношение A [X=Y] B

Номер поставщика	Наименование поставщика	X (Статус изделия)	Номер детали	Наименование детали	Y  (Статус изделия_1
3	Сидоров	2	2	Гайка	2

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

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

Пусть даны отношения A(A₁,A₂,...,A_n,X₁,X₂,...X_n) и B(X₁,X₂,...X_n,B₁,B₂,. ..,B_n), имеющие одинаковые атрибуты X₁,X₂,...X_n  (т.е. атрибуты с одинаковыми именами и определенные на одинаковых доменах).

Тогда естественным соединением отношений A и B называется отношение с заголовком (A₁,A₂,...,A_n,X₁,X₂,...X_n, B₁,B₂,...,B_m) и телом, содержащим множество строк (кортежей) (a₁,a₂,...,a_n,x₁,x₂,...,x_n,b₁,), таких, что (a₁,a₂,...,a_n,x₁,x₂,...,x_n) Î A и (x₁,x₂,...,x_n,,b_1. b_{2.. . .} b_n ) Î B.

Словами это можно попытаться представить так: <строки> из отношения A <сцепляются> с теми <строками> отношения B, для которых значения одноименных атрибутов совпадают. Естественно, что совпадающие атрибуты включаются в результирующее отношение в единственном экземпляре.

Естественное соединение настолько важно, что для него используют специальный синтаксис: A JOIN B.

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

Можно выполнять последовательное естественное соединение нескольких отношений. Естественное соединение (как, впрочем, и соединение общего вида) обладает свойством ассоциативности, т.е.:

(A JOIN B) JOIN C = A JOIN (B JOIN C)

поэтому такие соединения можно записывать, опуская скобки:

A JOIN B JOIN C.

Пример. Пусть имеются отношения P,  D и PD, хранящие информацию о поставщиках, деталях и поставках соответственно (для удобства введем краткие наименования атрибутов).

Таблица 6.23 - Отношение P (Поставщики)

Номер поставщика (PNUM)	Наименование поставщика (PNAME)
1	Иванов
2	Петров
3	Сидоров

Таблица 6.24 - Отношение D (Детали)

Номер детали (DNUM)	Наименование детали (DNAME)
1	Болт
2	Гайка
3	Винт

Таблица 6.25 - Отношение PD (Поставки)

Номер поставщика  (PNUM)	Номер детали  (DNUM)	Поставляемое количество  VOLUME
1	1	100
1	2	200
1	3	300
2	1	150
2	2	250
3	1	1000

Ответ на вопрос "какие детали поставляются поставщиками", можно записать в виде естественного соединения трех отношений P JOIN PD JOIN D).

Таблица 6.26 - Отношение P JOIN PD JOIN D

Номер поставщика PNUM	Наименование поставщика PNAME	Номер детали DNUM	Наименование детали DNAME	Поставляемое количество VOLUME
1	Иванов	1	Болт	100
1	Иванов	2	Гайка	200
1	Иванов	3	Винт	300
2	Петров	1	Болт	150
2	Петров	2	Гайка	250
3	Сидоров	1	Болт	1000

Деление (division) – это бинарная операция над разносхемными отношениями A и B. Пусть отношение A содержит атрибуты { X₁,X₂,…,X_n,Y₁,Y₂,…,Y_m}, а отношение B – атрибуты {Y₁,Y₂,…,Y_m },  причем атрибуты Y₁,Y₂,…,Y_m  - общие для двух отношений Результирующее отношение содержит атрибуты {X₁,X₂,…,X_n}. Кортеж включается в результирующее отношение, если его декартово произведение с отношением B входит в A.

Либо:

Делением отношений A на  B называется отношение с заголовком (X₁,X₂,…,X_n) и телом, содержащим множество кортежей (x₁,x₂,…,x_n), таких, что для всех кортежей y₁,y₂,…,y_m) Î B в отношении A найдется кортеж  (x₁,x₂,…,x_n,y₁,y₂,…,y_m).

Отношение A выступает в роли делимого, отношение  B выступает в роли делителя. Деление отношений аналогично делению чисел с остатком.

Синтаксис операции деления: A DEVIDBY B

Пример. В примере с поставщиками, деталями и поставками ответим на вопрос, "какие поставщики поставляют все детали?".

В качестве делимого возьмем проекцию X= PD [PNUM, DNUM], содержащую номера поставщиков и номера поставляемых ими деталей.

Таблица 6.27 - Проекция X=PD[PNUM,DNUM]

Номер поставщика  PNUM	Номер детали  DNUM
1	1
1	2
1	3
2	1
2	2
3	1

В качестве делителя возьмем проекцию Y=D[DNUM], содержащую список номеров всех деталей (не обязательно поставляемых кем-либо).

Таблица 6.28 - Проекция Y=D[DNUM]

Номер детали  DNUM

1

2

3

Деление X DEVIDEBY Y дает список номеров поставщиков, поставляющих все детали.

Таблица 6.29 - Отношение X DEVIDEBY Y

Номер поставщика  PNUM

1

Оказалось, что только поставщик с номером 1 поставляет все детали.

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

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

Рассмотрим пример. Пусть даны два отношения:

СОТРУДНИКИ (СОТР_НОМЕР, СОТР_ИМЯ, СОТР_ЗАРПЛ, ОТД_НОМЕР)

ОТДЕЛЫ (ОТД_НОМЕР, ОТД_КОЛ, ОТД_НАЧ)

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

1) выполнить соединение отношений:

СОТРУДНИКИ и ОТДЕЛЫ по условию СОТР_НОМ = ОТДЕЛ_НАЧ.

С1 = СОТРУДНИКИ [СОТР_НОМ = ОТД_НАЧ] ОТДЕЛЫ

2) из полученного отношения произвести выборку по условию ОТД_КОЛ > 10:

С2 = С1 [ОТД_КОЛ > 10].

3) спроецировать результаты предыдущей операции на атрибуты:

СОТР_ИМЯ, СОТР_НОМЕР

С3 = С2 [СОТР_ИМЯ, СОТР_НОМЕР]

Заметим, что порядок выполнения шагов может повлиять на эффективность выполнения запроса. Так,  время выполнения приведенного выше запроса можно сократить, если поменять местами этапы (1) и (2). В этом случае сначала из отношения СОТРУДНИКИ будет сделана выборка всех кортежей со значением атрибута ОТДЕЛ_КОЛ > 10, а затем выполнено соединение результирующего отношения с отношением ОТДЕЛЫ. Машинное время экономится за счет того, что в операции соединения участвуют меньшие отношения.

На языке реляционного исчисления данный запрос может быть записан как:

Выдать СОТР_ИМЯ и СОТР_НОМ для СОТРУДНИКИ таких, что

существует ОТДЕЛ с таким же, что и СОТР_НОМ значением ОТД_НАЧ и значением ОТД_КОЛ большим 50.

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

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

В зависимости от того, что является областью определения переменной, различаются исчисление кортежей и исчисление доменов.

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

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

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

Исчисление кортежей

Для определения кортежной переменной используется оператор RANGE. Например, для того, чтобы определить переменную СОТРУДНИК, областью определения которой является отношение СОТРУДНИКИ, нужно употребить конструкцию:

RANGE СОТРУДНИК IS СОТРУДНИКИ

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

Правильно построенные формулы (WFF - Well-Formed Formula) служат для выражения условий, накладываемых на кортежные переменные. Основой WFF являются простые сравнения (comparison), представляющие собой операции сравнения скалярных значений (значений атрибутов переменных или литерально заданных констант). Например, конструкция "СОТРУДНИК.СОТР_НОМ = 140" является простым сравнением. По определению, простое сравнение является WFF, а WFF, заключенная в круглые скобки, является простым сравнением.

Более сложные варианты WFF строятся с помощью логических связок NOT, AND, OR и IF ... THEN.

Так, если form - WFF, а comp - простое сравнение, то NOT form, comp AND form, comp OR form и IF comp THEN form являются WFF.

Наконец, допускается построение WFF с помощью кванторов. Если form - это WFF, в которой участвует переменная var, то конструкции EXISTS var (form) и FORALL var (form) представляют wff.

Переменные, входящие в WFF, могут быть свободными или связанными. Все переменные, входящие в WFF, при построении которой не использовались кванторы, являются свободными. Фактически, это означает, что если для какого-то набора значений свободных кортежных переменных при вычислении WFF получено значение true, то эти значения кортежных переменных могут входить в результирующее отношение. Если же имя переменной использовано сразу после квантора при построении WFF вида EXISTS var (form) или FORALL var (form), то в этой WFF и во всех WFF, построенных с ее участием, var - это связанная переменная. Это означает, что такая переменная не видна за пределами минимальной WFF, связавшей эту переменную. При вычислении значения такой WFF используется не одно значение связанной переменной, а вся ее область определения.

Пусть СОТР1 и СОТР2 - две кортежные переменные, определенные на отношении СОТРУДНИКИ.

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

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

На самом деле, правильнее говорить не о свободных и связанных переменных, а о свободных и связанных вхождениях переменных. Легко видеть, что если переменная var является связанной в WFF form, то во всех WFF, включающих данную, может использоваться имя переменной var, которая может быть свободной или связанной, но в любом случае не имеет никакого отношения к вхождению переменной var в WFF form.

Пример:

EXISTS СОТР2 (СОТР1.СОТР_ОТД_НОМ = СОТР2.СОТР_ОТД_НОМ) AND
FORALL СОТР2 (СОТР1.СОТР_ЗАРП > СОТР2.СОТР_ЗАРП)

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

Итак, WFF обеспечивают средства формулировки условия выборки из отношений БД. Чтобы можно было использовать исчисление для реальной работы с БД, требуется еще один компонент, который определяет набор и имена столбцов результирующего отношения. Этот компонент называется целевым списком (target_list).

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

- var.attr, где var - имя свободной переменной соответствующей WFF, а attr - имя атрибута отношения, на котором определена переменная var;

- var, что эквивалентно наличию подсписка var.attr1, var.attr2, ..., var.attrn, где attr1, attr2, ..., attrn включает имена всех атрибутов определяющего отношения;

- new_name = var.attr; new_name - новое имя соответствующего атрибута результирующего отношения.

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

Выражением реляционного исчисления кортежей называется конструкция вида target_list WHERE wff. Значением выражения является отношение, тело которого определяется WFF, а набор атрибутов и их имена - целевым списком.

6.4.1 Реляционное исчисление доменов

В исчислении доменов областью определения переменных являются не отношения, а домены. Применительно к базе данных СОТРУДНИКИ-ОТДЕЛЫ можно говорить, например, о доменных переменных ИМЯ (значения - допустимые имена) или НОМ_СОТР (значения - допустимые номера сотрудников).

Основным формальным отличием исчисления доменов от исчисления кортежей является наличие дополнительного набора предикатов, позволяющих выражать так называемые условия членства. Если R - это n-арное отношение с атрибутами a₁, a₂, ..., a_n, то условие членства имеет вид:

R (ai1:vi1, ai2:vi2, ..., aim:vim) (m <= n),

где v_ij - это либо литерально задаваемая константа, либо имя кортежной переменной. Условие членства принимает значение true в том и только в том случае, если в отношении R существует кортеж, содержащий указанные значения указанных атрибутов. Если v_ij - константа, то на атрибут a_ij задается жесткое условие, не зависящее от текущих значений доменных переменных; если же v_ij - имя доменной переменной, то условие членства может принимать разные значения при разных значениях этой переменной.

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

Для примера сформулируем с использованием исчисления доменов запрос "Выдать номера и имена сотрудников, не получающих минимальную заработную плату" (будем считать для простоты, что мы определили доменные переменные, имена которых совпадают с именами атрибутов отношения СОТРУДНИКИ, а в случае, когда требуется несколько доменных переменных, определенных на одном домене, мы будем добавлять в конце имени цифры):

СОТР_НОМ, СОТР_ИМЯ  WHERE EXISTS СОТР_ЗАРП1
(СОТРУДНИКИ (СОТР_ЗАРП1) AND
СОТРУДНИКИ (СОТР_НОМ, СОТР_ИМЯ, СОТР_ЗАРП) AND
СОТР_ЗАРП > СОТР_ЗАРП1)

Реляционное исчисление доменов является основой большинства языков запросов, основанных на использовании форм. В частности, на этом исчислении базировался известный язык Query-by-Example.