2. (FORALL PX) Делим полученный результат на отношение Р. В результате имеем следующее.

(Теперь у нас есть место, чтобы показать отношение полностью, без сокращений.)

1. (EXISTS JX) Проецируем, исключая атрибуты отношения J (J. Л, J.NAME и J.CITY). В результате получаем следующее.

Этап 5. Проецируем результат этапа 4 в соответствии со спецификациями в прототипе кортежа. В нашем примере прототип кортежа имеет следующий вид.

(SX.SNAME, SX.CITY)

Значит, конечный результат вычислений будет таков.

SNAME

CITY

Adams

Athens

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

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

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

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

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

Некоторый язык принято называть реляционно полным, если он по своим возможностям по крайней мере не уступает реляционному исчислению. Иначе говоря, любое отнощение, которое можно определить с помощью реляционного исчисления, можно определить и с помощью некоторого выражения рассматриваемого языка [6.1]. (В главе 6 отмечалось, что реляционно полный значит не уступающий по возможностям реляционной алгебре , а не исчислению, но, как читатель вскоре убедится, это одно и то же. По сути, из самого существования алгоритма редукции Кодда немедленно следует, что реляционная алгебра обладает реляционной полнотой.)

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

Далее, поскольку алгебра обладает реляционной полнотой, для доказательства того, что некоторый язык L также обладает реляционной полнотой, достаточно показать, что в языке L есть аналоги всех восьми алгебраических операций (на самом деле достаточно показать, что в нем есть аналоги пяти примитивных операций) и что операндами любой операции языка L могут быть любые выражения этого языка. Язык SQL - это пример языка, реляционную полноту которого можно доказать указанным способом (упр. 7.9). Язык QUEL - еще один пример подобного языка. В действительности на практике часто проще показать то, что в языке есть эквиваленты операций реляционной алгебры, чем то, что в нем существуют эквиваленты выражений реляционного исчисления. Именно поэтому реляционная полнота обычно определяется в терминах алгебраических выражений, а не в терминах выражений реляционного исчисления.

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

Вернемся к вопросу эквивалентности алгебры и исчисления. Мы на примере показали, что любое выражение исчисления можно преобразовать в его некоторый алгебраический эквивалент, а значит, алгебра по крайней мере не уступает по своей мощности исчислению. Можно показать обратное: каждое выражение реляционной алгебры можно преобразовать в эквивалентное выражение реляционного исчисления, а значит, исчисление по крайней мере не уступает по своей мощности реляционной алгебре. Полное доказательство этих утверждений можно найти, например, в книге Ульмана (UUman) [7.13]. Отсюда следует, что реляционная алгебра и реляционное исчисление эквивалентны.

7.5. Вычислительные возможности

Несмотря на то что ранее об этом не упоминалось, в определенном нами реляционном исчислении уже есть аналоги алгебраических операторов EXTEND и SUMMARIZE, и вот почему.

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

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

ш Первым или единственным аргументом в параметре <вызов обобщающей функции> является подпараметр <реляционная операциЯ>.

Замечание. Здесь мы ссылаемся на полное определение языка Tutorial D, которое приводится в [3.3].

Мы считаем, что не стоит приводить здесь все имеющие место синтаксические и семантические подробности; достаточно лишь рассмотреть несколько типичных примеров (сами примеры также несколько упрощены).

7.5.1. Определить номера и вес в граммах всех типов деталей, вес которых превышает 10 ООО г

( PX.Pi, РХ.WEIGHT * 454 AS GMWT )

WHERE PX.WEIGHT * 454 > WEIGHT ( 10000 )

Обратите внимание, что спецификация AS GMWT в прототипе кортежа дает имя соответствующему атрибуту результата. Поэтому такое имя недоступно для использования в предложении WHERE и выражение РХ.WEIGHT * 454 должно быть указано в двух местах.

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

( SX, Поставщик AS TAG )