и наконец, вашему вниманию был представлен обзор соответствующих средств языка 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

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

Упражнения

7л. Пусть р(х) и q - произвольные формулы WFF, в которых переменная х соответственно используется и не используется в качестве свободной переменной. Какие из следующих формулировок верны? (Здесь символ => означает следует , а символ = означает эквивалентно . Обратите внимание, что если А => В и В => А, то А = В.)

а) EXISTS X ( q ) = q

б) FORALL X ( q ) = q

в) EXISTS X ( p (X) AND q ) = EXISTS x ( p (x) ) AND q r) FORALL x ( p (X) AND q ) = FORALL x ( p (x) ) AND q д) FORALL X ( p (X) ) => EXISTS x ( p (x) )

7.2. Пусть p(x,y) - это произвольная формула WFF со свободными переменными х и у. Какие из следующих формулировок верны?

а) EXISTS X EXISTS у ( р(х,у) ) = EXISTS у EXISTS х ( р(х,у) )

б) FORALL X FORALL у ( р(х,у) ) = FORALL у FORALL х ( р(х,у) )

в) FORALL X ( р(х,у) ) = NOT EXISTS х ( NOT р(х,у) )

г) EXISTS X ( р(х,у) ) = NOT FORALL х ( NOT р(х,у) )

д) EXISTS X FORALL у ( p(x,y) ) = FORALL у EXISTS x ( p(x,y) )

е) EXISTS у FORALL x ( p(x,y) ) => FORALL x EXISTS у ( p(x,y) )

7.3. Пусть p(x) и q(y) - произвольные формулы WFF со свободными переменными х и у соответственно. Какие из следующих формулировок верны?

а) EXISTS X ( р(х) ) AND EXISTS у ( q(y) ) = EXISTS X EXISTS у ( p(x) AND q(y) )

б) EXISTS X ( IF p(x) THEN q(x) END IF ) =

IF FORALL X ( p(x) ) THEN EXISTS x ( q(x) ) END IF

7.4. Еще раз обратимся к запросу из примера 7.3.8: Определить номера поставщиков по крайней мере всех типов деталей, поставляемых поставщиком с номером S2 . Для этого запроса возможна следующая формулировка в терминах исчисления кортежей.

SX.S# WHERE FORALL SPY ( IF SPY.Sl = S2 THEN

EXISTS SPZ ( SPZ.SI = SX.S# AND SPZ.PI = SPY.PI )

END IF )

(Здесь SPZ - это еще одна переменная кортежа, изменяющаяся на отнощений поставок.) Что будет возвращено при выполнении этого запроса, если поставщик с номером S2 в данный момент не поставляет никаких деталей? Что будет, если в приведенном выражении переменную SX всюду заменить переменной SPX?

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

( PX.NAME, PX.CITY ) WHERE FORALL SX FORALL JX EXISTS SPJX

( SX.CITY = London AND JX.CITY = Paris AND SPJX.S# = SX.SI AND SPJX.P* = PX.PI AND SPJX.Jl = JX.Jl AND SPJX.QTY < QTY ( 500 ) )

а) Сформулируйте этот запрос в словесной форме.

б) Возьмите на себя роль СУБД и выполните этот запрос по предложенному Код-дом алгоритму редукции. Можете ли вы указать какие-либо улучшения, которые целесообразно внести в данный алгоритм?

7.6. Выразите в терминах исчисления кортежей запрос Получить три самые тяжелые детали .

7.7. Рассмотрим отнощение спецификации материалов переменной-отнощения PART STRUCTURE, представленной в главе 4. (Соответствующие SQL-определения даны в ответе к упр. 4.6, а пример значения приведен на рис. 4.6.) Обратимся к широкоизвестному запросу разузлования деталей Получить номера деталей, которые на любых уровнях вхождения являются компонентами некоторой заданной детали (скажем, детали с номером Р1) . Результат этого запроса, например от-

ношение PART LIST (которое, безусловно, является отношением, производным от исходного отношения PART STRUCTURE), нельзя сформулировать в виде единственного выражения начального реляционного исчисления (или реляционной алгебры). Иначе говоря, производное отношение PART LIST не может быть получено с помощью единственного выражения начального реляционного исчисления (или реляционной алгебры). Почему?

7.8. Предположим, что переменную-отношение поставщиков S заменили набором переменных-отношений LS, PS, AS... по одной переменной-отношению для каждого города (например, переменная-отношение LS будет содержать кортежи только для поставщиков из Лондона). Предположим также, что неизвестно, какие именно существуют города, в которых находятся поставщики, и поэтому неизвестно, сколько имеется таких переменных-отношений. Рассмотрим запрос Существует ли в базе данных поставщик с номером S1? . Можно ли такой запрос выразить в терминах исчисления (или алгебры)? Обоснуйте свой ответ.

7.9. Покажите, что язык SQL является реляционно полным.

7.10. Существуют ли в языке SQL эквиваленты реляционных операторов EXTEND и SUMMARIZE?

7.И. Существуют ли в языке SQL эквиваленты операторов реляционных сравнений?

7.12. Приведите как можно больше различных формулировок на языке SQL для запроса Выбрать имена поставщиков детали с номером Р2 .

Упражнения по запросам

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

7.13. Дайте ответы к упр. 6.13-6.50 в терминах исчисления кортежей.

7.14. Дайте ответы к упр. 6.13-6.50 в терминах исчисления доменов.

7.15. Дайте ответы к упр. 6.13-6.50, используя средства языка SQL.

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

в дополнение к приведенному ниже списку обратитесь также к [4.7], где описывается несколько расширений языка SQL, предназначенных для работы с транзитивным замыканием и другими подобными операциями. Эти расширения очень напоминают соответствующие возможности, предусмотренные стандартом SQL3, которые кратко описываются в приложении Б. По вопросу внедрения подобных средств в реляционное исчисление обратитесь к главе 23.

7.1. Codd E.F. А Data Base Sublanguage Founded on the Relational Calculus Proc. 1971 ACM SIGFIDET Workshop on Data Description, Access and Control. - San Diego, Calif. -November, 1971.