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

         Например, рассмотрим три отношения:

Ø  S-поставщики, каждый поставщик имеет уникальный номер (S#); имя (SNAME); значение рейтинга или статуса (STATUS); место расположения (CITY). Предполагается, что каждый поставщик находится только в одном городе.

Ø  P-детали, у каждого вида детали есть уникальный номер (P#); название детали (PNAME); цвет (COLOR); вес (WEIGHT); город, где хранится этот вид деталей (CITY). Каждый отдельный вид детали имеет только один цвет и хранится на складе только в одном городе.

Ø  SP-поставки, служит для организации логической связи двух других отношений. Например, первая строка отношения SP связывает поставщика с номером ‘S1’ из отношения S с соответствующей деталью, имеющей номер ‘P1’ в отношении P, т.е. представляет факт поставки деталей типа ‘P1’ поставщиком с номером ‘S1’  (а также указывает количество деталей-300 штук). Таким образом, каждая поставка характеризуется номером поставщика (S#), номером детали (P#) и количеством (QTY). Предполагается, что в одно и то же время может быть не более одной поставки  для одного поставщика и одной детали.

         Рассмотрим запрос «Выбрать номера поставщиков и названия городов, в которых находятся поставщики детали с номером ‘P2’». Алгебраическая версия этого запроса выглядит приблизительно так:

§  S и отношения поставок SP по атрибуту S#.

§  P2’.

§  S# и CITY.

Этот же запрос в терминах реляционного исчисления формулируется приблизительно так:

§  S# и CITY для таких поставщиков, для которых в отношении SP существует запись о поставке с тем же значением атрибута P#, равным ‘P2’.

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

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

         Подчеркнём, однако, что упомянутые отличия существуют только внешне. На самом деле реляционная алгебра и реляционное исчисление логически эквивалентны. Каждому выражению в алгебре соответствует эквивалентное выражение в исчислении, и точно так каждому выражению в исчислении соответствует эквивалентное выражение в алгебре. Это означает, что между ними существует взаимнооднозначное соответствие, а различия связаны лишь с разными стилями выражения; исчисление ближе к естественному языку, а алгебра -  к языку программирования; Но повторим еще раз, эти различия только кажущиеся, а не реальные. В частности, ни один из подходов нельзя назвать                                          « более непроцедурным « по сравнению с другим.

         Реляционное исчисление основано на разделе математической  логики, который называется исчислением  предикатов. Идея использования исчисления предикатов в качестве основы языка баз данных впервые была высказана в статье              Кунса  (Kuhns). Понятие реляционного исчисления, т.е. специального применения исчисления предикатов, в реляционных базах данных, впервые было предложено Коддом в 1972, а позже Кодд представил язык, основанный непосредственно на реляционном исчислении и названный  « подъязык данных ALPHA». Сам язык  ALPHA  никогда не был реализован, однако язык  QUEL,  который действительно был реализован и некоторое время  серьезно конкурировал с языком  SQL , очень походил на язык  ALPHA , оказавший заметное влияние на построение языка QUEL .

        Основным средством реляционного исчисления является  понятие  переменной кортежа  (также называемой переменной области значений). Коротко говоря, переменная кортежа – это переменная, «изменяющаяся на» некотором заданном  отношении, т.е. переменная, допустимыми значениями которой  являются кортежи заданного отношения. Другими словами, если переменная кортежа  V  изменяется в пределах отношения  r , то в любой заданный момент переменная  V  представляет некоторый кортеж  t  отношения  r. Например, запрос «Получить номера поставщиков из числа тех, которые находятся в Лондоне» может быть выражен на языке  QUEL так:

               RANGE OF SX IS S;

               RETRIEVE (SX.S#) WHERE SX.CITY = “London”;

       Переменной кортежа здесь является переменная SX, которая изменяется на отношении, представляющем собой текущее значение переменной – отношения  S (оператор RANGE – оператор определения этой переменной). Оператор RETRIEVE  означает следующее: «Для каждого возможного значения переменной  SX  выбирать компонент S# этого значения  тогда и только тогда, когда его компонент  CITY имеет значение ‘London’».

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

       Замечание.    Для удобства примем следующее соглашение: далее в этой книге термины исчисление и реляционное  исчисление, приведенные без уточнения «кортежей»  или  «доменов», будут означать именно исчисление кортежей  (там, где это играет какую-то роль).

       В статье Лакруа (Lacroix) и Пиротте (Pirotte) предлагается альтернативная версия исчисления, называемая исчислением  доменов, в которой переменные кортежа изменяются на доменах, т.е. являются переменными, изменяемыми на доменах, а не на отношениях. В литературе предлагается  множество языков исчисления доменов. Наиболее известный из них – пожалуй, Query-By-Example, или  QBE (в действительности он является смешанным, так как  в  языке  QBE  присутствуют и элементы исчисления кортежей). Существует несколько коммерческих реализаций этого языка.

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

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

                                         2.1.Синтаксис.

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

         Начнем с повторения синтаксиса параметра <реляционное выражение>.          < реляционное выражение>

                       :: =        RELATION {<список выражений кортежей>}

                                 |    < имя переменной-отношения>

                                 |    < реляционная операция>

                                 |    < реляционное выражение>

       Иными словами, синтаксис параметра  <реляционное выражение > остается прежним,  однако из наиболее важных его подпараметров, < реляционная   операция  >, теперь будет иметь совершенно иное определение.

             <определение переменной кортежа>

                       :: =         RANGEVAR  <имя переменной кортежа >

                                      RANGES OVER <список реляционных выражений >;

        Параметр <имя  переменной кортежа> может использоваться как  <выражение кортежа>, однако, лишь в определенном контексте, а именно:

§    и последующим уточнением в параметре < ссылка на атрибут кортежа >;

§ 

§    < логическое выражение >;

§    < прототип кортежа >.

                 < ссылка на  атрибут кортежа >

                          :: =     <имя переменной кортежа>.<ссылка на атрибут>[ AS <имя  атрибута>]

        Параметр <ссылка на атрибут кортежа > может использоваться как параметр < выражение>,  но только в определенном контексте, а именно:

§ 

§    параметр <прототип кортежа > или как (операнд) подпараметр                     <выражение> в параметре  <прототип кортежа>.

             < логическое выражение >

                           :: =    …  все обычные  возможности вместе с:

                                        | < логическое выражение с квантором>

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

§    < логическое выражение> расположен непосредственно после параметра < реляционная операция> (т.е. параметр  < логическое выражение > следует сразу  за ключевым словом  WHERE.).

§    содержащегося в том же выражении <реляционная операция>(т.е. параметр  <прототип кортежа> располагается непосредственно перед ключевым словом  WHERE).

       Замечание по терминологии. В контексте реляционного исчисления (в версии  исчисления доменов или исчисления кортежей) логические выражения часто называют  правильно построенными формулами (well-formed formulas – WFF, что произносится как « вэфф»). Далее мы также будем часто пользоваться этой терминологией.

            < логическое выражение с квантором>

                      :: =        EXISTS  < имя переменной  кортежа >(< логическое выражение >)

                                 | FORALL  <имя переменной кортежа > (< логическое выражение >)

           < реляционная операция >

                       :: =      < прототип кортежа > [ WHERE  < логическое выражение >]

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

            < прототип кортежа >

                       :: =       < выражение  кортежа>

        Все ссылки на переменные кортежа, помещенные непосредственно в значение параметра <прототип кортежа>, должны быть свободными в пределах данного параметра  < прототип кортежа>.

         Замечание. Прототип кортежа – термин удачный, но не стандартный.                                                                                                                                    

                                        2.2. Переменные кортежей.

       Приведём несколько примеров определения переменных кортежей (выраженных в контексте базы данных поставщиков и деталей).

             RANGEVAR SX RANGES OVER S;

             RANGEVAR SY RANGES OVER S;

             RANGEVAR SPX RANGES OVER SP;

             RANGEVAR SPY RANGES OVER SP;

             RANGEVAR PX RANGES OVER P;

             RANGEVAR SU RANGES OVER

                                 (SX WHERE SX.CITY=’London’)

                                 (SX WHERE EXISTS SPX (SPX.S# = SX.S#  AND

                                                                      SPX.P#  SPX = P# (‘P1’) ) );

      Переменная кортежа SU из последнего примера определена на объединении множества кортежей поставщиков детали с номером ‘P1’. Обратите внимание, что в определении переменной кортежа SU используются переменные кортежей SX и SPX. Также обратите внимание на то, что в подобных определениях переменных, построенных на объединении отношений, объединяемые отношения, безусловно, должны быть совместимы по типу.

       Замечание. Переменные кортежей не являются переменными в обычном смысле (как в языках программирования); они являются переменными в логическом смысле.

          2.3. Свободные и связанные переменные кортежей. 

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

       Пусть V – переменная кортежа. Тогда имеем следующее.

§  V в формулах WFF типа NOT p свободны или связаны  в пределах этой формулы в зависимости от того, свободны ли они в формуле p.Ссылки на переменную V в формулах WFF типа (p AND q) и (p OR q) свободны или связаны в зависимости от того, свободны ли они в формулах p и q.

§  V, которые свободны в формуле WFF p, связаны в формулах WFF типа EXISTS V(p) и FORALL V(p). Другие ссылки на переменные кортежей в формуле p будут свободны или связаны в формулах WFF типа EXISTS V(p) и FORALL V(p) в соответствии с тем, свободны ли они в формуле p.

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

§  V в значении параметра <имя переменной кортежа> является свободной в пределах этого параметра <имя переменной кортежа>.

§  V в значении параметра <ссылка на атрибут кортежа> V.A является свободной в пределах этого параметра <ссылка на атрибут кортежа>.

§  V является свободной в некотором выражении exp, то эта ссылка будет также свободной в любом выражении exp’, непосредственно содержащем выражение exp как подвыражение, если только в выражении exp’ не вводится квантор, связывающий переменную V.

Приведём несколько примеров формул WFF, содержащих переменные

кортежей.

§  Простые сравнения

SX.S# = S# (‘S1’)

SX.S# = SPX.S#

SPX.P# ≠ PX.P#

Здесь все ссылки на переменные SX, PX и SPX являются свободными.

§  Логические выражения из простых сравнений

PX.WEIGHT < WEIGHT (15.5) OR PX.CITY = ‘Rome’

NOT (SX.CITY = ‘London’)

SX.S# = SPX.S# AND SPX.P# ≠ PX.P#

PX.COLOR = COLOR (‘Red’) OR PX.CITY = ‘London’

Здесь также все ссылки на переменные SX,PX и SPX являются свободными.

§  Формулы WFF с кванторами

EXISTS SPX (SPX.S# = SX.S# AND SPX.P# = P# (‘P2’) )

FORALL PX (PX.COLOR = COLOR (‘Red’) )

В этих примерах ссылки на переменные SPX и PX являются связанными, а ссылка на переменную SX является свободной. Подробнее данные примеры объясняются ниже.

                                  2.4. Кванторы.

      Существуют два квантора: EXISTS и FORALL. Квантор EXISTS является квантором существования, а FORALL─ квантором всеобщности. По сути, если выражение p ─ формула WFF, в которой переменная V свободна, то выражения

EXISTS V (p)

и

FORALL V (p)

     также являются допустимыми формулами WFF, но переменная V в них обеих будет связанной. Первая формула означает следующее: «Существует по крайней мере одно значение переменной V, такое, что вычисление формулы p даёт для него значение истина». Вторая формула означает следующее: «Для всех значений переменной V вычисление формулы p даёт значение истина». Предположим, например, что переменная V изменяется на множестве «Члены сената США в 1999 году», и предположим также, что выражение p ─ следующая формула WFF: «V ─ женщина» (разумеется, здесь не пытаемся использовать формальный синтаксис). Тогда выражение EXISTS V(p) будет допустимой формулой WFF, имеющей значение истина (true); выражение FORALL V(p) также будет допустимой формулой WFF, но вычисление его значения будет давать значение ложь (false).

      Теперь рассмотрим квантор существования EXISTS более внимательно. Ещё раз обратимся к примеру из предыдущего раздела.

       EXISTS SPX (SPX.S# = SX.S# AND SPX.P# = P# (‘P2’) )

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

В текущем значении отношения SP существует кортеж (скажем, SPX),   такой, для которого значение атрибута S# в этом кортеже равно значению атрибута SX.S# (какое бы оно ни было), а значение атрибута P# в кортеже SPX равно ‘P2’.

       Каждая ссылка на переменную SPX в этом примере является связанной. Единственная ссылка на переменную SX свободна.

       Формально квантор существования EXISTS определяется как повторение операции OR (ИЛИ). Другими словами, если r ─ это отношение с кортежами t1, t2, … , tm, V ─ это переменная кортежа, изменяющаяся на данном отношении, и p(V) ─ это формула WFF, в которой переменная V используется как свободная переменная, то формула WFF вида

        EXISTS V (p (V))

равносильна следующей формуле WFF.

        false OR p (t1) OR … OR p (tm)

        В частности, обратите внимание, что если отношение R пустое (т.е. m=0), то результатом вычисления данного выражения будет значение ложь.

        Рассмотрим в качестве примера отношение r, содержащее следующие кортежи.

         (1, 2, 3)

         (1, 2, 4)

         (1, 3, 4)

        Для простоты предположим, что три атрибута, идущие по порядку слева направо, имеют имена A, B и C соответственно и каждый из этих атрибутов имеет тип INTEGER. Тогда приведённые ниже выражения будут иметь указанные значения.

       EXISTS V (V.C>1)                                     : true

       EXISTS V (V.B>3)                                     : false

       EXISTS V (V.A>1 OR V.C = 4)                 : true

       Теперь рассмотрим квантор общности FORALL, для чего вернёмся к соответствующему примеру из предыдущего раздела.

        FORALL PX (PX.COLOR = COLOR (‘Red’) )

        Эта формула WFF может быть прочитана следующим образом.

В текущем значении отношения P для всех кортежей (скажем, PX) значение их атрибута COLOR равно ‘Red’.

Обе ссылки на переменную PX в этом примере связаны.

        Подобно тому, как квантор EXISTS был определён как повторение операции OR, квантор существования FORALL определяется как повторяющаяся операция AND (И). Другими словами, если обозначения r, V и p(V) имеют тот же смысл, что и в приведённом выше определении квантора EXISTS, то формула WFF вида

        FORALL V (p (V) )

        равносильна следующей формуле WFF.  

   true AND p (t1) AND … AND p (tm)

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

        В качестве примера рассмотрим отношение R, содержащее те же кортежи, что и в предыдущем примере. Тогда приведённые ниже выражения будут иметь указанные значения.

        FORALL V (V.A>1)                                    : false

        FORALL V (V.B>1)                                    : true

        FORALL V (V.A = 1 and V.C>2)               : true

        Замечание. Квантор FORALL включён в реляционное исчисление просто для удобства. Он не является необходимым, так как приведённое ниже тождество показывает, что любая формула WFF, использующая квантор FORALL, всегда может быть заменена эквивалентной формулой WFF, использующей квантор EXISTS.

        FORALL V (p) ≡ NOT EXISTS V (NOT p)

        (Проще говоря, выражение «все значения V, удовлетворяющие формуле p» ─ это то же самое, что и выражение «нет таких значений V, которые бы не удовлетворяли формуле p».)

        Например, утверждение (истинное)

        Для любого целого x существует целое y, такое, что y>x

равносильно утверждению

       Не существует целого x, такого, что не существует целого y, такого, что y>x.

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

            2.5. Ещё раз о свободных и связанных переменных.

        Предположим, что переменная x изменяется на множестве всех целых чисел, и рассмотрим следующую формулу WFF.

        EXISTS x (x>3)

        Связанная переменная x  в этой формуле WFF является своего рода фиктивной переменной. Она служит лишь для связи внутренних параметров выражения с внешним квантором. В формуле WFF просто утверждается, что существует целое число (скажем, x), которое больше 3. Следовательно, значение этой формулы WFF осталось бы полностью неизменным, если бы все экземпляры x были заменены экземплярами некоторой другой переменной (скажем, y). Другими словами, формула WFF EXISTS y (y>3) семантически идентична формуле, приведённой ранее.

        Теперь рассмотрим другую формулу WFF.

        EXISTS x (x>3) AND x<0

        Здесь имеется три ссылки на переменную x, обозначающие две различные переменные. Первые две ссылки связаны и могли быть заменены ссылкой на другую переменную y без изменения общего смысла формулы. Третья ссылка на переменную x не может быть безболезненно изменена. Таким образом, из двух приведённых ниже формул WFF первая эквивалентна рассмотренной формуле, а вторая ─ нет.

        EXISTS y (y>3) AND x<0

        EXISTS y (y>3) AND y<0

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

        Дополнительная терминология. Формула WFF, в которой все переменные связаны, называется закрытой формулой WFF (фактически она является высказыванием). Открытая формула WFF ─ это формула, которая не является закрытой, т.е. такая формула, которая содержит по крайней мере одну ссылку на свободную переменную.

                               2.6. Реляционные операции.

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

        <реляционная операция>

                 : : =       <прототип кортежа> [ WHERE <логическое выражение> ]

        <прототип кортежа>

                 : : =       <выражение кортежа>

        Напоминаем также, что следующие синтаксические правила теперь несколько упрощены.

§ 

§  WHERE может быть свободной только в случае, если на эту же переменную (обязательно свободная) присутствует  в соответствующем значении параметра <прототип кортежа>.

        Например, следующее выражение является допустимым значением параметра <реляционная операция> («Получить номера поставщиков, находящихся в Лондоне»).

        SX.S# WHERE SX.CITY = ‘London’

        Здесь ссылка на переменную SX в прототипе кортежа является свободной. Ссылка на переменную SX в предложении WHERE также является свободной, поскольку ссылка на ту же переменную (обязательно свободную) имеется и в значении параметра <прототип кортежа> этого выражения.

        Замечание. Далее термин «прототип кортежа» будет употребляться без скобок.

        Приведём другой пример («Получить имена поставщиков детали с номером ‘P2’»)

        SX.SNAME WHERE EXISTS SPX (SPX.S# SX.S# AND

                                                                     SPX.P# = P# (‘P2’) )

        Здесь все ссылки на переменную SX являются свободными, тогда как все ссылки на переменную SPX (в предложении WHERE) являются связанными, как и должно быть, поскольку на них нет ссылок в прототипе кортежа.

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

§  AS для введения нового имени атрибута), либо просто именем переменной кортежа. Тем не менее отметим следующее.

а)     

б)      AS, в принципе, является сокращённым обозначением ссылки с предложением AS, в которой новое имя атрибута совпадает со старым.

Следовательно, без потери общности прототип кортежа можно рассматривать как список, состоящий из разделённых запятыми ссылок на атрибуты в виде Vi.Ai AS Bj. Обратите внимание, что ссылки Vi- и Aj-е могут повторяться, тогда как ссылки Bj-е должны быть разными.  

§  V1, V2, … ,Vm будут различными переменными кортежей, упоминаемыми в прототипе кортежа, и пусть эти переменные будут определены на отношениях r1, r2, … ,rm соответственно. Примем, что r1’, r2’, … ,rm’ ─ это новые отношения, полученные после переименования атрибутов в предложении AS, и пусть r’ ─ это декартово произведение отношений r1’, r2’, … , rm’.

§  r ─ это выборка из отношения r’, удовлетворяющая формуле WFF в предложении WHERE.                                                                                                                                                                             

Замечание. Здесь предполагается, что на предыдущем шаге были также переименованы атрибуты, упоминающиеся в предложении WHERE; в противном случае функция WFF в предложении WHERE может не иметь смысла.

§  r по всем заданным атрибутам Bj.

                                                   2.7. Примеры.

       Представляем несколько примеров использования реляционного исчисления кортежей для формулирования запросов.

Ø  Определить имена поставщиков детали с номером ‘P2’                                                                                       

SX

WHERE EXISTS SPX (SPX.S# = SX.S# AND

                                        SPX.P# = P# (‘P2’) )

         Обратите внимание на использование имени переменной кортежа в прототипе кортежа. Этот пример является сокращённой записью следующего выражения.

(SX.S#, SX.NAME, SX.STATUS, SX.CITY)

WHERE EXISTS SPX (SPX.S# = SX.S# AND

                                        SPX.P# = P# (‘P2’) )

Этот же пример решённый средствами реляционной алгебры выглядит так

( (SP JOIN S) WHERE P# =’P2’) {SNAME}

Ø  Определить имена поставщиков по крайней мере одной красной детали

SX.SNAME

WHERE EXISTS SPX (SX.S# = SPX.S# AND

                                        EXISTS PX (PX.P# = SPX.P# AND

                                                              PX.COLOR = COLOR (‘Red’) ) )

Этот же пример решённый средствами реляционной алгебры выглядит так

( ( ( P WHERE COLOR = COLOR (‘Red’) )

                                            JOIN SP) {S#} JOIN S) {SNAME}

  3. Сравнительный анализ реляционного исчисления и           реляционной алгебры.

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