    Глава 7 

    Реляционные операторы: 

    П. Реляционное исчисление 

    7.1. Введение 

    В главе 6 отмечалось, что часть реляционной модели, связанная с 
операторами, основана на реляционной алгебре, но с той же уверенностью можно 
сказать, что она основана и на реляционном исчислении. Другими словами, 
алгебра и исчисление представляют собой два альтернативных подхода. 
Принципиальное различие между ними следующее: алгебра предоставляет в явном 
виде набор операций (соединение, объединение, проекция и т.д.), которые можно 
использовать, чтобы сообщить системе, как в базе данных из определенных 
отношений реально построить необходимое отношение, в то время как исчисление 
представляет собой просто систему обозначений для определения необходимого 
отношения в терминах данных отношений. Рассмотрим, например, запрос "Получить 
номера и города поставщиков, поставляющих деталь Р2". Алгебраическая версия 
этого запроса выглядит приблизительно так (мы умышленно не используем 
формальный синтаксис главы 6): 
    •   Сначала образовать естественное соединение отношений S и SP по 
атрибуту S#. 
    •  Далее выбрать из результата этого соединения кортежи детали Р2. 
    •  И наконец, спроецировать результат этой выборки (выполнить проекцию) по 
атрибутам S# и CITY. 
    Формулировка этого запроса в терминах реляционного исчисления, для 
сравнения, выглядит приблизительно так: 
    •   Получить атрибуты S# и CITY для таких поставщиков, для которых 
существует поставка в отношении SP с тем же значением атрибута S# и со 
значением Р2 атрибута Р#. 
    При этом пользователь лишь устанавливает определенные характеристики 
необходимого отношения, оставляя системе решать, что соединять, проецировать и 
т.д., чтобы получить требуемый результат. Итак, можно сказать, что, по крайней 
мере внешне, формулировка запроса в терминах исчисления носит описательный 
характер, а алгебраическая формулировка — предписывающий. В исчислении просто 
описывается, в чем заключается проблема, а в алгебре описывается процедура 
решения этой проблемы. Или, говоря очень неформально, алгебра имеет 
процедурный характер (возможно, на высоком уровне, но все же процедурный, 
поскольку задает необходимые для выполнения процедуры), а исчисление — непроцедурный. 
    Подчеркнем, однако, что упомянутые отличия существуют только внешне. На 
самом деле алгебра и исчисление эквивалентны. Каждому выражению в алгебре 
соответствует эквивалентное выражение в исчислении, и точно так же каждому 
выражению в исчислении соответствует эквивалентное выражение в алгебре, т.е. 
между ними существует взаимно-однозначное соответствие. Различия связаны с 
разными стилями выражения: исчисление ближе к естественному языку, а алгебра — 
к языку программирования. Но повторяем еще раз: эти различия только кажущиеся, 
а не реальные; в частности, ни один из подходов нельзя назвать "более 
непроцедурным" по сравнению с другими. Вопрос эквивалентности двух подходов 
подробнее рассматривается ниже в этой главе. 

    Глава 7. Реляционные операторы: II. Реляционное исчисление	179 

    Реляционное исчисление основано на разделе математической логики, который 
называется исчислением предикатов. Идея использовать исчисление предикатов в 
качестве основы языка баз данных впервые была высказана в статье Кун-са 
(Kuhns) [7.8]. Понятие реляционного исчисления— т.е. специального применения 
исчисления предикатов в реляционных базах данных — было впервые предложено 
Коддом в [7.2], а в [7.3] Коддом был представлен язык, непосредственно 
основанный на исчислении и названный "Подъязык данных ALPHA". Сам язык ALPHA 
никогда не был реализован, однако язык QUEL [7.7, 7.12-7.14], который, 
конечно, был реализован и некоторое время серьезно конкурировал с языком SQL, 
очень походил на язык ALPHA, оказавший заметное влияние на конструкцию языка QUEL. 
    Основным средством исчисления согласно [7.2] является понятие переменной 
кортежа (также называемой переменной области значений). Вкратце, переменная 
кортежа — это переменная, которая "изменяется на" некотором отношении, т.е. 
переменная, допустимые значения которой — кортежи данного отношения. Другими 
словами, если переменная кортежа Т изменяется в пределах отношения R, в любое 
данное время переменная 7' представляет некоторый кортеж t отношения R. 
Например, запрос "Получить номера поставщиков из числа тех, которые находятся 
в Лондоне" может быть выражен на языке QUEL так: 

    RANGE OF SX IS S 
    RETRIEVE ( SX.S# ) WHERE SX.CITY = "London" 

    Переменная кортежа здесь — SX, а изменяется она на отношении S (оператор 
RANGE является оператором определения этой переменной). Оператор RETRIEVE 
означает следующее: "Для каждого возможного значения переменной SX выбрать 
компонент S# этого значения, если и только если компонент CITY имеет значение London." 
    В связи с тем, что первоначальное реляционное исчисление основано на 
переменных кортежа, и в отличие от исчисления доменов (см. ниже) его называют 
также исчислением кортежей. Исчисление кортежей подробно описано далее в этой главе. 
    В статье Лакроикса и Пиротте (Lacroix and Pirotte) [7.9] предлагается 
альтернативная версия исчисления, называемая исчислением доменов, в которой 
переменные кортежа заменяются переменными доменов, т.е. переменными, 
изменяемыми на доменах, а не на отношениях. Язык ILL, основанный на исчислении 
доменов, представлен теми же авторами в [7.10]. Можно привести и другие 
примеры языков исчисления доменов: FQL [7.11], DEDUCE [7.1] и (спорно) 
Query-By-Example, или QBE [7.15]. Наиболее известный из этих языков, пожалуй, 
QBE; существует несколько коммерческих реализаций этого языка. В общих чертах 
исчисление доменов будет описано ниже в этой главе, а язык QBE вкратце 
рассматривается в комментариях к [7.15]. 
    Замечание. Пытаясь сделать эту главу короче главы 6, мы умышленно 
пропускаем подробное описание реляционных присвоений, реляционных сравнений и 
операций обновления. Все эти элементы можно перенести на "почву" реляционного 
исчисления (в версии кортежей или доменов) вполне очевидным способом. 

    7.2. Реляционное исчисление (вариант кортежей) 

    Как и для алгебры в главе 6, необходимо ввести конкретный синтаксис для 
реляционного исчисления, чтобы обеспечить базис для дальнейшего изложения. 
Синтаксис исчисления определяется с помощью грамматики в форме Бэкуса-Наура 
(БНФ) и приведен на рис. 7.1. 
    Замечание. Квадратные скобки "[" и "]" используются в этой грамматике не 
как символы языка, а чтобы показать, что компоненты, заключенные в такие 
скобки, могут быть по умолчанию опущены. 

    180	Часть II. Реляционная модель 

    Некоторые замечание по грамматике 

    1.  Условное обозначение commalist (список элементов, разделенных 
запятыми) уже объяснялось в главе 4. 
    2.   Категории терминов relation (отношение), variable (переменная) и 
attribute (атрибут) определяются как идентификаторы. Они представляют имя 
отношения, имя переменной кортежа и имя атрибута соответственно. 

    range-variable-definition 
    ::=	RANGE OF variable IS range-item-coramalist ; 
    range-item 
    : :=    relation | expression 
    expression 
    : :=	(   target-item-commalist )   [ WHERE wff } 
    target-item 
    : :=	variable  \   variable .  attribute [ AS attribute ] 
    wff 
    : :=    condition I NOT wff 
    I condition AND uff I condition OR wff I IF condition THEN wff I EXISTS 
variable ( uff ) I FORALL variable ( wff ) I ( wff ) 

    Рис. 7.1. Грамматика для исчисления кортежей в форме Бэкуса-Наура (БНФ) 

    3.  Категория condition (условие) представляет или формулу WFF, 
заключенную в скобки (см. пункт 4), или простое скалярное сравнение вида 

    comparand 6 comparand 

    Здесь "9" обозначает любой используемый скалярный оператор сравнения (=, 
^, >, >, и т.п.), и каждый солрагапо:— это либо скалярная константа, либо 
значение атрибута, представленное ссылкой на атрибут в форме 
переменная.атрибут (иногда называемой "уточненным именем атрибута"). 
    Замечание. В системе, поддерживающей логический тип данных, условие 
(condition) также может состоять из ссылки на атрибут или из литерала этого 
типа данных. 
    4.  Категория wff представляет "правильно построенную формулу" 
(well-formulated formula — WFF, произносится "вэфф"). В последующих 
подразделах WFF обсуждается более детально. 
    Замечание. Не вдаваясь в подробности, отметим, что мы условились опускать 
ненужные скобки при написании WFF. 

    Переменные кортежей 

    Переменная кортежа (или области значений) определяется следующим образом: 

    RANGE OF  Т IS XI,   Х2,    ...,   Хп 

    Здесь Т— определяемая переменная кортежа, а Xi (/ = 1, 2,..., п) — либо 
имя отношения, либо выражение исчисления кортежей. Пусть Xi является 
отношением Ri (i - 1, 2, ..., п). Отношения /?/, R2, ..., Rn должны быть 
совместимы по типу, т. е. они должны иметь идентичные заголовки. Тогда 
переменная кортежа Т изменяется на 

    Глава 7. Реляционные операторы: II. Реляционное исчисление 181 

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

    RANGE OF SX IS S ; 
    RANGE OF SPX IS SP ; 
    RANGE OF SY IS ( SX ) WHERE SX.CITY = 'London', 
    ( SX ) WHERE EXISTS SPX ( SPX.S* = SX.S# AND SPX.P* = 'PI' ) ; 

    Переменная кортежа SY может принимать значения из множества кортежей S для 
поставщиков, которые или размещены в Лондоне, или поставляют деталь Р1 (или и 
то и другое). Пояснения будут даны позже. 
    Замечание. В интересах исторической правды заметим, что первоначальное 
определение исчисления в [7.2] не включало переменных кортежей, которые 
принимали бы значения чего-либо, кроме единственного именованного отношения. 
Вследствие этого начальное исчисление не поддерживает ни операцию UNION, ни— 
что более важно! — реальную возможность создания вложенных выражений. 
    Далее в этой главе подразумевается, что действуют следующие переменные 
области значений: 

    RANGE OF SX	IS S 
    RANGE OF SY	IS S 
    RANGE OF SZ	IS S 
    RANGE OF PX	IS P 
    
    RANGE OF PY	IS P 
    RANGE OF PZ	IS P 
    RANGE OF SPX	IS SP ; 
    RANGE OF SPY	IS SP ; 
    RANGE OF SPZ	IS SP ; 

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

    Свободные и связанные переменные 

    Каждый экземпляр переменной кортежа в формуле WFF является или свободным, 
или связанным. Объясним это понятие сначала в чисто синтаксических терминах, с 
примерами, а затем перейдем к обсуждению его значения. Под экземпляром 
переменной кортежа в формуле WFF будем подразумевать наличие имени переменной 
в формуле WFF а) в контексте ссылки атрибута типа Т.А (где А — атрибут 
отношения, значения которого принимает переменная 7), или б) как переменной, 
непосредственно следующей за одним из кванторов существования EXISTS или 
всеобщности FORALL (о кванторах речь идет ниже). Далее приведены правила, 
устанавливающие, каким будет данный экземпляр переменной кортежа (или кратко 
"экземпляр") — свободным или связанным. 
    1.  В простом сравнении, подобном "т. л < ал", все экземпляры свободны. 
    2.   Экземпляры в формулах WFF "( f )" и "NCT /' свободны или связаны в 
зависимости от того, свободны или связаны они в/ Экземпляры в формулах WFF "f 
AND g", "f OR g" и "IF f THEN g" свободны или связаны в зависимости от того, 
свободны или связаны они в/и g. 
    3.  Экземпляры переменной Т, которые свободны в формуле/ связаны в 
