Реферат: Реляционное исчисление

        (Это отношение, конечно, представляет собой эквивалент результата операции соединения.)

        Этап 4. Применяем кванторы в порядке справа налево следующим образом.

-   Для квантора EXISTS RX (где RX ─ переменная кортежа, принимающая значение на некотором отношении r) проецируем текущий промежуточный результат, чтобы исключить все атрибуты отношения r.

-   Для квантора FORALL RX делим текущий промежуточный результат на отношение «выбранной области значений», соответствующее RX, которое было получено выше. При выполнении этой операции также будут исключены все атрибуты отношения r.

Замечание. Под делением здесь подразумевается оригинальная операция деления Кодда.

В нашем примере имеем следующие кванторы.

EXISTS JX FORALL PX EXISTS SPJX

Значит, выполняются следующие операции.

1. (EXISTS SPJX) Проецируем, исключая атрибуты отношения SPJ (SPJ.S#,     

   SPJ.P#, SPJ.J#  и SPJ.QTY). В результате получаем следующее.

S#	SN	STA TUS	CI-TY	P#	PN	CO-LOR	WEIGHT	CITY	J#	JN	CI-TY
S1	Sm	20	Lon	P1	Nt	Red	12.0	Lon	J4	Cn	Ath
S2	Jo	10	Par	P3	Sc	Blue	17.0	Rom	J3	OR	Ath
S2	Jo	10	Par	P3	Sc	Blue	17.0	Rom	J4	Cn	Ath
S4	Cl	20	Lon	P6	Cg	Red	19.0	Lon	J3	OR	Ath
S5	Ad	30	Ath	P2	Bt	Green	17.0	Par	J4	Cn	Ath
S5	Ad	30	Ath	P1	Nt	Red	12.0	Lon	J4	Cn	Ath
S5	Ad	30	Ath	P3	Sc	Blue	17.0	Rom	J4	Cn	Ath
S5	Ad	30	Ath	P4	Sc	Red	14.0	Lon	J4	Cn	Ath
S5	Ad	30	Ath	P5	Cm	Blue	12.0	Par	J4	Cn	Ath
S5	Ad	30	Ath	P6	Cg	Red	19.0	Lon	J4	Cn	Ath

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).

Первая формулировка заслуживает более подробного обсуждения. Именно одна из трёх предложенных вариантов является допустимой в первоначальной версии языка SQL (явная операция JOIN была добавлена в стандарт  SQL/92). Концептуально можно рассматривать реализацию этой версии запроса следующим образом.

·     Во-первых, после выполнения предложения FROM мы получаем декартово произведение S TIMES P. (Строго говоря, перед вычислением произведения следовало бы позаботится о переименовании столбцов. Для простоты мы этого не делаем.)

·     Во-вторых, после выполнения предложения WHERE мы получаем выборку из этого произведения, в которой два значения атрибута CITY в каждой строке равны (иначе говоря, выполнено соединение таблиц поставщиков и деталей по эквивалентности их атрибутов городов).

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

Следовательно, предложение FROM в языке SQL соответствует декартову произведению, предложение WHERE ─ операции выборки, а совместное применение предложений SELECT-FROM-WHERE ─ проекции выборки произведения.

                               7. Заключение.

         Мы рассмотрели реляционное исчисление, альтернативное реляционной алгебре.

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

         Реляционное исчисление существует в двух версиях: исчисление кортежей и исчисление доменов. Основное различие между ними состоит в том, что переменные исчисления кортежей изменяются на отношениях, а переменные исчисления доменов изменяются на доменах.

         Выражение исчисления кортежей состоит из прототипа кортежа и необязательного предложения WHERE, содержащего логическое выражение или формулу WFF («правильно построенную формулу»). Подобная формула WFF может включать кванторы (EXISTS и  FORALL), свободные и связанные ссылки на переменные, логические (булевы) операторы (AND, OR, NOTи др.) и т.д. Каждая свободная переменная, которая встречается в формуле WFF, также должна быть упомянута в прототипе кортежа.

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

         На примере было показано[1], как алгоритм редукции Кодда может использоваться для преобразования произвольного выражения реляционного исчисления в эквивалентное выражение реляционной алгебры, таким образом подготавливая почву для выбора возможной стратегии реализации исчисления. Вновь обратившись к вопросу реляционной полноты, мы кратко обсудили, каким образом можно доказать, что некоторый язык L является полным в этом смысле.

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

         И наконец, нашему вниманию был представлен обзор соответствующих средств языка SQL. Язык SQL является своеобразной смесью реляционной алгебры и исчисления (кортежей
). Например, в нём есть прямая поддержка таких операций реляционной алгебры, как соединение и объединение, но одновременно с этим используются переменные кортежей и квантор существования из реляционного исчисления. SQL – запрос представляет собой табличное выражение. Обычно такая конструкция содержит единственное выражение выборки, однако поддерживаются и различные типы явных выражений операций соединения (JOIN), причём выражения соединения и выборки могут комбинироваться произвольным образом с помощью операторов UNION, INTERSECT и EXCEPT. Также упоминалось о возможности использования предложения ORDER BY для определения упорядоченности строк в таблице, являющейся результатом вычисления данного табличного выражения (любого вида).

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

-   Базовое предложение SELECT, в том числе использование ключевого слова DISTINCT, скалярных выражений, введение имён результирующих столбцов и использование предложения SELECT *

-   Предложение FROM, включая использование переменных кортежей

-   Предложение WHERE, включая использование оператора EXISTS

-   Предложение GROUP BY и HAVING, включая использование обобщающих функций  COUNT, SUM, AVG, MAX и MIN

-   Использование подзапросов в предложениях SELECT, FROM и WHERE

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

                                          8. Список литературы.

1)    «Введение в системы баз данных» К.Дж.Дейт, издательство «Питер», СПб 2002г.

2)    «Базы данных: модели, разработка, реализация» учебник под редакцией Т.Карповой, издательство «Питер», СПб 2001г.

3)    «Системы баз данных» Г.Гаремо-Малино, Москва 2003г. 

        

    

                                          8. Список литературы.

4)    «Введение в системы баз данных» К.Дж.Дейт, издательство «Питер», СПб 2002г.

5)    «Базы данных: модели, разработка, реализация» учебник под редакцией Т.Карповой, издательство «Питер», СПб 2001г.

6)    «Системы баз данных» Г.Гаремо-Малино, Москва 2003г. 

        

    

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