Реляционное исчисление
Также следует отметить, что восемь алгебраических операторов Кодда являются мерой оценки выразительной силы любого языка баз данных.
Некоторый язык принято называть реляционно полным, если он по своим возможностям по крайней мере не уступает реляционному исчислению. Иначе говоря, любое отношение, которое можно определить с помощью реляционного исчисления, можно определить и с помощью некоторого выражения рассматриваемого языка. («Реляционно полный» значит «не уступающий по возможностям реляционной алгебре», а не исчислению, но это одно и то же, как мы вскоре убедимся. По сути, из самого существования алгоритма редукции Кодда немедленно следует, что реляционная алгебра обладает реляционной полнотой.)
Реляционную полноту можно как основную меру выразительной силы языков баз данных в самом общем случае. В частности, так как реляционное исчисление и реляционная алгебра обладают реляционной полнотой, они могут служить основой для проектирования не уступающих им по выразительности языков без необходимости выполнять пересортировку для организации циклов. Это замечание особенно важно, если язык предназначается для конечных пользователей, хотя оно также существенно, если язык предназначается для использования прикладными программистами.
Далее, поскольку алгебра обладает реляционной полнотой, для доказательства того, что некоторый язык L также обладает реляционной полнотой, достаточно показать, что в языке L есть аналогии всех восьми алгебраических операций (на самом деле достаточно показать, что в нём есть аналоги пяти примитивных операций) и что операндами любой операции языка L могут быть любые выражения этого языка. Язык SQL ─ это пример языка, реляционную полноту которого можно доказать указанным способом. Язык QUEL ─ ещё один пример подобного языка. В действительности на практике часто проще показать то, что в языке есть эквиваленты операций реляционной алгебры, чем то, что в нём существуют эквиваленты выражений реляционного исчисления. Именно поэтому реляционная полнота обычно определяется в терминах алгебраических выражений, а не в терминах выражений реляционного исчисления.
При этом важно понимать, что реляционная полнота необязательно влечёт за собой полноту какого-либо другого рода. Например, желательно, чтобы язык также обеспечивал «вычислительную полноту», т.е. позволял вычислять результаты всех вычислимых функций. Заметим, что согласно нашему определению исчисление не обладает полнотой такого рода, хотя на практике подобная полнота для языка баз данных весьма желательна. Вычислительная полнота ─ это один из факторов, побудивших ввести в реляционную алгебру операции EXTEND и SUMMARIZE. В следующем разделе описано, как можно расширить реляционное исчисление, чтобы обеспечить в нём наличие аналогов этих операций.
Вернёмся к вопросу эквивалентности алгебры и исчисления. Мы на примере показали, что любое выражение исчисления можно преобразовать в его некоторый алгебраический эквивалент, а значит, алгебра по крайней мере не уступает по своей мощности исчислению. Можно показать обратное: каждое выражение реляционной алгебры можно преобразовать в эквивалентное выражение реляционного исчисления, а значит, исчисление по крайней мере не уступает по своей мощности реляционной алгебре. Отсюда следует, что реляционная алгебра и реляционное исчисление эквивалентны.
4. Вычислительные возможности.
Несмотря на то что ранее об этом не упоминалось, в определённом нами реляционном исчислении уже есть аналоги алгебраических операторов EXTEND и SUMMARIZE, и вот почему.
Одной из допустимых форм прототипа кортежа является параметр <операция выборки кортежа>, компонентами которого могут быть произвольные подпараметры <выражение>.
В параметре <логическое выражение> сравниваемыми элементами могут быть произвольные подпараметры <выражение>.
Первым или единственным аргументом в параметре <вызов обобщающей функции> является подпараметр <реляционная операция>.
4.1. Примеры.
Для каждой детали выбрать номер и общий объём поставки в штуках
(PX.P#, SUM (SPX WHERE SPX.P# = PX.P#, QTY) AS TOTQTY)
Определить общее количество поставляемых деталей
SUM (SPX, QTY) AS GRANDTOTAL)
Определить номера и вес в граммах всех типов деталей, вес которых превышает 10000г
(PX.P#, PX.WEIGHT * 454 AS GMWT)
WHERE PX.WEIGHT * 454 > WEIGHT (10000)
Обратите внимание, что спецификация AS GMWT в прототипе кортежа даёт имя соответствующему атрибуту результата. Поэтому такое имя недоступно для использования в предложении WHERE и выражение PX.WEIGHT * 454 должно быть указано в двух местах.
5. Исчисление доменов.
Как указывалось в «Введении», реляционное исчисление, ориентированное на домены (или исчисление доменов), отличается от исчисления кортежей тем, что в нём вместо переменных кортежей используется переменные доменов, т.е. переменные, принимающие свои значения в пределах домена, а не отношения. С практической точки зрения большинство очевидных различий между версиями исчисления доменов и исчисления кортежей основано на том, что версия для доменов поддерживает форму параметра <логическое выражение>, который мы будем называть условием принадлежности. В общем виде условие принадлежности можно записать так.
R (пара, пара, …)
Здесь R─ имя отношения, а каждый параметр пара имеет вид A: v, где A ─ атрибут отношения R, а v ─ имя переменной домена или литерал. Проверка условия даёт значение истина тогда и только тогда, когда в текущем значении отношения R существует кортеж, имеющий указанные значения для указанных атрибутов. Например, рассмотрим результат вычисления следующего выражения.
SP (S# : S# (‘S1’), P# : P# (‘P1’) )
Он будет иметь значение истина тогда и только тогда, когда в отношении SP будет существовать кортеж со значением атрибута S#, равным ‘S1’, и значением атрибута P#, равным ‘P1’. Аналогично условие принадлежности
SP (S# : SX, P# : PX)
принимает значение истина тогда и только тогда, когда в отношении SP существует кортеж со значением атрибута S#, эквивалентным текущему значению переменной домена PX (опять же, какому бы ни было).
Далее будем подразумевать существования следующих переменных доменов.
Домен Переменная домена
S# SX, SY, …
P# PX, PY, …
NAME NAMEX, NAMEY, …
COLOR COLORX, COLORY, …
WEIGHT WEIGHTX, WEIGHTY, …
QTY QTYX, QTYY, …
CHAR CITYX, CITYY, …
INTEGER STATUSX, STATUSY, …
Ниже приведено несколько примеров выражений исчисления доменов.
SX
SX WHERE S (S# : SX)
SX WHERE S (S# : SX, CITY : ‘London’)
(SX, CITYX) WHERE S (S# : SX, CITY : ‘London’)
AND SP (S# : SX, P# : P# (‘P2’) )
(SX,PX) WHERE S (S# : SX, CITY : CITYX)
AND P (P# : PX, CITY : CITYY)
AND CITYX ≠ CITYY
Если говорить нестрого, первое выражение означает множество всех номеров поставщиков, второе ─ множество всех номеров поставщиков из Лондона. Следующее выражение ─ это выраженный в терминах исчисления доменов запрос «Определить номера поставщиков и названия городов, в которых находятся поставщики детали с номером ‘P2’» (вспомните, что в этом запросе, выраженном в терминах исчисления кортежей, использовался квантор существования). И последнее выражение ─ это представленный в терминах исчисления доменов запрос «Найти все такие пары номеров поставщиков и номеров деталей, для которых поставщик и деталь находятся в одном городе».
5.1. Примеры.
Найти все такие пары номеров поставщиков, в которых два поставщика находятся в одном городе
(SX AS SA, SY AS SB) WHERE EXISTS CITYZ
(S (S# : SX, CITY : CITYZ) AND
S (S# : SY, CITY : CITYZ) AND
SX < SY)
Определить имена поставщиков по крайней мере одной красной детали
NAMEX WHERE EXISTS SX EXISTS PX
(S (S# : SX, SNAME : NAMEX)
AND SP (S# : SX, P# : PX)
AND P (P# : PX, COLOR : COLOR (‘Red’) ) )
Выбрать имена поставщиков всех типов деталей
NAMEX WHERE EXISTS SX (S (S# : SX, SNAME : NAMEX)