формулах WFF "EXISTS т ( f >" и "FORALL т ( f )". Другие экземпляры в 
формуле/— свободны или связаны в таких формулах WFF в соответствии с тем, 
свободны или связаны они в/ 

    182	Часть II. Реляционная модель 

    Примеры. 

    • Сравнения: 
    SX.S# = 'SI1 SX.S# = SPX.S# SPX.P# Ф PX.P# 
    Здесь все экземпляры SX, PX и SPX свободны. 
    • Логические формулы WFF: 
    PX.WEIGHT <  15 OR PX.WEIGHT > 25 
    NOT   (  SX.CITY =  'London1   ) 
    SX.S# = SPX.S# AND SPX.P# # PX.P# 
    IF PX.COLOR =  'Red'  THEN PX.CITY =   'London' 
    И снова все экземпляры SX, PX и SPX здесь свободны. 

    • Кванторные формулы WFF: 
    EXISTS SPX ( SPX.S* = SX.S# AND SPX.P# = 'P2' ) FORALL PX ( PX.COLOR = 
'Red' ) 
    Эти два примера объясняются ниже. 

    Кванторы 

    Существует два квантора: EXISTS (существует) и FORALL (для всех). По сути, 
если /— формула WFF, в которой переменная х свободна, то 

    EXISTS х  (  f ) 
    И 
    FORALL х  (  f ) 

    являются допустимыми формулами WFF, а переменная х связана в них обеих. 
Первая формула означает: "Существует по крайней мере одно такое значение 
переменной х, что вычисление формулы WFF/дает значение истина". Вторая формула 
означает: "Для всех значений переменной х вычисление формулы WFF/ дает 
значение истина". Предположим, например, что переменная х изменяется на 
множестве "Члены сената США в 1993 году", и предположим также, что/— формула 
WFF "х — женщина".1 Тогда формула "EXISTS х { f )" будет допустимой формулой 
WFF, имеющей значение истина (true)', формула "FORALL х ( f >" тоже будет 
допустимой формулой WFF, но вычисление ее значения будет давать ложь (false). 
    Теперь рассмотрим кванторы более тщательно. Сначала обсудим квантор 
существования EXISTS. Еще раз приводим пример из предыдущего раздела: 

    EXISTS SPX   (  SPX.S# = SX.SS AND SPX.P# =   'P2'   ) 

    Эта формула WFF может быть прочитана следующим образом: 
    Существует кортеж отношения SP, скажем SPX, для которого значение S# равно 
какому-нибудь значению SX.S#, а значение Р#равно Р2. 
    Каждый экземпляр SPX в этом примере связан. Отдельный экземпляр SX свободен. 
    Квантор существования EXISTS определяется формально как повторяющееся OR 
(ИЛИ). Другими словами, если R— это отношение с кортежами 77, 72,..., Тт\ Т— 
это переменная кортежа, которая изменяется на этом отношении; af(T) — это 
формула WFF, в которой Т используется как свободная переменная, то формула WFF 

    EXISTS  Т (   f  (   Т )   ) 

    определяется равносильно следующей формуле WFF: 

    false OR  (  f (   Tl )   )  OR  ...  OR  (  f (   En )   ) 

    1 Внимательный читатель заметит, что, строго говоря, это недопустимая 
формула согласно синтаксису, приведенному на рис. 7.1. Однако ее легко 
преобразовать в допустимую формулу WFF. 

    Глава 7. Реляционные операторы: II. Реляционное исчисление	183 

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

    Пример. Пусть отношение R содержит следующие кортежи: 

    (	1,	2,	3	) 
    (	1,	2,	4	) 
    (	1,	3,	4	) 

    Для простоты предположим, что компоненты кортежа могут быть 
идентифицированы по их порядковой позиции, так что можно ссылаться на них с 
помощью индексной ссылки 71/]. Тогда следующие выражения будут иметь 
приведенные ниже значения: 

    EXISTS   Т	(	Т[3]	>	1   )	:	true 
    EXISTS  Т	(	Г[2]	>	3  )	:	false 
    EXISTS  Т	(	Г[1]	>	1 OR Г[3]	= 4   )          :	true 

    Теперь рассмотрим квантор общности FORALL, повторно приведя пример с этим 
квантором из предыдущего раздела: 

    FORALL РХ   (  РХ.COLOR =  'Red'   ) 

    Эта формула WFF может быть прочитана следующим образом: 
    Для всех кортежей отношения Р, скажем РХ, значение атрибута COLOR в этих 
кортежах равно Red. 

    Два экземпляра РХ в этом примере связаны. 

    Так же, как EXISTS был определен как повторяющееся OR, квантор 
существования FORALL определяется как повторяющееся AND (И). Другими словами, 
если R, Тн/(Т) такие же, как рассматривались выше, то формула WFF 

    EORALL  Т (  ?  (   Т )   ) 

    определяется равносильно следующей формуле WFF: 

    true AND   (  f (   Tl  }   }  AND  ...  AND   (  f (   Bn )   ) 

    Заметьте, в частности, что результатом вычисления этого выражения будет 
истина, если отношение R пустое. 
    Пример. Если отношение R содержит те же самые кортежи, что и в предыдущем 
примере, то приведенные ниже выражения будут иметь такие значения: 

    FORALL	Т (	Г[1]	>	1   )	:   false 
    FORALL	Г (	Т[2]	>	1   )	:   true 
    FORALL	Г (	Т[1]	=	1 AND Г[3]	> 2  )     :  true 

    Замечание. Квантор FORALL включен в исчисление просто для удобства; он не 
является необходимым, так как приведенное ниже тождество показывает, что любая 
формула WFF, использующая квантор FORALL, может быть всегда заменена 
эквивалентной формулой WFF, использующей квантор EXISTS: 

    FORALL х   (   f" )   = NOT EXISTS X   (  NOT f ) 

    (проще говоря, выражение "все х, удовлетворяющие формуле/'— это то же 
самое, что и "нет таких х, которые бы не удовлетворяли формуле/'). 
    Например,утверждение(истинное) 
    "Для любого целого х существует целое у, такое что у > х" равносильно утверждению 
    "Не существует целого х такого, что не существует целого у, такого что у > х". 
    Но обычно легче выразить утверждение в терминах квантора FORALL, чем в 
терминах квантора EXISTS и двойного отрицания; другими словами, на практике 
удобнее использовать оба квантора. 

    Еще раз о свободных и связанных переменных 

    Предположим, что переменная х изменяется на множестве всех целых, и 
рассмотрим формулу WFF 
    EXISTS X   (  х > 3   ). 

    184	Часть II. Реляционная модель 

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

    EXISTS у  (  у > 3   ) 

    семантически идентична приведенной ранее. Теперь рассмотрим формулу WFF 

    EXISTS X  (  X > 3  )   AND х < 0. 

    Здесь имеется три экземпляра х, ссылающихся на две различные переменные. 
Первые два экземпляра связаны и могли бы быть заменены некоторой другой 
переменной у без изменения общего смысла формулы. Третий экземпляр переменной 
х не может быть безболезненно изменен. Таким образом, из двух формул WFF, 
приведенных ниже, первая эквивалентна рассмотренной формуле, а вторая — нет. 

    EXISTS у  ( у > 3  )   AND х < О EXISTS у  (  у > 3   )   AND у < О 

    Кроме того, обратите внимание, что истинностное значение первоначальной 
формулы WFF не может быть определено, если не знать значения свободной 
переменной х. В зависимости от этого значения формула WFF, в которой все 
переменные связаны, является истиной или ложью. 
    Дополнительная терминология. Формула WFF, в которой все переменные 
связаны, называется закрытой формулой WFF. Открытая формула WFF — это такая 
формула, которая содержит по крайней мере одну свободную переменную (т.е. не 
является закрытой). 

    Список целевых элементов 

    Каждый целевой элемент списка является или именем простой переменной, 
такой как Т, или выражением вида 

    Т.А  [ AS X } 

    Здесь Т— это переменная кортежа, А — это атрибут сопоставляемого отношения 
(сопоставляемое отношение является объединением множества совместимых по типу 
отношений, представленных выражениями исчисления кортежей; эти выражения будут 
описаны ниже), аХ— это имя атрибута результата вычисления списка целевых 
элементов (снова см. ниже). Обратите внимание, что часть "AS х" может быть 
опущена; в таком случае атрибут результата будет наследовать имя 
соответствующего сопоставляемого отношения (в рассматриваемом выше случае 
наследуемым именем было бы А). Если список целевых элементов включает 
какие-нибудь повторяющиеся имена, то должно быть указано новое имя. 
    Целевой элемент, который является просто именем переменной Т, определяется 
сокращенно для списка целевых элементов 

    T.KL,   T.A2,   ...,   Т. An, 

    где Л/, А2,..., An являются атрибутами отношения, сопоставляемого с Т. 

    Примеры: 

    sx.s# 
    SX.S# AS SNO 
    SX 
    SX.SS,   SX.CITY AS SCITY,   PX.PS,   PX.CITY AS PCITY 

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

    Глава 7, Реляционные операторы: II. Реляционное исчисление	185 

    в указанном списке целевых элементов, будут Т, U,..., V. Пусть отношения, 
на которых изменяются переменные кортежа, будут TR, UR,..., VR соответственно. 
Пусть результирующие   атрибуты   имеют   имена   (явно   определенные   или   
наследуемые) Х1,Х2,...,ХгЛогт: \.  Строится расширенное декартово произведение 

    TR TIMES UR TIMES . . . TIMES VR 

    2. Кортежи, которые не удовлетворяют формуле ^?? в фразе ШЕРЕ \et3\w o\v& 
ъс\ъ\ исключаются из результата шага 1. 
    3.  Результат шага 2 проецируется по атрибутам XI, Х2,..., Хг. 

    Выражения 

    Выражение исчисления кортежей имеет вид 

    (  target-item-commalist )   [ WHERE f ] 

    В этом выражении каждая свободная переменная в f (если такая есть) должна 
быть указана в целевом списке элементов target-item-commaiist. Как объяснялось 
выше, значение этого выражения определяется как проекция подмножества 
расширенного декартова произведения IK TIMES UR TIMES ... TIMES VR, для 
которого вычисление формулы f дает истину, или если фраза WHERE f опущена, то 
значение определяется как проекция всего расширенного декартова произведения. 
Рассматриваемая проекция берется по атрибутам XI, Х2,..., Хг (где Л7 
определены выше). 
    Замечание. Мы будем часто использовать соглашение о сокращении, согласно 
которому скобки, закрывающие целевой список элементов, могут быть по умолчанию 
опущены, если такой список содержит только один целевой элемент. 
    Примеры'. 

    (	SX.S# ) 
    {	SX.S# ) WHERE SX.CITY = 'London' 
    (	SX.S# AS SNO ) WHERE SX.CITY = 'London' 
    (	SX.S#, SX.CITY ) WHERE EXISTS SPX ( SPX.Stf = SX.Stt AND 
    SPX.P* = 'P2' ) 
    (	SX.Stt, PX.P# ) WHERE SX.CITY * PX.CITY 
    (	SX ) 

    Первое из этих выражений означает множество всех номеров поставщиков в 
отношении S; второе — подмножество номеров поставщиков, размещенных в Лондоне. 
Третье выражение такое же, за исключением того, что один атрибут результата 
переименовывается в SNO. Четвертое выражение — это представленный в терминах 
исчисления кортежей запрос "Получить номера и города для поставщиков, которые 
поставляют деталь Р2" (он является примером запроса, приведенного в начале 
главы; заметьте, что этот пример — первый, в котором действительно требуются 
скобки, заключающие целевой список элементов). Пятое выражение является 
представленным в терминах исчисления кортежей запросом "Получить такие пары 
номера поставщиков-номера деталей, в которых поставщик и деталь не размещены в 
одном городе". И последнее выражение означает целое отношение поставщиков. 

    7.3. Примеры 

    Представляем несколько примеров использования реляционного исчисления 
кортежей при формулировке запросов. Для сравнения с реляционной алгеброй 
некоторые примеры соответствуют подобным из главы 6. Как и в той главе, любые 
примеры можно расширить, включив в них завершающий шаг присвоения и присвоив 
значение выражения некоторому именованному отношению; этот шаг для краткости опускается. 

    7.3.1. Получить номера поставщиков из Парижа со статусом больше 20 

    ( SX.S# WHERE SX.CITY = 'Paris' AND SX.STATUS > 20 

    186	Часть II. Реляционная модель 

    7.3.2. Получить все такие пары номеров поставщиков, что два поставщика 
размещаются в одном городе 

    ( SX.S* AS FIRSTS*, SY.S* AS SECONDS! ) WHERE SX.CITY = SY.CITY AND SX.S# 
< SY.S# 

    Замечание. Спецификации "AS FIRSTS*" и "AS SECONDS*" дают имена атрибутам 
результата', следовательно, такие имена недоступны для использования в фразе 
WHERE и потому второе сравнение в фразе WHERE — "sx.s# < SY.S*", а не "FIRSTS* 
< SECONDS*". 

    7.3.3. Получить имена поставщиков, которые поставляют деталь Р2 

    SX.SNAME WHERE EXISTS SPX ( SPX.S* = SX.S* AND SPX.P* = 'P2' ) 

    7.3.4. Получить имена поставщиков, которые поставляют по крайней мере одну 
красную деталь 

    SX.SNAME WHERE EXISTS SPX ( SX.S* = SPX.S* AND 
    EXISTS PX ( PX.P* = SPX.P# AND PX.COLOR = 'Red1 ) ) Или эквивалентная 

формула (но в предваренной нормальной форме, в которой все кванторы 
записываются в начале формулы WFF): 

    SX.SNAME WHERE EXISTS SPX ( EXISTS PX ( SX.S* = SPX.S* AND 
    SPX.P* = PX.P* AND PX.COLOR = 'Red' ) ) 

    Предваренная нормальная форма не является более или менее правильной по 
сравнению с другими формами, но немного попрактиковавшись можно убедиться, что 
в большинстве случаев это наиболее естественная формулировка запросов. Кроме 
того, эта форма позволяет уменьшить количество скобок, как показано ниже. 
Формулу WFF 

    quant-l  vble-1   {  quant-2 vble-2  (  wff )   ) 

   (где каждый из кванторов quant-i и quant-2 представляет или квантор 
EXISTS, или квантор FORALL, vbie-i и vbie-2— имена переменных) по умолчанию 
можно однозначно сократить к виду 

    quant-l vble-1 quant-2 vble-2  (  wff ) 

    Таким образом, приводимое выше выражение исчисления можно переписать (при 
желании) следующим образом: 

    SX.SNAME WHERE EXISTS SPX EXISTS PX ( SX.S* = SPX.S* AND 
    SPX.P* = PX.P* AND PX.COLOR = 'Red' ) 

    Однако для ясности мы будем продолжать показывать все скобки во всех 
остальных примерах. 
    7.3.5. Получить имена поставщиков, которые поставляют по крайней мере одну 
деталь, поставляемую поставщиком S2 

    SX.SNAME WHERE EXISTS SPX ( EXISTS SPY ( SX.S* = SPX.S* AND 
    SPX.P* = SPX.P* AND SPY.S* = 'S2' ) ) 

    7.3.6. Получить имена поставщиков, которые поставляют все детали 

    SX.SNAME WHERE FORALL PX ( EXISTS SPX ( SPX.S* = SX.S* AND 
    SPX.P* = PX.P* ) ) 

    Или равносильное выражение без использования квантора FORALL: 

    SX.SNAME WHERE NOT EXISTS PX ( NOT EXISTS SPX 
    ( SPX.S* = SX.S* AND SPX.P* = PX.P* ) ) 

    Отметим, что содержание этого запроса — "имена поставщиков, которые 
поставляют все детали" — является точным на 100% (в отличие от случая с 
алгебраическим аналогом при использовании оператора DIVIDEBY). 

    Глава 7. Реляционные операторы: II. Реляционное исчисление	187 

    7.3.7. Получить имена поставщиков, которые не поставляют деталь Р2 

    SX.SNAME WHERE NOT EXISTS SPX 
    (   SPX.S* = SX.Sft AND SPX.Ptt =   'P2'   ) 

    Обратите внимание, как просто это решение можно получить из примера 7.3.3. 
    7.3.8. Получить номера поставщиков, которые поставляют по крайней мере все 
детали, поставляемые поставщиком S2 

    SX.S# WHERE FORALL SPY ( SPY.Sft # 'S2' OR 
    EXISTS SPZ   (   SPZ.S* = SX.S# AND SPZ.Pt = SPY.P#   )   ) 

    Переформулируем запрос в соответствии с приведенным в выражении: "Получить 
номера поставщиков, скажем SX, таких, что для всех поставок SPY поставка 
осуществляется либо не от поставщика S2, либо если от поставщика S2, то 
существует поставка SPZ детали SPY от поставщика SX". 
    Введем другое синтаксическое соглашение, чтобы облегчить формулирование 
таких сложных запросов, как этот, а именно: явную синтаксическую форму для 
оператора логической импликации. Если/и g— формулы WFF, то выражение 
логической импликации 

    IF f THEN g 

    также будет формулой WFF с семантикой, идентичной семантике формулы 

    ( NOT / )   OR g 

    Таким образом, выражение, приведенное выше, может быть переписано (при 
желании) так: 

    SX.S# WHERE FORALL SPY ( IF SPY.S* = 'S2' THEN 
    EXISTS SPZ ( SPZ.Stt = SX.S# AND SPZ.P# = SPY.P# ) ) 

    Дадим словесную формулировку: "Получить номера поставщиков, скажем SX, 
таких, что для всех поставок SPY в случае поставки от поставщика S2 существует 
поставка SPZ детали SPY от поставщика SX". 
    7.3.9. Получить номера деталей, которые или весят более 16 фунтов, или 
поставляются поставщиком S2, или и то и другое 

    RANGE OF PU IS PX.P# WHERE PX.WEIGHT >  16, 
    SPX.P* WHERE SPX.S* =   'S2'   ; PO.P# 

    В реляционном алгебраическом эквиваленте здесь могло бы использоваться 
явное объединение. 
    Ради интереса, покажем альтернативную формулировку этого запроса. Однако 
тот факт, что каждый номер детали в отношении SP присутствует и в отношении Р, 
делает эту вторую формулировку не в "стиле объединения". 

    РХ.Р# WHERE PX.WEIGHT > 16 
    OR   EXISTS SPX ( SPX.Ptt = PX.P# AND SPX.S# = 'S21 ) 

    7.4. Реляционное исчисление и реляционная алгебра 

    В начале этой главы утверждалось, что реляционная алгебра и реляционное 
исчисление в своей основе эквивалентны. Обсудим это утверждение более 
подробно. Вначале Кодд показал в своей статье [7.2], что алгебра, по крайней 
мере, мощнее исчисления. (Для краткости в этом разделе будет использован 
неопределенный термин "исчисление" для обозначения исчисления кортежей.) Он 
сделал это, придумав алгоритм, называемый "алгоритмом редукции Кодда", с 
помощью которого любое выражение исчисления можно преобразовать в семантически 
эквивалентное выражение алгебры. Мы не станем приводить здесь полностью этот 
алгоритм, а ограничимся до

    188	Часть II. Реляционная модель 

    вольно сложным примером, иллюстрирующим в общих чертах, как этот алгоритм функционирует.1 
    В качестве основы для нашего примера используется не знакомая база данных 
поставщиков и деталей, а расширенная версия базы данных, встречающаяся в 
упражнениях главы 4 и в других главах. Для удобства на рис. 7.2 приводится 
набор примерных значений для этой базы данных (копия рис. 4.6). 

    S								SPJ 
    s#	SNAME		STATUS	CITY					S#	P#	J#	C?TY 
    SI	Smith		20	London					SI	PI	Jl	200 
    S2	Jones		10	Paris					SI	PI	J4	700 
    S3	Black		30	Paris					S2	P3	Jl	400 
    S4	Clark		20	London					S2	P3	J2	200 
    S5	Adams		30	Athens					S2	P3	J3	200 
    S2	P3	J4	500 
    S2	P3	J5	600 
    р	P#	PNAME		COLOR		WEIGHT		CITY		S2	P3	J6	400 
    
    PI	Nut		Red		12		London		S2	P3	J7	800 
    P2	Bolt		Green		17		Paris		S2	P5	J2	100 
    P3	Screw		Blue		17		Rome		S3	P3	Jl	200 
    P4	Screw		Red		14		London		S3	P4	J2	500 
    P5	Cam		Blue		12		Paris		S4	P6	J3	300 
    P6	Cog		Red		19		London		S4	P6	J7	300 
    S5	P2	J2	200 
    S5	P2	J4	100 
    J	J#		JNAME		CITY					S5	P5	J5	500 
    Jl		Sorter		Paris					S5	P5	J7	100 
    J2		Display		Rome					S5	P6	J2	200 
    J3		OCR		Athens					S5	PI	J4	100 
    J4		Console		Athens					S5	P3	J4	200 
    J5		RAID		London					S5	P4	J4	800 
    J6		EDS		Oslo					S5	P5	J4  '	400 
    07		Tape		London					S5	P6	J4	500 
    
    
    Рис. 7.2. База данных поставщиков, деталей и проектов (значения для примера) 

    Рассмотрим запрос: "Получить имена и города поставщиков, обеспечивающих по 
крайней мере один проект в городе Атенс (Athens) с поставкой по крайней мере 
50 штук каждой детали". Выражение исчисления для этого запроса следующее: 

    ( SX.SNAME, SX.CITY ) WHERE EXISTS JX FORALL PX EXISTS SPJX 
    ( JX.CITY = 'Athens' AND JX.J# = SPJX.Jtt AND PX.P# = SPJX.P# AND SX.S# = 
SPJX.Stt AND SPJX.QTY > 50 ) 

    Здесь SX, PX, JX и SPJX — переменные кортежей, берущие свои значения из 
отношений S, Р, J и SPJ соответственно. Теперь покажем, как вычислить это 
выражение, чтобы добиться необходимого результата. 
    Шаг I. Для каждой переменной кортежа выбираем ее область значений (т.е. 
набор всех значений для этой переменной), если это возможно. Выражение 
"выбираем, если возможно" подразумевает, что существует условие выборки, 
встроенное в фразу 

    1 В действительности алгоритм, представленный в [7.2], содержит небольшую 
ошибку [7.4]. Более того, версия исчисления, определенная в этой статье, не 
включала аналога операции объединения, а значит, исчисление Кодда значительно 
менее мощное, чем его алгебра. Тем не менее, утверждение о том, что алгебра и 
исчисление, включающее аналог операции объединения, эквивалентны, является, 
как доказано многими авторами, истиной (см. [6.13]). 

    Глава 7. Реляционные операторы: II. Реляционное исчисление 189 

    WHERE, которую можно использовать, чтобы сразу исключить из рассмотрения 
некоторые кортежи. В нашем случае выбираются следующие наборы кортежей: 
    SX	:	Все кортежи отношения S	5 кортежей 
    РХ	:	Все кортежи отношения Р	6 кортежей 
    JX	:	Кортежи отношения J, в которых CITY = 'Athens'	2 кортежа 
    SPJX	:	Кортежи отношения SPJ, в которых CITY > 50	24 кортежа 

    Шаг 2. Строим декартово произведение диапазонов, выбранных на первом шаге. Получим 

    з#	SN	scare	CITY	P#	?N	COLOR	WEICHT	CITY	J#	JN	CITY	Sff	P#	J#	QTY 
    31	Sm	20	Lon	Pi	Nt	Red	12	Lon	J3	OR	Ath	SI	PI	Jl	200 
    SI	Sm	20	Lon	PI	Nt	Red	12	Lon	J3	OR	Ath	SI	PI	J4	700     
    
    
    и т.д. Полное произведение содержит 5*6*2*24 = 1440 кортежей. Замечание. 
Для экономии места мы не приводим его полностью. Мы также не переименовывали 
атрибутов (это следовало сделать во избежание двусмысленности), а просто 
расположили их в таком порядке, чтобы было видно, какой атрибут S#, например, 
относится к отношению S, а какой — к отношению SPJ. Это также сделано для 
сокращения изложения. 
    
    Шаг 3. Осуществляем выборку из произведения, построенного на втором шаге в 
соответствии с частью "условие соединения" фразы WHERE. В нашем примере эта 
часть следующая: 

    JX.J# = SPJX.J* ANDPX.Ptt = SPJX.Ptt AND SX.Sft  =SPJX.S# 

    Поэтому из произведения исключаются кортежи, для которых значение S# 
поставщика не равно значению S# поставки, значение Р# детали не равно значению 
Р# поставки, значение J# проекта не равно значению J# поставки, после чего 
получаем подмножество декартова произведения, состоящее только из десяти кортежей: 
    
    s#	SN	STATUS	CITY	P#	PN	COLOR	WEIGHT	CITY	J#	JN	CITY	S#	P#	J#	OTY 
    SI	Sm	20	Lon	PI	Nt	Red	12	Lon	J4	Cn	Ath	SI	PI	J4	700 
    S2	Jo	10	Par	P3	Sc	Blue	17	Ron	J3	OR	Ath	S2	P3	J3	200 
    S2	Jo	10	Par	P3	Sc	Blue	17	Ron	J4	Cn	Ath	S2	P3	J4	200 
    S4	Cl	20	Lon	P6	Cg	Red	19	Lon	J3	OR	Ath	34	P6	J3	300 
    S5	Ad	30	Ath	P2	Bt	Green	17	Par	J4	Cn	Ath	35	P2	J4	100 
    S5	Ad	30	Ath	PI	Nt	Red	12	Ion	J4	Cn	Ath	35	PI	J4	100 
    S5	Ad	30	Ath	P3	Sc	Blue	17	Ron	J4	Cn	Ath	35	P3	J4	200 
    S5	Ad	30	Ath	P4	Sc	Red	14	Lon	J4	Cn	Ath	S5	P4	J4	800 
    S5	Ad	30	Ath	P5	Cm	Blue	12	Par	J4	Cn	Ath	S5	P5	J4	400 
    S5	Ad	30	Ath	P6	Cg	Red	19	Lon	J4	Cn	Ath	S5	P6	J4	500 

    (Отношение, конечно, представляет эквивалент соединения.) Шаг 4. Применяем 
кванторы справа налево следующим образом: 
    •   Для квантора "EXISTS RX" (где RX— переменная кортежа, принимающая 
значение на некотором отношении К) проецируем текущий промежуточный результат, 
чтобы исключить все атрибуты отношения R. 
    •  Для квантора "FORALL кх" делим текущий промежуточный результат на 
отношение "выбранной области значений", соответствующее RX, которое было 
получено выше. При выполнении этой операции также будут исключены все атрибуты 
отношения R. 
    В нашем примере имеем следующие кванторы: 

    EXISTS JX FORALL PX EXISTS SPJX 

    Выполняем соответствующие операции. 
    1.  EXISTS SPJX. Проецируем, исключая атрибуты отношения SPJ (SPJ.S#, 
SPJ.P#, SPJ.J# и SPJ.QTY). В результате получаем: 

    190 Часть II. Реляционная модель 

    s#	SN	STATUS	CITY	P#	PN	COLOR	WEIGHT	CITY	J#	JN	CITY 
    SI	Sm	20	Lon	PI	Nt	Red	12	Lon	J4	Cn	Ath 
    S2	Jo	10	Par	P3	Sc	Blue	17	Rom	J3	OR	Ath 
    S2	Jo	10	Par	P3	Sc	Blue	17	Rom	J4	Cn	Ath 
    S4	Cl	20	Lon	P6	Cg	Red	19	Lon	J3	OR	Ath 
    S5	Ad	30	Ath	P2	Bt	Green	17	Par	J4	Cn	Ath 
    S5	Ad	30	Ath	PI	Nt	Red	12	Lon	J4	Cn	Ath 
    S5	Ad	30	Ath	P3	Sc	Blue	17	Rom	J4	Cn	Ath 
    S5	Ad	30	Ath	P4	Sc	Red	14	Lon	J4	Cn	Ath 
    S5	Ad	30	Ath	P5	Cm	Blue	12	Par	J4	Cn	Ath 
    S5	Ad	30	Ath	P6	Cg	Red	19	Lon	J4	Cn	Ath 

    2.  FORALL PX. Делим на отношение Р. В результате получаем: 

    s#	SN	STATUS	CITY	J#	JNAME	CITY 
    S5	Adams	30	Athens	J4	Console	Athens 
    (Теперь у нас есть место, чтобы показать отношение полностью, без сокращений.) 

    3.  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 
[7.7], который основывается на исчислении, одно из возможных применений 
заключается в том, чтобы можно было брать запрос в том виде, в каком он 
предоставляется пользователем (являющийся, по существу, просто выражением 
исчисления), и применять к нему алгоритм получения эквивалентного 
алгебраического выражения. Это алгебраическое выражение, конечно, содержит 
множество алгебраических операций, которые согласно определению по своей 
природе выполнимы. (Следующий шаг состоит в продолжении оптимизации этого 
алгебраического выражения. Об этом в последующих главах книги.) 
    Также необходимо отметить, что восемь алгебраических операторов Кодда 
являются мерой оценки выразительной силы любого языка баз данных 
(существующего или предлагаемого). Это уже кратко упоминалось в главе 6; 
давайте обсудим этот вопрос подробнее. 

    Глава 7. Реляционные операторы: II. Реляционное исчисление 191 

    Во-первых, язык называется реляционно полным, если он по своим 
возможностям, по крайней мере, не уступает реляционному исчислению, т.е. любое 
отношение, которое можно определить с помощью реляционного исчисления, также 
можно определить и с помощью некоторого выражения рассматриваемого языка 
[7.2]. (В главе б отмечалось, что "реляционно полный" — значит, не уступающий 
по возможностям алгебре, а не исчислению, но, как читатель вскоре убедится, 
это то же самое. По сути, из существования алгоритма преобразования Кодда 
немедленно следует, что реляционная алгебра обладает реляционной полнотой.) 
    Реляционную полноту можно рассматривать как основную меру возможностей 
выборки и выразительной силы языков баз данных вообще. В частности, так как 
исчисление и алгебра— реляционно полные, они могут служить базисом для 
проектирования языков, не уступающих им по выразительности, без необходимости 
пересортировки для использования циклов — особенно важное замечание, если язык 
предназначается конечным пользователям, хотя оно также применимо, если язык 
предназначается прикладным программистам. 
    Далее, поскольку алгебра реляционно полная, то, чтобы доказать, что 
некоторый язык L обладает реляционной полнотой, достаточно показать, что в 
языке L есть аналоги всех восьми алгебраических операций (на самом деле 
достаточно показать, что в нем есть аналоги пяти примитивных операций) и что 
операндами любой операции языка L могут быть любые выражения этого языка. Язык 
SQL — это пример языка, реляционную замкнутость которого можно показать таким 
способом (это обсуждается в главе 8). Язык QUEL — еще один такой пример. В 
действительности на практике часто проще показать, что в данном языке есть 
эквиваленты алгебраических операций, чем найти в нем эквиваленты выражений 
исчисления. Именно поэтому реляционная полнота обычно определяется в терминах 
алгебраических выражений, а не выражений исчисления. 
    При этом важно понимать, что реляционная полнота не обязательно влечет за 
собой полноту какого-либо другого рода. Например, необходимо, чтобы язык также 
обеспечивал "вычислительную полноту", т.е. мог вычислять все вычислимые 
функции. Заметим, что согласно нашему определению исчисление не обладает 
полнотой такого рода, хотя на практике такая полнота для языка баз данных 
весьма желательна; вычислительная полнота — это одна из причин, побудивших 
ввести в алгебру операции EXTEND и SUMMARIZE (которые обсуждались в главе 6). 
В следующем разделе описано, как можно расширить исчисление, чтобы обеспечить 
наличие аналогов этих операций. 
    Вернемся к вопросу эквивалентности алгебры и исчисления. Мы на примере 
показали, что любое выражение исчисления можно преобразовать в алгебраический 
эквивалент, а значит, алгебра, по крайней мере, не уступает по возможностям 
исчислению. Можно показать обратное: каждое алгебраическое выражение можно 
преобразовать в эквивалент исчисления, а значит, исчисление, по крайней мере, 
не уступает по возможностям алгебре; доказательство смотрите, например, в 
[7.16]. Отсюда следует, что алгебра и исчисление эквивалентны. 

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

    Добавить вычислительные возможности в исчисление довольно просто: 
необходимо расширить определение ко.мпарандов и целевых элементов так, чтобы 
они включали новую категорию — скалярные выражения, в которых операнды, в свою 
очередь, могут включать литералы, ссылки на атрибуты и (или) ссылки на 
итоговые функции. Для целевых элементов также требуется использовать 
спецификацию вида "AS attribute" для того, чтобы дать подходящее имя 
результирующему атрибуту, если нет очевидного наследуемого имени. 
    Мы считаем, что смысл скалярного выражения легко воспринимается, и потому 
опускаем здесь подробности. Однако синтаксис для ссылок на итоговые функции мы 
покажем: aggregate-function ( expression [, attribute ] ) 

    192	Часть II. Реляционная модель 

    Здесь итоговыми функциями (aggregate-function) могут быть COUNT, SUM, AVG, 
МАХ или MEN (возможны, конечно, и некоторые другие), egression— это выражение 
исчисления кортежей (вычисляющее отношение), a attribute— это такой атрибут 
результирующего отношения, по которому подсчитывается итог. Для функции COUNT 
аргумент attribute не нужен и опускается; для других итоговых функций его 
можно опустить по умолчанию, если и только если вычисление аргумента 
expression дает отношение степени один и в таком случае единственный атрибут 
результата вычисления выражения egression подразумевается по умолчанию. 
Кстати, заметьте, что ссылка на итоговую функцию возвращает скалярное значение 
и поэтому допустима в качестве операнда скалярного выражения. 
    Из всего сказанного можно сделать следующие выводы: 
    1. Итоговая функция действует в некоторых отношениях как новый тип 
квантора. В частности, если аргумент expression в данной ссылке на итоговую 
функцию представляется в виде "(tic) WHERE f", где tic— целевой элемент списка 
    (target-item-ccmmalist), a f— ЭТО формула WFF, И ССЛИ ЭКЗСМПЛЯр переменной 
КОр
    тежа Г свободен в формуле/ то такой экземпляр переменной Г связан в ссылке 
на итоговую функцию 
    aggregate-function ((tic ) WHERE f [, attribute ]) 
    2.  Для тех читателей, которые хорошо знают SQL, заметим, что с помощью двух 
    Следующих  аргументов   В  ССЫЛКе   на   ИТОГОВУЮ   фуНКЦИЮ,   expression 
И   attribute, 
    можно избежать необходимых для SQL специальных приемов использования 
оператора DISTINCT для исключения дублирующих кортежей, если это требуется, 
перед выполнением итоговой операции. Вычисление аргумента expression дает 
отношение, из которого повторяющиеся кортежи всегда исключаются по 
определению. Аргумент attribute обозначает атрибут такого отношения, по 
которому выполняются итоговые вычисления, а дублирующие значения перед 
подсчетом итога из такого атрибута не удаляются. Конечно, атрибут может не 
содержать никаких дублирующих значений в любом случае, в частности, если такой 
атрибут является первичным ключом. 
    Теперь давайте рассмотрим несколько примеров. Чтобы облегчить сравнение с 
реляционной алгеброй, некоторые примеры соответствуют подобным примерам из 
главы 6. 
    7.5.1. Получить номера деталей и их вес в граммах, если этот вес превышает 
10 000 
    ( РХ.Р#, РХ.WEIGHT * 454 AS GMWT ) WHERE PX.WEIGHT * 454 > 10000 
    Заметьте, что спецификация "AS GMWT" дает имя соответствующему атрибуту 
результата. Поэтому такое имя недоступно для использования в фразе WHERE и 
потому выражение "PX.WEIGHT * 454" записывается в двух местах. 
    7.5.2. Получить всех поставщиков, добавив для каждого литеральное значение "Поставщик" 
    ( SX,   'Поставщик'  AS TAG ) 
    7.5.3. Получить каждую поставку с полными данными о входящих в нее деталях 
и общим весом поставки 
    ( SPX.St, SPX.QTY, РХ, PX.WEIGHT * SPX.QTY AS SHIPWT ) WHERE PX.P# = SPX.P# 
    7.5.4. Для каждой детали получить ее номер и общее поставляемое количество 
    ( РХ.Р#, SUM ( SPX WHERE SPX.P* = РХ.Р#, OTY ) AS TOTCTY ) 

    Глава 7. Реляционные операторы: II. Реляционное исчисление	193 
    7 Введение в системы баз данных 

    Заметьте, что вместо фразы вида "BY (P#)" ссылка на итоговую функцию 
включает в качестве первого аргумента выражение исчисления; вычисление этого 
выражения (для данной детали) дает точное множество кортежей, по которому 
подсчитывается итог. Также стоит отметить, что результат будет включать один 
кортеж для каждой детали, даже для деталей, которые в данное время не 
поставляются никакими поставщиками (количество для каждой такой детали будет 
равно нулю). 
    7.5.5. Получить общее количество поставляемых деталей 

    SUM   (SPX,   QTY  )   AS GFANDTOTAL  ) 

    В отличие от своего эквивалента — оператора SUMMARIZE, это выражение 
возвращает корректный результат (а именно нуль), если отношение SP пустое. 
    7.5.6. Для каждого поставщика получить его номер и общее количество 
поставляемых им деталей 

    { SX.S#, COUNT ( SPX WHERE SPX.S# = SX.S# ) AS #_OF_PARTS ) 

    В отличие от своего эквивалента — оператора SUMMARIZE, это выражение дает 
результат, который включает кортеж для поставщика S5 (с нулевым количеством). 
    7.5.7. Получить города, в которых хранится а) более пяти красных деталей; 
б) не более пяти красных деталей 

    PX.CITY WHERE COUNT   (   PY WHERE PY.CITY = PX.CITY 
    AND PY.COLOR =   'Red'   )   > 5 

    Это выражение представляет собой решение задачи для части (а). В отличие 
от своего эквивалента — оператора SUMMARIZE, это решение может быть 
преобразовано в решение для части (б) простой заменой знака ">" на "<". 

    7.6. Реляционное исчисление (вариант доменов) 

    Как указано выше в этой главе, реляционное исчисление, ориентированное на 
домены (или исчисление доменов), отличается от исчисления кортежей тем, что в 
нем используются переменные доменов вместо переменных кортежей, т.е. 
переменные, принимающие свои значения в пределах домена, а не отношения. 
(Замечание. "Переменную домена" было бы лучше назвать "скалярной переменной", 
так как ее значения — это элементы домена, т.е. скаляры, а не сами домены.) 
Здесь мы лишь кратко обсудим исчисление доменов. 
    С практической точки зрения большинство очевидных различий между версиями 
исчисления для доменов и кортежей основано на том, что версия для доменов 
поддерживает дополнительную форму условия, которое мы будем называть условием 
принадлежности. В общем виде условие принадлежности можно записать так: R ( 
pair, pair,   ...  ), 
    где R — это имя отношения, а каждая пара pair имеет вид A:v (где А — 
атрибут отношения Л, a v — или переменная домена, или литерал). Проверка 
условия дает значение истина, если и только если существует кортеж в отношении 
R, имеющий определенные значения для определенных атрибутов. Например, 
вычисление выражения 

    SP  ( S#:'SI1,   P#:'P1'   ) 

    дает значение истина, если и только если в отношении SP существует кортеж 
со значением S#, равным S1, и значением Р#, равным Р1. Аналогично, условие принадлежности 

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

    принимает значение истина, если и только если в отношении SP существует 
кортеж со значением S#, эквивалентным текущему значению переменной домена SX 
(какому бы то ни было), и значением Р#, эквивалентным текущему значению 
переменной домена РХ (опять же какому бы то ни было). 

    194	Часть II. Реляционная модель 

    Далее будем подразумевать существование переменных доменов с именами, 
образуемыми добавлением букв X, Y, Z,... к соответствующим именам доменов, 
исключая такие имена доменов, которые оканчиваются на "#" и в которых символ 
"#" будет пропускаться. Напомним читателю, что в базе данных поставщиков и 
деталей каждый атрибут имеет такое же имя, как и соответствующий ему домен, за 
исключением атрибутов SNAME и PNAME, для которых соответствующий домен 
называется просто NAME. 
    Примеры выражений исчисления доменов: 

    ( SX ) 
    ( SX ) WHERE S ( S#:SX ) { SX ) WHERE S ( S#:SX, CITY:'London1 ) ( SX, 
CITYX ) WHERE S ( S#:SX, CITY:CITYX ) AND SP ( S#:SX, P#:'P2' ) 
    ( SX, PX ) WHERE S (S#:SX, CITY:CITYX ) AND P ( P#:PX, CITY:CITYY ) AND 
CITYX * CITYY 

    Если говорить нестрого, первое выражение означает множество всех номеров 
поставщиков;1 второе— множество всех номеров поставщиков отношения S; третье — 
подмножество номеров поставщиков из города Лондон. Следующее — это выраженный 
в терминах исчисления доменов запрос "Получить номера и города поставщиков, 
поставляющих деталь Р2" (заметьте, что для этого запроса, выраженного в 
терминах исчисления кортежей, требовался квантор существования; заметьте 
также, что это первый из приведенных здесь примеров, где действительно 
необходимы скобки для списка целевых элементов). И последнее выражение — это 
представленный в терминах исчисления доменов запрос "Получить такие пары 
номера поставщиков-номера деталей, что поставщики и детали размещены в одном городе". 
    Приводим некоторые рассмотренные выше примеры, но выраженные в терминах 
исчисления доменов. 

    7.6.1. Получить номера поставщиков из Парижа со статусом больше 20 


    SX WHERE EXISTS STATUSX (STATUSX > 20 AND S ( S#:SX, STATUS:STATUSX, 
CITY:'Paris' ) ) 

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

    7.6.2. Получить все такие пары номеров поставщиков, что два поставщика 
размещаются в одном городе 

    ( SX AS FIRSTS#, SY AS SECONDS* ) 
    WHERE EXSIST CITYZ 
    ( S ( S#:SX, CITY:CITYZ) AND S ( S#:SY, CITY:CITYZ) AND SX < SY ) 

    7.6.3. Получить имена поставщиков, которые поставляют по крайней мере одну 
красную деталь 

    NAMEX WHERE EXISTS SX EXISTS PX 
    ( S ( S#:SX, SNAME:NAMEX ) AND SP ( S#:SX, P#:PX ) AND P ( P#:PX, 
COLOR:'Red' ) )	• 

    7.6.4. Получить имена поставщиков, которые поставляют по крайней	| мере 
одну деталь, поставляемую поставщиком S2 

    NAMEX WHERE EXISTS SX EXISTS PX 
    (  S   (  S#:SX,   SNAME:NAMEX  ) 

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

    Глава 7. Реляционные операторы: II. Реляционное исчисление	195 

    AND SP   (  S#:SX,   P#:PX  ) AND SP   (  S#:'S21,   P#:PX  )   ) 

    7.6.5. Получить имена поставщиков, которые поставляют все детали 

    NAMEX WHERE EXISTS SX ( S ( S#:SX, SNAME:NAMEX ) AND FORALL PX ( IF P ( 
P#:PX ) 
    THEN SP ( S#:SX, P#:PX ) ) ) 

    7.6.6. Получить имена поставщиков, которые не поставляют деталь Р2 

    NAMEX WHERE EXISTS SX ( S ( S#:SX, SNAME:NAMEX ) 
    AND NOT SP (S#:SX, P:'P2' ) ) 

    7.6.7. Получить номера поставщиков, которые поставляют по крайней мере все 
детали, поставляемые поставщиком S2 

    SX WHERE FORALL PX ( IF SP ( S# : ' S2 ', P#: PX } 
    THEN SP ( S#:SX, P#:PX ) ) 

    7.6.8. Получить номера деталей, которые или весят более 16 фунтов, или 
поставляются поставщиком S2, или и то и другое 

    PX WHERE EXISTS WEIGHTX 
    ( P ( P#:PX, WEIGHT:WEIGHTX ) 
    AND WEIGHTX > 16 ) OR SP ( S#:'S2', P#:PX ) 

    Исчисление доменов, как и исчисление кортежей, формально эквивалентно 
реляционной алгебре (т.е. оно реляционно полно). Для доказательства можно 
сослаться, например, на статью Ульмана (Ullman) [7.16]. 

    7.7. Резюме 

    В этой главе кратко рассматривалось реляционное исчисление, альтернативное 
реляционной алгебре. Внешне два подхода очень отличаются — исчисление 
описательное, а алгебра предписывающая, но на более низком уровне они 
представляют собой одно и то же, поскольку любые выражения исчисления могут 
быть преобразованы в семантически эквивалентные выражения в алгебре и наоборот. 
    Исчисление существует в двух формах: исчисление кортежей и исчисление 
доменов. Основное различие между ними состоит в том, что переменные исчисления 
кортежей являются переменными кортежей (они изменяются на отношении, а их 
значения являются кортежами), в то время как переменные исчисления доменов 
являются переменными доменов (они изменяются на доменах, а их значения 
являются скалярами; в этом смысле, действительно, "переменная домена" — не 
очень точный термин). 
    Выражение исчисления кортежей содержит заключенный в скобки список целевых 
элементов и выражение WHERE, содержащее формулу WFF ("правильно построенную 
формулу")- Такая формула WFF составляется из кванторов (EXISTS и FORALL), 
свободных и связанных переменных, литералов, операторов сравнения, логических 
(булевых) операторов и скобок. Каждая свободная переменная, которая 
встречается в формуле WFF, должна быть также перечислена в списке целевых элементов. 
    Замечание. Мы неявно затрагивали этот вопрос в главе, но выражения 
исчисления предназначены, по существу, для тех же целей, что и выражения алгебры. 
    На примере было показано, как алгоритм преобразования Кодда может 
использоваться для преобразования произвольного выражения исчисления в 
эквивалентное выражение алгебры, таким образом подготавливая почву для 
возможной стратегии реализации исчисления. Вновь напомнив проблемы реляционной 
полноты, мы кратко рассмотрели, каким образом можно показать, что определенный 
язык L является полным в этом смысле. 

    196	Часть II. Реляционная модель 

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

    Упражнения 

    В одних упражнениях рассматриваются некоторые теоретические аспекты 
исчисления, а в других читателю предлагается сформулировать некоторые запросы 
в виде выражений реляционного исчисления. (В качестве интересного варианта 
этих упражнений читатель может выбрать "обратный" — прочитать сначала ответ и 
определить словесное значение данного выражения, а затем составить выражение 
реляционного исчисления.) 
    7.1. Пусть f(x) и g— произвольные формулы WFF, в которых х в качестве 
свободной переменной используется и не используется соответственно. Какие из 
следующих формулировок верные? (Символ => означает "следует"; символ = 
означает "эквивалентно".) 
    а) EXISTS х ( g ) = g 
    б) FORALL х ( д ) = д 
    B) EXISTS х ( f (х) AND g ) s EXISTS x ( f (x) ) AND g Г) FORALL x ( f (x) 
AND g ) з FORALL x ( f (x) ) AND g Д) FORALL x ( f (x) ) => EXISTS X ( f (x) ) 
    7.2. Пусть f(x,y) — произвольная формула WFF со свободными переменными х и 
у. Какие из следующих формулировок верные? 
    a) EXISTS x EXISTS у ( f(x,y) ) s EXISTS у EXISTS X ( f(x,y) ) 
    6) FORALL x FORALL у ( f (x,y) ) s FORALL у FORALL X ( f (x,y) ) 
    B) FORALL x ( f(x,y) ) = NOT EXISTS x ( NOT f (x,y) ) 
    Г) EXISTS x ( f (x,y) ) = NOT FORALL x ( NOT f(x,y) ) 
    Д) EXISTS x FORALL у ( f (x,y) ) = FORALL у EXISTS x ( f (x,y) ) 
    6) EXISTS у FORALL x ( f (x,y) ) => PORALL X EXISTS у ( f(x,y) ) 
    7.3. Пусть f(x) и g(y) — произвольные формулы WFF со свободными 
переменными х и у соответственно. Какие из следующих формулировок верные? 
    a) EXISTS х ( f(x) ) AND EXISTS у ( g(y) ) = 
    EXISTS x EXISTS у ( f(x) AND g(y) ) 6) EXISTS x ( IF f (x) THEN g(x) ) = 
    IF FORALL x ( f (x) ) THEN EXISTS X ( g(x) ) 
    7.4. Снова рассмотрим запрос, приводимый выше в этой главе: "Получить 
номера поставщиков, поставляющих все детали, поставляемые поставщиком S2". Для 
этого запроса возможна следующая формулировка в терминах исчисления кортежей: 
    SX.Sf WHERE FORALL SPY ( IF SPY.St * 'S2' THEN 
    EXISTS SPZ ( SPZ.Stt = SX.S# AND SPZ.P* = SPY.PS ) ) 

    Глава 7. Реляционные операторы: II. Реляционное исчисление	197 

    Что будет возвращено при выполнении этого запроса, если поставщик S2 не 
поставляет никаких деталей? Что будет, если мы заменим SX на SPX в приведенном выражении? 

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

    (   PX.NAME,   PX.CITY  )   WHERE FORALL SX TORALL JX EXISTS SPJX 
    (  SX.CITY =   'London1   AND OX.CITY =  'Paris'  AND SPJX.S# = SX.S# AND 
SPJX.PJt = PX.P# AND SPJX.J* = OX.J# AND SPJX.QTY < 500  ) 

    а) сформулируйте этот запрос в словесной форме; 
    б) представьте себе, что вы — СУБД, и "выполните" этот запрос по 
предложенному алгоритму. Не можете ли вы указать какие-либо улучшения, которые 
можно внести в этот алгоритм? 

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

    7.7. Рассмотрим отношение спецификации материалов PART_STRUCTURE из главы 
4 (примерные значения приведены на рис. 4.4). Хорошо известный запрос узлов 
детали "Получить номера деталей, которые являются компонентами некоторой 
определенной детали, скажем детали Р1", результат которого, скажем отношение 
PART_LIST (является, конечно, отношением, производным от отношения 
PART_STRUCTURE), нельзя сформулировать в виде одного выражения реляционного 
исчисления (или реляционной алгебры). Иначе говоря, отношение PART_STRUCTURE 
не может быть сформулировано в виде одного выражения реляционного исчисления 
(или реляционной алгебры). Почему? 

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

    7.9. Дайте решения к упр. 6.13-6.48 в терминах исчисления кортежей. 

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

    7.11. Дайте решения к упр. 6.13-6.48 в терминах исчисления доменов. 

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

    7.1. Chang C.L. DEDUCE — A Deductive Query Language for Relational Data 
Bases // C.H. Chen (ed.) Pattern Recognition and Artificial Intelligence. — 
New York: Academic Press, 1976. 
    7.2. Codd E.F. Relational Completeness of Data Base Sublanguages // Data 
Base Systems, Courant Computer Science Symposia Series 6. — Englewood Cliffs, 
N.Y.: Prentice-Hall, 1972. 

    198	Часть II. Реляционная модель 

    В статье вводится понятие реляционной полноты. Она включает первоначальные 
определения реляционного исчисления и реляционной алгебры (т.е. восемь 
операций, описанных в главе 6). В ней также представлен в подробностях 
алгоритм редукции, кратко описанный выше в этой главе, подтверждающий, что с 
помощью алгебры можно, по крайней мере, выразить то же самое, что и с помощью 
исчисления. (Кстати, для версии исчисления, определенной в статье, обратное не 
верно, поскольку эта версия не включает никакого эквивалента алгебраического 
оператора UNION.) Статью завершает краткое изложение аргументов в пользу 
применения исчисления (по сравнению с алгеброй) как основы для практического 
языка базы данных. Речь идет о следующих аргументах. 
    1.  Возможности расширения. Язык, основанный на исчислении, больше чем 
алгебраический подходит для расширения через объединение скалярных 
вычислительных операторов, итоговых функций и т.д. 
    2.  Легкость в выражении запроса пользователя (важно для оптимизации, 
проверки полномочий пользователя и т.п.). Исчисление, позволяющее 
пользователям запрашивать данные по их свойствам вместо последовательности 
операторов обработки, является по сравнению с алгеброй лучшей основой для этих целей. 
    3.  Близость к естественному языку. Кодд признает, что большинство 
пользователей не могут непосредственно использовать ни алгебру, ни исчисление 
как таковые. Но идея получения данных по их свойствам более естественна по 
сравнению с составлением последовательности операций обработки данных. Таким 
образом, исчисление может служить лучшей основой для некоторого более 
дружественного высокоуровневого языка. 
    Однако не ясно, какие из этих аргументов в действительности устоят, 
учитывая, что оба подхода формально эквивалентны. Возможно, третий аргумент 
достоин внимания, потому что и исчисление и алгебра, как синтаксически более 
определенные, гораздо больше подходят по сравнению с SQL для такого целевого 
языка! Примечательно, что многие системы SQL в целях реализации фактически 
внутренне конвертируют SQL в нечто более близкое к алгебре. 
    7.3. Codd E.F. A Data Base Sublanguage Founded on the Relational Calculus 
// Proc. 1971 ACM SIGFIDET Workshop on Data Description, Access and Control.— 
San Diego, Calif., 1971. 
    В статье определяется "Подъязык данных ALPHA". Стоит проработать один 
вопрос, касающийся ALPHA, а именно использование неявных переменных области 
значений. Основная идея заключается в том, чтобы использовать имя отношения 
для обозначения неявной переменной, которая изменятся на данном отношении, 
устраняя всякую неоднозначность результата. Языки QUEL и SQL заимствовали это 
достаточно очевидное сокращение. В языке QUEL, например, мы можем написать просто 

    RETRIEVE   (  S.S#   )   WHERE S.SITY = "London" 

    вместо 

    RANGE OF SX IS S 
    RETRIEVE   (  SX.Stt  )   WHERE SX.SITY =  "London" 

    В первой формулировке не совсем понятно, что, например, "S" в "S.S#" не 
представляет отношение S, а представляет переменную отношения, называемую S, 
которая изменяется на отношении с таким же именем. 
    7.4. Date C.J. A Note on the Relation Calculus // ACM SIGMOD Record. — 
1989. — 18, №4. (Переиздано: An Anomaly in Codd's Reduction Algorithm // C.J. 
Date and Hugh Darwen. Relational Database Writings 1989-1991.— Reading, Mass.: 
Addison Wesley, 1992.) 

    Глава 7. Реляционные операторы: II. Реляционное исчисление	199 

    В статье указываются и объясняются некоторые мелкие упущения в алгоритме 
редукции Кодда [7.2]. 
    7.5. Date C.J. Why Quantifier Order Is Important // C.J. Date and Hugh 
Darwen. Relational Database Writings 1989-1991. — Reading, Mass.: Addison 
Wesley, 1992. 
    7.6. Date C.J. Relational Calculus as an Aid to Effective Query 
Formulation // Ibid. 
    Почти все современные реляционные продукты на рынке поддерживают язык SQL, 
а не реляционное исчисление (или реляционную алгебру). В этой статье, тем не 
менее, отстаивается (и иллюстрируется) применение реляционного исчисления как 
промежуточного шага в построении "сложных" запросов SQL. 
    7.7. Held G.D., Stonebraker M.R., Wong E. INGRES — A Relational Data Base 
System // Proc. NCC 44. — Anaheim, Calif.; Montvale, N.J.: AFIPS Press, 1975. 
    В середине и до конца 70-х годов разрабатывались два главных реляционных 
прототипа: система R в фирме IBM и система INGRES в Калифорнийском 
университете в Беркли. Оба этих проекта стали очень важными в 
исследовательском мире и впоследствии лидировали среди коммерческих систем как 
СУБД DB2 (в случае системы R) и как коммерческий продукт INGRES (в случае 
системы INGRES). 
    Замечание. Прототип INGRES иногда называют "университетским INGRES", чтобы 
отличать его от коммерческой версии этой системы. 
    Система INGRES не была вначале SQL-системой, а поддерживала язык QUEL 
("Query Language"), который во многих отношениях технически превосходил SQL. В 
самом деле, язык QUEL по-прежнему составляет основу достаточного числа 
современных исследований баз данных, а примеры на языке QUEL до сих пор 
появляются в исследовательской литературе. Данная статья, впервые описавшая 
прототип INGRES, включает предварительное определение языка QUEL. 
    См. также [7.12-7.14]. 
    7.8. Kuhns J.L. Answering Questions by Computer:  A Logical  Study // 
Report RM-5428-PR. — Santa Monica, Calif.: Rand Corp., 1967. 
    7.9. Lacrorix M., Pirotte A. Domain-Oriented Relational Languages // Proc. 
3rd Intern. Conf. on Very Large Data Bases. — 1977. 
    7.10. Lacrorix M., Pirotte A. ILL: An English Structured Query Language 
for Relational Data Bases // G.M. Nijssen (ed.). Architecture and Models in 
Data Base Management Systems. — Amsterdam, Netherlands: North-Holland; New 
York, N.Y.: Elsevier Science, 1977. 
    7.11. Pirotte, Wodon P. A Comprehensive Formal Query Language for 
Relational Data Base // R.A.I.R.O. Informatique/Computer Science. — 1977. — 
11, № 2. 
    "Формальный язык запросов" (formal query language — FQL) построен (как и 
язык ILL) на основе исчисления доменов, но в отличие от языка ILL он более 
формализован (т.е. он меньше похож на обычный разговорный язык). 
    7.12. Stonebraker M. (ed.). The INGRES Papers: The Anatomy of a Relational 
Database Management System. — Reading, Mass.: Addison-Wesley, 1986. 
    Собрание некоторых наиболее важных документов университетского проекта 
INGRES под редакцией одного из первых создателей этого проекта. (В это 
собрание включены статьи [7.13, 7.14].) Насколько известно автору настоящей 
книги, это единственное доступное издание, подробно описывающее проект и 
реализацию полномасштабной реляционной СУБД. Весьма ценный материал для 
серьезных студентов. 

    200	Часть II. Реляционная модель 

    7.13. Stonebraker M., Wong E., Kreps P., Held G. The Design Implementation 
of INGRES // ACM TODS. — 1976. — 1, № 3. (Переиздание [7.12].) 
    Подробное описание прототипа INGRES. 
    7.14. Stonebraker M. Retrospection on a Data Base System // Ibid. — 1980. 
— 5, № 2. (Переиздание [7.12].) 
    Доклад по истории проекта прототипа INGRES (до января 1979г.). Акцент 
сделан скорее на ошибках и полученных уроках, чем на успехах. 
    7.15. Zloof М.М. Query By Example // Proc. NCC 44. — Anaheim, Calif. 
Montvale, N.J.: AFIPS Press, 1975. 
    Реляционный язык Query-By-Example (QBE), включающий элементы и исчисления 
кортежей и особенно исчисления доменов. Привлекательный и интуитивно простой 
синтаксис языка основывается на идее формирования элементов в "скелетные 
таблицы" на экране вместо записи линейных операторов. Например, формулировка 
QBE для запроса "Получить имена поставщиков, которые поставляют по крайней 
мере одну деталь, поставляемую поставщиком S2" (довольно сложный запрос) может 
выглядеть так: 
    S          S#                SNAME                       SP	S#	P# 
    SX             P.   NX	SX	_PX 
    SP	s#	Р# 
    S2	РХ 
    Пояснение. Пользователь обращается к системе с запросом отобразить три 
скелетные таблицы на экране, одну для отношения S и две для отношения SP, и 
сформировать в них элементы, как это показано выше. Элементы, начинающиеся 
подчеркиванием, представляют "образцы" (т.е. переменные доменов); другие 
элементы представляют литералы. Затем пользователь обращается с запросом 
"предоставить" ("Р") значения имен поставщиков (_NX) таких, что если это 
поставщик _SX, то _SX поставляет некоторую деталь _РХ, а деталь _РХ, в свою 
очередь, также поставляется поставщиком S2. Заметьте, что под кванторами 
существования подразумевается (как, кстати, и под кванторами существования в 
QUEL) совсем другой смысл, поэтому синтаксис — интуитивно легкий для понимания. 
    Вот другой пример: "Получить пары номеров таких поставщиков, которые 
размещаются в одном и том же городе". 
    S	s#	CITY 
    SX	CZ                            P.              SX              SY 
    _SY	_CZ 
    К сожалению, язык QBE не является реляционно полным, а конкретнее, не 
поддерживает (в полной мере) негативный квантор существования (NOT EXISTS). 
Вследствие этого определенные запросы (например, "Получить имена поставщиков, 
которые поставляют все детали") не могут быть выражены в языке QBE. 
    (На самом деле язык QBE вначале "поддерживал" квантор NOT EXISTS, no 
крайней мере неявно, но построение всегда было сопряжено с некоторыми 
трудностями. Основная проблема заключалась в том, что не было способа указать 
порядок, в котором различные неявные кванторы могли бы быть применены, а 
порядок, к сожалению, очень важен — см. [7.5]. Поэтому определенные запросы 
были неоднозначными [7.5].) 
    Злуф (автор этой работы) первым изобрел и разработал язык QBE. Данная 
статья была первой из многих, написанных Злуфом по этой теме. 
    7.16. Ullman J.D. Principles of Database and Knowledge-Base Systems: 
Volume I. — Rockville, Md.: Computer Science Press, 1988. 

    Глава 7. Реляционные операторы: II. Реляционное исчисление 201 

    Книга Ульмана, в отличие от настоящей книги, содержит более формальное 
изложение реляционного исчисления и связанных с ним вопросов. В частности, в 
ней обсуждается понятие безопасности выражений исчисления. Это имеет значение 
при адаптации немного измененной версии исчисления, в которой переменные 
области значений не определяются отдельными операторами RANGE, а связываются с 
областью значений посредством явных условий в фразе WHERE. В такой версии 
исчисления запрос "Получить всех поставщиков из Лондона", например, может 
выглядеть как 

    SX WHERE SX e S AND SX.CITY =  'London1 

    вместо 

    RANGE OF SX IS S  ; 
    SX WHERE SX.CITY =   'London1 

    Одна из проблем, возникающих при использовании этой версии исчисления 
заключается в том, что в ней недопустимы запросы, такие как 

    SX WHERE NOT   (  SX e  S  ) 

    Подобные выражения называются "небезопасными", так как они не возвращают 
конечный результат (множество всего, что не входит в отношение S, бесконечно). 
Поэтому необходимо ввести некоторые правила, обеспечивающие безопасность в 
этом смысле. В книге Ульмана описаны такие правила (как для исчисления 
кортежей, так и для исчисления доменов). 
    Ответы к некоторым упражнениям 
    7.1. а) верно; б) верно; в) верно; г) верно; д) не верно. 
    Замечание: Причина, по которой (д) не верно, состоит в том, что применение 
квантора FORALL к пустому множеству всегда дает истину. И наоборот, применение 
квантора EXISTS к пустому множеству дает ложь. Поэтому, например, если 
утверждение "Все фиолетовые детали весят более 100 фунтов" истинно, то это не 
обязательно означает, что действительно существуют фиолетовые детали. 
    Заметим, что (верные!) тождества могут быть использованы как основа для 
множества правил преобразования выражений исчисления, точно так же как и 
алгебраические правила преобразования, упоминавшиеся в главе 6 (и подробно 
обсуждаемые далее в этой книге). Аналогичные замечания также применимы и к 
упр. 7.2 и 7.3. 
    7.2. а) верно; б) верно; в) верно (этот пример рассматривался в главе); г) 
верно (следовательно, каждый квантор может быть определен через другой); д) не 
верно; е) верно. Обратите внимание, что последовательность одинаковых 
кванторов — как в (а) и (б) — может быть записана в любом порядке без 
изменения смысла выражения, тогда как для разных кванторов — как показано в 
примере (д) — такой порядок имеет существенное значение. Чтобы 
проиллюстрировать последнее, предположим, что х и у изменяются на множестве 
целых чисел и/является формулой WFF "у > х". Очевидно, что формула 

    FORALL X EXISTS у  ( у > х ) 

    ("для всех целых х существует целое у, большее х") дает истину, в то время 
как формула 

    EXISTS у FORALL х  (у > х ) 

    ("существует целое у, большее чем любое целое дг") дает ложь. Таким 
образом, перестановка неодинаковых кванторов изменяет значение выражения. 
Поэтому в языке запросов, основанном на исчислении, перестановка неодинаковых 
кванторов в фразе WHERE изменяет значение запроса [7.5]. 

    202	Часть II. Реляционная модель 

    7.3. а) верно; б) верно. 
    7.4. Если поставщик S2 в данный момент не поставляет деталей, начальный 
запрос будет возвращать все номера поставщиков в отношении S (включая, в 
частности, самого поставщика S2, который согласно нашему предположению 
содержится в отношении S и не содержится в отношении SP). Если везде заменить 
SX на SPX, то запрос будет возвращать все номера поставщиков, содержащихся в 
отношении SP. Различие между двумя формулировками следующее: первая означает 
"Получить номера поставщиков, которые поставляют по крайней мере все детали, 
поставляемые поставщиком S2" (как требуется), а вторая означает "Получить 
номера поставщиков, поставляющих по крайней мере одну деталь и поставляющих по 
крайней мере все такие детали, которые поставляются поставщиком S2." 
    7.5. а) получить наименование детали и город для деталей, поставляемых для 
каждого проекта в Париже каждым поставщиком в Лондоне в количестве менее 500 
штук; б) результат этого запроса — пустое множество. 
    7.6. Это упражнение очень трудное! Особенно, если мы будем учитывать, что 
вес деталей неуникален. (Если бы их вес был уникален, мы могли бы 
переформулировать запрос как "Получить все детали такие, что количество более 
тяжелых деталей меньше трех.") Упражнение такое трудное, что мы не пытаемся 
дать здесь полное решение на языке исчисления. Оно очень хорошо иллюстрирует 
тот факт, что реляционная полнота является лишь основным критерием 
выразительной силы языка, но не обязательно достаточным. (Следующие два 
примера также иллюстрируют этот момент). 
    Сравнительно мало систем может справиться с проблемой, которую 
иллюстрирует это упражнение, несмотря на то что такие задачи весьма 
распространены на практике. Мы будем называть такие задачи долевыми запросами. 
Любопытно, что язык Кодда ALPHA [7.3] включает возможности для долевых 
запросов, но (как уже отмечалось) этот язык никогда не был реализован. На 
языке ALPHA пример может иметь такой вид: 

    (3) ( РХ.Р#, PX.PNAME, PX.COLOR, PX.WEIGHT, PX.CITY } DOWN PX.WEIGHT 

    Начальное " (3)" — это квота (означает первые три); "DOWN PX.WEIGHT" 
означает: "Для достижения квоты последовательность кортежей отношения деталей 
концептуально рассматривается по убыванию значения WEIGHT". 
    Продукт Rdb/VMS компании DEC — один из примеров коммерческой системы, 
которая поддерживает долевые запросы. 
    7.7. Пусть PSA, PSB, PSC, ..., PSw— переменные кортежей для отношения 
PART_STRUCTURE; предположим также, что данная деталь — это деталь Р1. Тогда: 
    а) выражение исчисления для запроса "Получить номера деталей для всех 
деталей, которые являются компонентами детали Р1 (на первом уровне)" будет таким: 
    PSA.MINOR_P# WHERE PSA.MAJOR_P# = 'PI' 
    б) выражение исчисления для запроса "Получить номера деталей для всех 
деталей, которые являются компонентами детали Р1 (на втором уровне)" будет таким: 
    PSB.MINOR_P# WHERE EXISTS PSA 
    ( PSA.MAJOR_P# = 'PI' AND 
    PSB.MAJOR_P# = PSA.MINOR_P# ) 

    Глава 7. Реляционные операторы: II. Реляционное исчисление	203 

    в) выражение исчисления для запроса "Получить номера деталей для всех 
деталей, которые являются компонентами детали Р1 (на третьем уровне)" будет таким: 
    PSC.MINOR_P# WHERE EXISTS PSA EXISTS PSB 
    ( PSA.MAJOR_P# = 'PI1 AND ( PSB.MAJOR_P# = PSA.MINOR_P# AND PSC.MAJOR_P# = 
PSB.MINOR_P# ) 
    И т.д. Выражение исчисления для запроса "Получить номера деталей для всех 
деталей, которые являются компонентами детали Р1 (на и-м уровне)" будет таким: 
    PSn.MINOR_P# WHERE EXISTS PSA EXISTS PSB ... EXISTS PS(n-l) ( PSA.MAJOR_P# 
= 'PI' AND ( PSB.MAJOR_P# = PSA.MINOR_P# AND PSC.MAJOR_P# = PSB.MINOR_P# AND 
........................... AND 
    PSn.MAJOR_P# = PS(n-l) .MINOR_P# ) 
    Все результирующие отношения (а, б, в,...) затем необходимо объединить 
вместе для построения отношения PART_LIST. 
    Проблема заключается в том, что невозможно записать и таких выражений, 
если значение п не известно. Таким образом, запрос узлов детали является 
классической иллюстрацией задачи, которая не может быть сформулирована только 
с помощью отдельных выражений на языке, обладающем только свойством 
реляционной полноты, т.е. языке, который не является более мощным, чем 
исчисление (или алгебра). 
    Замечание. Хотя эту задачу обычно называют "спецификациями материалов" или 
"определением узлов деталей", ее применимость на самом деле значительно шире, 
чем можно судить по этим названиям. В действительности класс отношений вида 
"детали содержат детали" очень широко распространен в самых разных 
приложениях. Кроме прочего, такой вид отношений используется в управлении 
иерархическими структурами, фамильными деревьями, сетями связи, структурами 
программного вызова модулей, транспортными сетями и т.д. 
    7.8. Этот запрос нельзя выразить ни в терминах исчисления, ни в терминах 
алгебры. Например, чтобы выразить его в терминах исчисления, нам, по существу, 
необходимо было бы уметь выражать нечто подобное следующему: 
    Существует ли отношение R такое, что существует кортеж Т в отношении R 
такой, что 7.S# = 'Sr? 
    Другими словами, мы должны были бы уметь определять количество на 
отношениях, а не кортежах, и нам, следовательно, потребовалась бы переменная 
области значений нового типа, такая, значениями которой являются некоторые 
(именованные) отношения. Поэтому такой запрос не может быть выражен в 
реляционном исчислении, поскольку реляционное исчисление поддерживает лишь 
переменные, значениями которых являются кортежи (а значит, позволяют 
определять количество на кортежах, а не на отношениях). 
    Заметьте, кстати, что рассматриваемый запрос — это запрос типа "да-нет" 
(желаемый ответ— в основном истинное значение). Поэтому читателю может 
показаться, что запрос нельзя выразить в терминах исчисления или с помощью 
алгебры, потому что выражения исчисления и алгебры принимают значения 
отношений, а не истинностные. Однако запросы типа "да-нет" могут быть выражены 
в терминах исчисления и алгебры, если они правильно 

    204	Часть II. Реляционная модель 

    реализованы! Главная трудность заключается в том, чтобы понять, что "да" и 
"нет" (эквиваленты истины и лжи) могут представляться как отношения. 
Рассматриваемые отношения — это TABLE_DEE и TABLE_DUM соответственно. Более 
подробное обсуждение этих отношений приводилось в главе 4. 
    7.9. Мы перенумеровали решения как 7.9.и, где п — номер исходного 
упражнения в главе 6, т.е. упр. б.п. Мы подразумеваем, что SX, SY, PX, PY, JX, 
JY, SPJX, SPJY (и т.д.) — кортежи переменных, изменяющихся на отношениях S, P, 
J, SPJ соответственно; определение этих переменных области значений не показано. 
    7.9.13. ох 
    7.9.14. OX WHERE JX.CITY = 'London1 
    7.9.15. SPJX.Stt WHERE SPJX.Jtt = 'Л' 
    7.9.16. SPJX WHERE SPJX.QTY > 300 AND SPJX.QTY < 750 
    7.9.17. ( PX.COLOR, PX.CITY ) 
    7.9.18. ( SX.Stt, PX.P#, JX.J# ) WHERE SX.CITY = PX.CITY 
    AND  PX.CITY = JX.CITY AND  JX.CITY = SX.CITY 
    7.9.19. ( SX.Stt, PX.Ptt, JX.J# ) WHERE SX.CITY Ф PX.CITY 
    OR   PX.CITY Ф JX.CITY OR   JX.CITY Ф SX.CITY 
    7.9.20. ( SX.Stt, PX.Ptt, JX.Jtt ) WHERE SX.CITY Ф PX.CITY 
    AND  PX.CITY Ф JX.CITY AND  JX.CITY Ф SX.CITY 
    7.9.21. SPJX.P# WHERE EXISTS SX ( SX.Stt = SPJX.Stt AND 
    SX.CITY = 'London' ) 
    7.9.22. SPJX.Ptt WHERE EXISTS SX EXISTS JX 
    ( SX.Stt = SPJX.Stt AND SX.CITY = 'London1 AND JX.J# = SPJX.J# AND JX.CITY 
= 'London' ) 
    7.9.23. ( SX.CITY AS SCITY, JX.CITY AS JCITY ) 
    WHERE EXISTS SPJX ( SPJX.Stt = SX.Stt AND SPJX.Jtt = JX.Jtt ) 
    7.9.24. SPJX.Ptt WHERE EXISTS SX EXISTS JX 
    ( SX.CITY = JX.CITY AND SPJX.Stt = SX.Stt AND SPJX.J* = JX.Jtt ) 
    7.9.25. SPJX.Ptt WHERE EXISTS SX EXISTS JX 
    ( SX.CITY Ф JX.CITY AND SPJX.Stt = SX.S# AND SPJX.Jtt = JX.Jtt ) 
    7.9.26. ( SPJX.Ptt AS XPtt, SPJY.Ptt AS YPtt ) 
    WHERE SPJX.Stt = SPJY.S* AND SPJX.Ptt < SPJY.Ptt 
    7.9.27. COUNT ( SPJX.Jtt WHERE SPJX.S# = 'si' ) AS N 
    7.9.28. SUM ( SPJX WHERE 
    SPJX.Stt = 'SI1 AND SPJX.Ptt = 'PI1, OTY ) AS Q 
    Следующее "решение" не верно (почему?): 
    SUM ( SPJX.OT.Y WHERE 

    Глава 7. Реляционные операторы: II. Реляционное исчисление	205 

    SPJX.S* =   'SI1  AND SPJX.P# =   'PI1,   QTY )   AS Q 
    (Ответ. Так как повторяющиеся значения QTY будут игнорироваться при 
вычислении суммы.) 
    7.9.29. ( SPJX.P*, SPJX.J#, 
    SUM ( SPJY ЩЕКЕ SPJY.P# = SPJX.P* 
    AND     SPJY.J# = SPJX.J*, QTY ) AS Q ) 
    7.9.30. SPJX.P* 
    WHERE AVG ( SPJY WHERE SPJY.P# = SPJX.PS 
    AND     SPJY.J# = SPJX.JS, QTY ) > 320 
    7.9.31. JX.JNAME WHERE EXISTS SPJX ( SPJX.J* = JX.J# АЮ 
    SPJX.S# = 'SI1 ) 
    7.9.32. PX.COLOR WHERE EXISTS SPJX ( SPJX.P* = PX.P# AND 
    SPJX.S# = 'SI' ) 
    7.9.33. SPJX.P* WHERE EXISTS JX { JX.CITY = 'London' AND 
    JX.J# = SPJX.J# ) 
    7.9.34. SPJX.J* WHERE EXISTS SPJY ( SPJX.P* = SPJY.P# AND 
    SPJY.S* = 'SI' ) 
    7.9.35. SPJX.Sft WHERE EXISTS SPJY EXISTS SPJZ EXISTS PX ( SPJX.Ptt = 
SPJY.P# AND SPJY.S* = SPJZ.SS AND SPJZ.P# = PX.P# AND PX.COLOR = 'Red' ) 
    7.9.36. SX.S# WHERE EXISTS SY ( SY.S# = 'SI' AND 
    SX.STATUS < SY.STATUS ) 
    7.9.37. JX.J# WHERE TORALL JY   (  JY.CITY > JX.CITY  ) ИЛИ JX.J# WHERE 
JX.CITY = MIN   (  JY.CITY  ) 
    7.9.38. SPJX.J# WHERE SPJX.P# =   'PI'  AND 
    AVG   (  SPJY WHERE SPJY.Pft =   'PI' 
    AND      SPJY.J# = SPJX.J*,   QTY  )   > MAX   (  SPJZ.QTY WHERE SPJZ.J# = 
  'Jl'   ) 
    7.9.39. SPJX.S# WHERE SPJX.P# = 'PI' AND  SPJX.QTY > AVG ( SPJY 
    WHERE SPJY.P# = 'PI' 
    AND  SPJY.J# = SPJX.Jtt, QTY ) 
    7.9.40. JX.J# WHERE NOT EXISTS SPJX EXISTS SX EXISTS PX ( SX.CITY = 
'London' AND PX.COLOR = 'Red' AND SPJX.S* = SX.SS AND SPJX.P# = PX.P# AND 
SPJX.J* = JX.J# ) 
    7.9.41. JX.J# WHERE FDRALL SPJY ( IF SPJY.JS = JX.J# 
    THEN SPJY.Stf = 'SI' ) 

    206	Часть II. Реляционная модель 

    7.9.42. PX.P# WHERE FORALL JX 
    ( IF JX.CITY = 'London1 THEN EXISTS SPJY ( SPJY.P* = PX.PS AND SPJY.J# = 
JX.J# ) ) 
    7.9.43. SX.S# WHERE EXISTS PX FORALL OX EXISTS SPJY ( SPJY.Stt = SX.S# AND 
SPJY.P# = PX.P# AND SPJY.J* = JX.J# ) 
    7.9.44. JX.Jt WHERE FORALL SPJY ( IF SPJY.S* = 'SI' THEN 
    EXISTS SPJZ ( SPJZ.J# = JX.J# AND SPJZ.P# = SPJY.P# ) ) 
    7.9.45. RANGE OF VX IS ( SX.CITY ), ( PX.CITY ), ( JX.CITY ) ; VX.CITY 
    7.9.46. SPJX.P# WHERE EXISTS SX ( SX.S# = SPJX.S* AND 
    SX.CITY = 'London' ) 
    OR        EXISTS JX   (   JX.J# = SPJX.Jtt AND JX.CITY =  'London'   ) 
    7.9.47.   (  SX.Sft,   PX.P#   )   WHERE NOT EXISTS SPJX 
    (  SPJX.S# = SX.Stt AND SPJX.Ptf = PX.P#  ) 
    7.9.48. ( sx.s# AS xs#, SY.S# AS YS# ) WHERE FORALL PZ 
    ( ( IF  EXISTS SPJX ( SPJX.S* = SX.S# AND SPJX.Ptt = PZ.P# ) 
    THEN EXISTS SPJY ( SPJY.Stt = SY.S# AND SPJY.P* = PZ.Ptt ) ) AND 
    (   IF  EXISTS SPJY ( SPJY.S* = SY.S# AND SPJY.P# = PZ.P# ) 
    THEN EXISTS SPJX ( SPJX.Stf = SX.S# AND SPJX.P* = PZ.P# ) ) ) 
    7.10. Оставляем для читателя. 
    7.11. Мы перенумеровали решения как 7.11.и, где п— номер исходного 
упражнения в главе 6, т.е. упр. 6.п. Относительно определений и наименований 
переменных доменов мы следуем соглашениям, принятым выше в этой главе. 
    7.11.13. ( JX, NAMEX, CITYX ) 
    WHERE J ( J#:JX, JNAMEiNAMEX, CITY:CITYX ) 
    7.11.14. ( JX, NAMEX, 'London' AS CITY ) 
    WHERE J ( J#:JX, JNAMEiNAMEX, CITY:'London' ) 
    7.11.15. SX WHERE SPJ ( S#:SX, J#:'J1' ) 
    7.11.16. ( SX, PX, JX, QTYX ) 
    WHERE SPJ ( S#:SX, P#:PX, J#:JX, OTY:OTYX ) AND  OTYX > 300 AND OTYX < 750 
    7.11.17. ( COLORX, CITYX ) WHERE P ( COLOR:COLORX, CITY:CITYX ) 
    7.11.18. ( SX, PX, JX ) WHERE EXISTS CITYX 
    ( S ( S#:SX, CITY:CITYX ) AND P ( P#:PX, CITY:CITYX ) AND J ( J#:JX, 
CITY:CITYX ) ) 

    Глава 7. Реляционные операторы: II. Реляционное исчисление	207 

    7.11.19. ( SX, PX, JX ) WHERE EXISTS CITYX EXISTS CITYY EXISTS CITYZ ( S ( 
S#:SX, CITY:CITYX ) AND P ( P#:PX, CITY:CITYY ) AND J ( J#:JX, CITY:CITYZ ) 
AND ( CITYX # CITYY OR CITYY * CITYZ OR CITYZ Ф CITYX ) ) 
    7.11.20. ( SX, PX, JX ) WHERE EXISTS CITYX EXISTS CITYY EXISTS CITYZ { S ( 
S#:SX, CITY:CITYX ) AND P ( P#:PX, CITY:CITYY ) AND J ( J#:JX, CITY:CITYZ ) 
AND ( CITYX * CITYY AND CITYY Ф CITYZ AND CITYZ * CITYX ) ) 
    7.11.21. PX WHERE EXISTS SX ( SPJ ( P#:PX, S#:SX ) AND 
    S ( S#:SX, CITY:'London' ) ) 
    7.11.22. PX WHERE EXISTS SX EXISTS JX 
    ( SPJ ( S#:SX, P#:PX, J#:JX ) AND S ( S#:SX, CITY:'London' ) AND J ( 
J#:JX, CITY:'London' ) 
    7.11.23. ( CITYX AS SCITY, CITYY AS JCITY ) WHERE EXISTS SX EXISTS JY 
    ( S ( S#:SX, CITY:CITYX ) AND J ( J#:JY, CITY:CITYY ) AND SPJ { S#:SX, 
J#:JY ) ) 
    7.11.24. PX WHERE EXISTS SX EXISTS JX EXISTS CITYX ( S ( S#:SX, CITY:CITYX 
) AND J ( J#:JY, CITY:CITYX ) AND SPJ ( S#:SX, P#:PX, J#:JX ) ) 
    7.11.25. JY WHERE EXISTS SX EXISTS CITYX EXISTS CITYY ( SPJ ( S#:SX, J#:JY 
) AND S ( S#:SX, CITY:CITYX ) AND J ( J#:JY, CITY:CITYY ) AND CITYX * CITYY ) 
    7.11.26. ( PX AS XP#, PY AS YP# ) WHERE EXISTS SX 
    ( SPJ ( S#:SX, P#:PX ) AND SPJ ( S#:SX, P#:PY } AND PX < PY ) 
    7.11.27-30. Решения опущены. 
    7.11.31. NAMEX WHERE EXISTS JX 
    ( J ( J#:JX, JNAME:NAMEX ) AND SPJ ( S#:'S1', J#:JX ) ) 
    7.11.32. COLORX WHERE EXISTS PX 

    208	Часть II. Реляционная модель 

    (  Р   (  Р#:РХ,   СОШК:СОШКХ  )  AND SPJ  (  S#:'SI1,   P#:PX )   } 
    7.11.33. РХ WHERE EXISTS OX 
    ( SPJ ( P#:PX, J#:JX ) AND J ( J|:JX, CITY:'London' ) } 
    7.11.34. JX WHERE EXISTS PX 
    ( SPJ ( P#:PX, J#:JX ) AND SPJ { Pl:PX, S#:'SI' ) ) 
    7.11.35. SX WHERE EXISTS PX EXISTS SY EXISTS PY ( SPJ ( S#:SX, P#:PX ) AND 
SPJ ( P#:PX, S#:SY ) AND SPJ ( S#:SY, P#:PY ) AND P ( P#:PY, COLOR:'Red' ) ) 
    7.11.36. SX WHERE EXISTS STATUSX EXISTS STATUSY 
    ( S ( S#:SX, STATUS:STATUSX ) AND S ( S#:'S1', STATUS: STATUSY ) AND 
STATUSX < STATUSY ) 
    7.11.37. JX WHERE EXISTS CITYX 
    ( J ( J#:JX, CITY:CITYX ) AND FORALL CITYY ( IF J ( CITY:CITYY ) 
    THEN CITYY > CITYX ) ) 
    7.11.38-39. Решения опущены. 
    7.11.40. JX WHERE J ( J#:JX ) AND 
    NOT EXISTS SX EXISTS PX 
    ( SPJ ( S#:SX, P#:PX, J#:JX ) AND S ( S#:SX, CITY:'London' ) AND P ( 
P#:PX, COLOR:'Red' ) ) 
    7.11.41. JX WHERE J ( J#:JX ) 
    AND  FORALL SX ( IF SPJ ( S#:SX, J#:JX ) THEN SX = 'SI' ) 
    7.11.42. PX WHERE P ( P#:PX ) 
    AND  FORALL JX ( IF J ( J#:JX, CITY:'London' ) THEN SPJ ( P#:PX, J#:JX ) ) 
    7.11.43. SX WHERE S ( S#:SX ) 
    AND  EXISTS PX FORALL JX 
    ( SPJ ( S#:SX, P#:PX, J#:JX ) ) 
    7.11.44. JX WHERE J ( J#:JX ) 
    AND  FORALL PX ( IF SPJ ( S#:'SI', P#:PX ) 
    THEN SPJ ( P#:PX, J#:JX ) ) 
    7.11.45. CITYX WHERE EXISTS S ( CITY:CITYX ) OR P ( CITY:CITYX } OR J ( 
CITY:CITYX ) 
    7.11.46. PX WHERE EXISTS SX ( SPJ ( S#:SX, P#:PX ) AND 

    Глава 7. Реляционные операторы: II. Реляционное исчисление	209 

    S ( S#:SX, CITY:'London' ) ) OR   EXISTS JX ( SPJ ( J#:JX, P#:PX } AND 
    J ( J#:JX, CITY:'London' ) ) 
    7.11.47. ( SX, PX ) WHERE S ( S#:SX ) AND P ( P#:PX ) AND  NOT SPJ ( 
S#:SX, P#:PX ) 
    7.11.48. ( SX AS XS#, SY AS YS# } WHERE S ( S#:SX ) AND S ( S#:SY ) AND 
FORALL PZ 
    ( ( IF SPJ ( S#:SX, P#:PZ ) THEN SPJ ( S#:SY, P#:PZ ) ) AND ( IF SPJ ( 
S#:SY, P#:PZ ) THEN SPJ ( S#:SX, P#:PZ ) ) ) 

    210 Часть II. Реляционная модель 

