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

Если P — предикат, то множество всех значений переменной x, при которых суждение P становится истинным, будем обозначать как tx |Fpxqu.

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

• Исчисление доменов — предложено Эдгаром Коддом [1]. Здесь областями определения переменных являются домены, на которых определены атрибуты отношений базы данных, т. е. допустимым значением каждой переменной является значение некоторого домена.

• Исчисление кортежей — предложено Мишелем Лакруа и Алеином Пиро [3]. Здесь областями определения переменных являются тела отношений базы данных, т. е. допустимым значением каждой переменной является кортеж тела некоторого отношения.

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

Вреляционном исчислении кортежей (turple relational calculus) задача состоит в нахождении та-

ких кортежей, для которых предикат является истинным. Это исчисление основано на переменных кортежа.

Определение 1. Переменными кортежа являются такие переменные, областью определения1 которых служат тела отношений базы данных.

Будем обозначать множество всех кортежей T , для которых предикат FpT q принимает истинное значение, в виде: tT | FpT qu.

Правильно построенная формула F (Well-Formed Formula, WFF) служит для выражения условий, накладываемых на кортежные переменные.

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

простое сравнение.

Для указания количества экземпляров, к которым должен быть применен предикат, в формулах могут использоваться два типа кванторов:

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

•квантор общности @, используемый в выражениях, которые относятся ко всем экземплярам.

Один из кванторов можно исключить, т. к. они выражаются друг через друга. Обычно исключают квантор всеобщности, заменяя его, используя тождество p@xqpPpxqq pDxqp Ppxqq.

Определение 2. Переменные кортежа называются свободными переменными, если они не квалифицируются кванторами D или @; в противном случае они называются связанными переменными.

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

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

1Понятие «область определения» в данном случае относится не к используемому диапазону значений, а к домену,

вкотором определены эти значения.

23

где T1; T2; : : : ; Tn; : : : ; Tm — переменные кортежа и в совокупности называются целевым списком, ai — атрибуты отношения, в котором определено значение переменной Ti, a F — формула.

Дадим формальное определение понятия «формула», для этого надо определить формально понятие элементарного выражения, из которых строится формула.

Определение 3. Элементарным выражением (атомом, простым условием) называются формулы следующего вида:

•pTi P Rq (еще обозначают как RpT q), где Ti — переменная кортежа, а R — отношение; это выражение истинно тогда и только тогда, когда кортеж Ti принадлежит телу отношения R;

•pTi:a1 Tk:a2q, где Ti и Tk — переменные кортежа, a1 — атрибут отношения, в котором определено значение переменной Ti, a2 — атрибут отношения, в котором определено значение переменной Tk, и P tă; ď; ą; ě; ; u — одна из операций сравнения; атрибуты a1 и a2 должны иметь области определения, для сравнения элементов которых применение знака операции

является допустимым.

•Ti:a1 const, где Ti — переменная кортежа, 1 — атрибут отношения, в котором определено значение переменной Ti, const — константа из домена атрибута и P tă : ď; ą; ě; ; u — одна из операций сравнения.

Определение 4. Допустимые формулы (well-formed formulas, WFF) рекурсивно строятся из эле-

ментарных выражений на основе следующих правил:

•Любое элементарное выражение (атом) рассматривается как формула.

•Если выражения F1 и F2 являются формулами, то выражения, полученные в результате их конъюнкции (pF1 ^ F2q), дизъюнкции (pF1 _ F2q) и отрицания ( pF1q — еще могут обозначать символом s вместо ), также являются формулами.

•Если выражение F является формулой со свободной кортежной переменной T , то выражения pDT qpFq и p@T qpFq также являются формулами.

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

Например, выражение tT | pT P Rqu является опасным, поскольку в нем предусмотрено получение кортежей, не принадлежащих к отношению R, т. e. кортежей, находящихся за пределами области определения отношения. Некоторые авторы указывают, что для предотвращения возникновения этой проблемы можно применить переменные области определения, заданные с помощью отдельной операции RANGE.

Эквивалентность исчисления кортежей и реляционной алгебры

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

1. Проекция на атрибуты A ta1; : : : ; anu отношения R:

tT :a1; : : : ; T :an |pDT2qppT2 P Rq ^ pT2:a1 T :a1q ^ : : : ^ pT2:an T :anqqu :

2.Выборка из отношения R с атрибутами ta1; : : : ; anu по условию F Fpai1 ; : : : ; aik q, где aij — некоторые атрибуты отношения R:

tT :a1; : : : ; T :an |pT P Rq ^ FpT :ai1 ; : : : ; T :aik qu :

3. Объединение отношений R1 и R2 с одинаковым набором атрибутов ta1; : : : ; anu: tT :a1; : : : ; T :an |pT P R1q _ pT P R2qu :

24