Выражение реляционного исчисления кортежей

Переменная кортежа (или области значений) определяется с помощью синтаксиса, являющегося синтаксисом языка QUEL, следующим образом:

RANGE OF T IS X1, X2, …, Xn. (1).

Здесь Т — определяемая переменная кортежа, а Xi (i = 1, 2, …, n) — либо имя отношения, либо выражение исчисления кортежей. Пусть Xi является отношением Ri (i = 1, 2, …, n). Отношения R1, R2, …, Rn должны быть совместимы по типу, т. е. они должны иметь идентичные заголовки. Тогда переменная кортежа Т изменяется на объединении этих отношений, т. е. ее значение в любое заданное время будет некоторым текущим кортежем по крайней мере одного из этих отношений. Конечно, если список идентификаторов выражений будет просто одним именованным отношением R (это обычный случай), то переменная кортежа будет просто принимать значения текущих кортежей одного такого отношения R. При использовании кортежных переменных в формулах можно ссылаться на значение атрибута переменной (это аналогично тому, как, например, при программировании на языке Pascal можно сослаться на значение поля переменной типа записи). Правильно построенная формула WFF служит для выражения условий, накладываемых на кортежные переменные. WFF состоит из простых сравнений скалярных значений (значений атрибутов переменных или литерально заданных констант). Более сложные варианты WFF строятся с помощью логических операций NOT, AND, OR, IF… THEN, и двух кванторов EXISTS и FORALL. Квантор EXISTS называется квантором существования, а квантор FORALL — квантором общности. Если f — формула WFF, в которой участвует переменная x, то EXISTS x (f) и FORALL x (f) являются допустимыми формулами WFF.

Первая формула означает: «существует по крайней мере одно значение переменной x, что вычисление формулы f для этого x дает значение истина». Вторая формула означает: «Для всех значений переменной x вычисление формулы f дает значение истина». Квантор существования EXISTS определяется формально, как повторяющееся OR (ИЛИ). То есть, если R — это отношение с кортежами Т1, Т2, …, Тm; Т — это переменная кортежа, которая изменяется на этом отношении; а f (T) — это формула, в которой используется переменная Т, то формула EXISTS T (f (T)) определяется равносильно следующей формуле WFF: false OR (f (T1)) OR … OR (f™). Квантор существования FORALL определяется, как повторяющееся AND (И). Другими словами, если R, T и f (T) такие же, как рассматривались выше, то формула FORALL T (f (T)) определяется равносильно следующей формуле:

true AND (f (T1)) AND … AND (f (Tm)). (2).

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

Пусть T и K — две кортежные переменные, определенные на отношении R. Тогда, WFF EXISTS K (T.A > K. A) для текущего кортежа переменной T принимает значение true в том и только в том случае, если во всем отношении R найдется кортеж (связанный с переменной K) такой, что значение его атрибута A удовлетворяет внутреннему условию сравнения. Формула WFF FORALL K (T.A > K. A) для текущего кортежа переменной T принимает значение true в том и только в том случае, если для всех кортежей отношения R (связанных с переменной K) значения атрибута A удовлетворяют условию сравнения. Таким образом, кванторы в реляционном исчислении играют ту же роль, что декларации в языке программирования. Понятие свободной переменной аналогично понятию глобальной переменной, описанной вне текущей процедуры. Понятие связанной переменной аналогично понятию локальной переменной, описанной в текущей процедуре. Итак, WFF обеспечивают средства формулировки условия выборки из отношений БД. Чтобы можно было использовать исчисление для реальной работы с БД, требуется еще один компонент, который определяет набор и имена столбцов результирующего отношения. Этот компонент называется целевым списком (target_list). Целевой список строится из целевых элементов, каждый из которых может иметь следующий вид:

T.A [AS X] (3).

где T — имя свободной переменной соответствующей WFF, а A — имя атрибута отношения, на котором определена переменная T, а X — это имя атрибута, результата вычисления элементов целевого списка. T, что эквивалентно наличию подсписка T. A1, T. A2,…, T. An, где A1, A2, …, An включает имена всех атрибутов определяющего отношения;

N = T. A;

N — новое имя соответствующего атрибута результирующего отношения.

Последний вариант требуется в тех случаях, когда в WFF используются несколько свободных переменных с одинаковой областью определения. Выражением реляционного исчисления кортежей называется конструкция вида TARGET_LIST WHERE WFF. Значением выражения является отношение, тело которого определяется WFF, а набор атрибутов и их имена — целевым списком. Как указывалось выше, для описания реляционного исчисления кортежей использован синтаксис реального языка запросов QUEL. Если использовать традиционный синтаксис языка предикатов, то описание реляционного исчисления с переменными кортежей выглядит следующим образом. Выражение записывается в виде:

{t | y (t)} (4).

где t — единственная свободная переменная, обозначающая кортеж фиксированной длины (если необходимо указать арность кортежа, то используют запись t⁽ⁱ⁾; i — арность кортежа t); y — правильно построенная формула (WFF).

На рис. 2 представлен обзор рассмотренных элементов языка QUEL и их эквиваленты из языка предикатов.

Рис. 2. Элементы синтаксиса языка QUEL и языка предикатов