referat (Реляционное исчисление), страница 5

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

S#	SN	STATUS	CITY	J#	JNAME	CITY
S5	Adams	30	Athens	J4	Console	Athens

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

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

S#	SN	STATUS	CITY
S5	Adams	30	Athens

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

(SX.SNAME, SX.CITY)

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

SNAME	CITY
Adams	Athens

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

И хотя многие подробности в пояснениях были упущены, этот пример вполне адекватно отражает общую идею работы алгоритма редукции.

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

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

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

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

Далее, поскольку алгебра обладает реляционной полнотой, для доказательства того, что некоторый язык 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)

AND FORALL PX (IF P (P# : PX)

THEN SP (S# : SX, P# : PX)

END IF)

6. Средства языка SQL.

Как уже говорилось в разделе «Сравнительный анализ реляционного исчисления и реляционной алгебры», в основу реляционного языка могут быть положены как реляционная алгебра, так и реляционное исчисление. Что же положено в основу языка SQL? Ответом будет №частично и то, и другое, а частично ни то, ни другое…». Когда язык SQL только разрабатывался, предполагалось что он будет отличаться как от реляционной алгебры, так и от реляционного исчисления. Действительно, именно этим мотивировалось введение в язык конструкции IN . Однако со временем выяснилось, что язык SQL нуждается в определённых средствах как реляционной алгебры, так и исчисления, поэтому он был расширен для включения этих функций. На сегодняшний день ситуация складывается таким образом, что язык SQL в чём-то похож на реляционную алгебру, в чём-то на реляционное исчисление, а в чем-то отличается от них обоих.

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

6.1. Примеры.

• Для всех деталей указать номер и вес в граммах

SELECT P.P#, P.WEIGHT * 454 AS GMWT

FROM P;

Спецификация AS GMWT вводит соответствующее имя результирующего столбца. Таким образом, два столбца результирующей таблицы будут называться P# и GMWT. Если бы спецификация AS GMWT была опущена, то соответствующий столбец был бы фактически безымянным. Отметим, что хотя в подобных случаях правила языка SQL в действительности не требуют от пользователя указания имени результирующего столбца.

• Выбрать информацию обо всех парах поставщиков и деталей, находящихся в одном городе

В языке SQL существует несколько способов формулирования этого запроса. Приведем три самых простых.

1. SELECT S.*, P.P#, P.NAME, P.COLOR, P.WEIGHT

FROM S, P

WHERE S.CITY =P.CITY;

2. S JOIN P USING CITY;

3. S NATURAL JOIN P;

Результатом в каждом случае будет естественное соединение таблиц S и P (по атрибуту города CITY).