Реляционное исчисление с переменными-кортежами

Как уже говорилось, в данном случае областью определения переменных являются отношения. Переменные-кортежи должны удовлетворять определенной схеме отношения R. Правильно построенная формула (wff – well formulated formula) определяет результаты отбора: выбираются те кортежи, для которых wff дает значение 1.

Обозначим правильно построенную формулу (предикат, значения которого 0 или 1) через y(t).

Рассмотрим правила построения y(t).

I. Основой формулы являются атомы, которые могут иметь значения 0 или 1.

Существует три типа атомов формулы y(t).

1. Пусть r(R) – некоторая реализация отношения, удовлетворяющая схеме R; t – некоторая переменная-кортеж, удовлетворяющая схеме R. Тогда r(t) – атом; означает, что t есть кортеж в отношении r (т.е. формула истинна, если t Î r).

2. Пусть r(R) – некоторая реализация отношения, удовлетворяющая схеме R; u и v – переменные-кортежи из отношения r(R) (т.е. u Î r, v Î r); q – арифметическая операция сравнения (<, =, >, ³, ¹, £); A, B – атрибуты схемы отношения R, сравнимые по операции q; тогда u[A] q v[B] – атом.

3. Пусть u – переменная-кортеж из отношения r(R) (т.е. u Î r, v Î r); q – арифметическая операция сравнения (<, =, >, ³, ¹, £); A, B – атрибуты схемы отношения R, сравнимые по операции q; c – константа из домена, на котором определен атрибут B; тогда u[A] q c (или c q u[A]) – атом.

В приведенных выше условиях запись u[A] означает «значение переменной-кортежа u по атрибуту A».

II. Формула реляционного исчисления y(t), а также свободные и связанные вхождения переменных определяются по следующим рекурсивным правилам:

1. Каждый атом есть формула. Все вхождения переменных-кортежей, упомянутых в атоме, являются свободными. Например, формула r(t) утверждает, что переменная-кортеж t является кортежем отношения r(R).

2. Если x(R) – переменная-кортеж из отношения r со схемой R; y(x) – формула, в которой переменная x имеет свободное вхождение; тогда $ x(R) (y(x)) – формула, в которой вхождение переменной x становится связанным квантором $. Данная формула утверждает, что существует хотя бы один кортеж x в отношении r(R), такой, что при подстановке его в формулу y(x) вместо всех свободных вхождений x получим значение "истина". Например, формула $ x(R) (r(x)) утверждает, что отношение r не пусто (то есть, существует хотя бы один кортеж x, принадлежащий r).

3. Если x(R) – переменная-кортеж из отношения r со схемой R; y(x) – формула, в которой переменная x имеет свободное вхождение; тогда " x(R) (y(x)) – формула, в которой вхождение переменной x становится связанным квантором ". Данная формула утверждает, что для всех кортежей x из отношения r(R) при подстановке их в формулу y(x) вместо всех свободных вхождений x получим значение "истина". Например, формула " x(R) (x[A] ¹ Æ) утверждает, что для всех кортежей значение атрибута A является обязательным.

4. Если y(x) и j(x) – формулы, тогда Øy(x), y(x) Ù j(x), y(x) Ú j(x) – тоже формулы. Вхождения переменной x в эти формулы остаются свободными или связанными – такими, какими были в y(x) или j(x), соответственно. Например, если переменная x имела в j(x) свободное вхождение, а в y(x) – связанное, то в этих функциях сохраняется тип вхождения переменных.

5. Если y(x) – формула, то (y(x)) – тоже формула; вхождение переменной x остается свободным или связанным – таким, каким оно было в y(x).

6. Ничто иное не является формулой.

При вычислении формул используется порядок старшинства операций, определяемый правилами построения формулы:

a) атомы, в которых могут быть использованы арифметические операции сравнения;

b) кванторы;

c) отрицание (Ø)

d) операция "И" (Ù)

e) операция "ИЛИ" (Ú)

Скобки используются для изменения порядка вычисления формулы.

Определение

Выражение реляционного исчисления с переменными-кортежами имеет вид: { t(R) | y(t) }, где t – переменная-кортеж, удовлетворяющая схеме отношения R; единственная переменная, имеющая свободное вхождение в формулу y(t); y(t) – правильно построенная формула.

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

Пример

Пусть есть отношение R(ИМЯ, СТИПЕНДИЯ); атрибут СТИПЕНДИЯ определен на домене D = {«да», «нет»}. Тогда выражение

{ t(ИМЯ) | $x(R) (r(x) Ù x[СТИПЕНДИЯ] = «да» Ù x[ИМЯ] = t[ИМЯ]}

позволит получить из отношения имена всех студентов, получающих стипендию.