    Глава б 

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

    I. Реляционная алгебра 

    6.1. Введение 
    Третья и последняя часть реляционной модели — операторы — существенно 
эволюционировала со времени первой публикации статьи Кодда [6.1]. Однако как и 
раньше основным компонентом этой части модели является так называемая 
реляционная алгебра, которая в основном состоит из набора операторов, 
использующих отношения в качестве операндов и возвращающих отношения в 
качестве результата. В главе 3 кратко обсуждались операторы выборки, проекции 
и соединения; эти и некоторые другие операторы рассматриваются в этой главе 
более подробно. 
    В [6.2] Кодд определяет так называемую "начальную" алгебру, т.е. набор из 
восьми операторов, показанный символически на рис. 6.1. Определяя именно эти 
восемь операторов, Кодд преследовал особую цель, о которой пойдет речь в 
следующей главе. Однако важно понимать, что на этих операторах не 
заканчивается история; на самом деле можно было бы определить любое число 
операторов, которые бы удовлетворяли простому необходимому условию: "отношение 
на входе, отношение на выходе" (множество таких операторов действительно 
предлагалось разными авторами; см., например, [6.9-6.11]). В этой главе 
сначала рассматриваются операторы Кодда (или, по крайней мере, его версия 
операторов), а затем они используются в качестве основы для обсуждения 
различных алгебраических идей; в продолжение этой темы обсуждаются способы, с 
помощью которых данный первоначальный набор операторов можно расширить. 

    Обзор начальной алгебры 

    Как утверждалось выше, реляционная алгебра, определенная Коддом в [6.2], 
состоит из восьми операторов, составляющих две группы, по четыре оператора в 
каждой
    1.  Традиционные операции над множествами: объединение, пересечение, 
вычитание и декартово произведение (все они модифицированы с учетом того, что 
их операндами являются отношения, а не произвольные множества). 
    2.  Специальные реляционные операции: выборка, проекция, соединение и 
деление. Ниже приведены упрощенные определения этих восьми операторов (см. 
рис. 6.1). 
    Выборка: 
    возвращает отношение, содержащее все кортежи из определенного отношения, 
которые удовлетворяют определенным условиям. Операция выборки также называется 
операцией ограничения1, поэтому далее в этой книге будет также употребляться 
термин ограничение, если подразумевается алгебраическая операция. 
    Проекция: 
    возвращает отношение, содержащее все кортежи (называемые как подкортежи) 
определенного отношения после исключения из него некоторых атрибутов. 
    1 Изначально эта операция называлась restrict (дословно — ограничение), но 
теперь ее чаще называют select (выборка). Однако это последнее название не 
совсем удачное, поскольку его легко перепутать с оператором SELECT в SQL, а 
это далеко не то же самое. На самом деле оператор SELECT в SQL гораздо мощнее 
алгебраической операции restrict — он в основном включает функциональные 
возможности всех первоначальных восьми алгебраических операций и еще кое-что. 

    Глава 6. Реляционные операторы: I. Реляционная алгебра 135 

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

    Выборка 
    Проекция 
    ^-^Произведение  -ч 
    С   7      i 
    Объединение 
    Пересечение 
    JT Соединение (естественное) -. 
    Вычитание 
    г Деление 
    -^.Деление —_ 
    а	X 
    а	У 
    а	Z 
    Ь	X 
    с	У 

    Рис. 6.1. Первоначальные восемь операторов (обзор) 

    Объединение: 
    возвращает отношение, содержащее все кортежи, которые принадлежат или 
одному из двух определенных отношений, или обоим. 

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

    Пересечение: 
    возвращает отношение, содержащее все кортежи, которые принадлежат 
одновременно двум определенным отношениям. 
    Вычитание: 
    возвращает отношение, содержащее все кортежи, которые принадлежат первому 
из двух определенных отношений и не принадлежат второму. 
    Соединение: 
    возвращает отношение, кортежи которого — это сочетания двух кортежей 
(принадлежащих соответственно двум определенным отношениям), имеющих общее 
значение для одного или нескольких общих атрибутов этих двух отношений (и 
такие общие значения в результирующем кортеже появляются только один раз, а не дважды). 
    Замечание. Строго говоря, это естественное соединение. (О различных видах 
соединений речь идет ниже в этой главе.) 
    Деление: 
    для двух отношений, бинарного и унарного, возвращает отношение, содержащее 
все значения одного атрибута бинарного отношения, которые соответствуют (в 
другом атрибуте) всем значениям в унарном отношении. 
    На этом закончим краткий обзор первоначальных операторов. План остальной 
части главы такой: в следующем вводном разделе повторно и более подробно 
рассматривается вопрос замкнутости. Затем в деталях обсуждается восемь 
первоначальных операторов, предложенных Коддом и даются некоторые примеры 
использования этих операторов для формулирования запросов. Далее обсуждается 
вопрос "зачем нужна алгебра" и описываются два немаловажных оператора, 
называемых EXTEND и SUMMARIZE. Затем рассматриваются операции присвоения, 
обновления и реляционное сравнение. И наконец, дается краткое заключение. 

    6.2. Замкнутость 

    Уже не раз отмечалось, что результат каждой операции над отношением (или 
реляционной операции) также является отношением. Это реляционное свойство 
называется свойством замкнутости и впервые упоминается в главе 3. Там же 
делается вывод: поскольку результат любой операции имеет тот же тип, что и 
исходные объекты (отношения), то результат одной операции может использоваться 
в качестве исходных данных для другой. Таким образом, имеется возможность, 
например, взять или проекцию от объединения, или соединение от двух выборок, 
или объединение соединения и пересечения и т.д. 
    Другими словами, можно записывать вложенные выражения, т.е. выражения, в 
которых операнды сами представлены выражениями вместо простых имен отношений. 
В этой главе приводится много примеров таких вложенных выражений (фактически 
они будут встречаться на протяжении всей книги). 
    Замечание. Есть явная аналогия между возможностями использования вложенных 
реляционных выражений в реляционной алгебре и вложенных арифметических 
выражений в обычной арифметике. Действительно, тот факт, что отношения 
замкнуты, важен в алгебре по тем же причинам, по которым в обычной арифметике 
важно, что числа замкнуты. 
    При обсуждении свойства замкнутости в главе 3 сознательно умалчивался один 
существенный момент. Как уже разъяснялось в главе 4, отношение имеет две части 
— заголовок и тело; нестрого говоря, заголовок — это множество атрибутов, а 
тело — это данные. Заголовок для базового отношения, очевидно, вполне 
конкретен и известен системе, поскольку он определяется как часть 
соответствующего оператора CREATE BASE RELATION (см. главу 4). Ну а как же для 
производных отношений? Рассмотрим, например, выражение 
    S JOIN P, 

    Глава 6. Реляционные операторы: I. Реляционная алгебра	137 

    которое представляет соединение отношения поставщиков и отношения деталей 
по соответствующим городам (значение атрибута CITY общее для двух отношений). 
Что будет заголовком для результата этого соединения? Обязательное наличие 
заголовка диктуется замкнутостью, а системе должно быть известно, что это 
такое (это в равной степени необходимо и пользователю, как мы скоро увидим). 
    Поэтому, если рассматривать замкнутость более строго, каждая реляционная 
операция должна быть определена таким образом, чтобы выдавать результат с 
надлежащим заголовком (т.е. с соответствующим набором необходимых имен 
атрибутов). Причина такого требования к результирующим отношениям заключается 
в необходимости иметь возможность обращаться к именам атрибутов в последующих 
операциях, например в дальнейших операциях, расположенных на более глубоких 
уровнях вложенного выражения. Мы не могли бы, например, даже записать такое 
выражение, как 

    (S JOIN P)   WHERE WEIGHT > 18, 

    если бы не знали, что результат вычисления выражения s JOIN P имеет 
атрибут WEIGHT. Другими словами, необходим такой набор правил наследования 
имен атрибутов, встроенный в алгебру, чтобы можно было предсказывать имена 
атрибутов на выходе произвольной реляционной операции, зная имена атрибутов на 
входе этой операции. Задав такие правила для всех операций, можно 
гарантировать, что для выражения любой сложности будет вычисляться результат, 
имеющий вполне определенный набор атрибутов. 
    Прежде чем двигаться дальше, отметим, что этот аспект алгебры, как 
правило, недооценивается в литературе, кроме двух заметных работ — Холла 
(Hall) и др. [6.9] и Дарвена (Darwen) [4.7]. Версия алгебры, представленная в 
этой главе, была выбрана в значительной мере под влиянием работы Дарвена. (В 
более ранних изданиях этой книги, обращаясь к проблеме наследования имен 
атрибутов, мы использовали подход, который был значительно хуже предложенного Дарвеном.) 
    Наша версия реляционной алгебры определена таким образом, чтобы 
гарантировать, что все отношения будут иметь правильные заголовки, т.е. 
заголовки, в которых все атрибуты имеют правильные имена, уникальные в 
содержащем их отношении. Для достижения этой цели необходим новый оператор 
RENAME, предназначенный для переименования атрибутов в определенном отношении. 
Точнее, для определенного отношения оператор RENAME возвращает (по крайней 
мере концептуально) новую копию отношения, в котором некоторый атрибут имеет 
другое заданное имя. (Определенное отношение, конечно, может быть результатом 
вычисления выражения, включающего другие алгебраические операции.) Например, 
можно написать: 

    S RENAME CITY AS SCITY 

    С помощью этого выражения (обратите внимание, что рассматриваемая запись 
является выражением, а не командой или оператором, а значит, может быть 
вложена в другие выражения) вычисляется отношение, имеющее то же самое тело, 
что и отношение S, но с именем атрибута SCITY вместо CITY: 

    s#	SNAME	STATUS	SCITY 

    SI	Smith	20	London 
    S2	Jones	10	Paris 
    S3	Black	30	Paris 
    S4	Clark	20	London 
    S5	Adams	30	Athens 

    Другие атрибуты этого отношения наследуют имена своих эквивалентов в 
отношении S без изменения. Само отношение безымянное. (Напоминаем читателю, 
что мы начали использовать переменную RENAME в синтаксисе для определения 
внешних ключей. Если нужно освежить этот материал в памяти, обратитесь к главе 5.) 
    В заключение стоит обратить ваше внимание на то, что можно расширять 
понятие замкнутости и дальше. Как отмечалось в главе 5, каждое отношение имеет 
не только заголовок и тело, а и множество потенциальных ключей. Поэтому в определенных 

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

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

    6.3. Синтаксис реляционной алгебры 

    Сейчас самое время ввести конкретный синтаксис для операций реляционной 
алгебры (см. BNF-грамматику на рис. 6.2). Обратите внимание, что синтаксис не 
рассматривается в качестве серьезного кандидата для языка конечного 
пользователя, он не особенно дружественный, а используется как надежная основа 
для обсуждения операторов в оставшейся части главы и, конечно, его можно было 
бы сделать более дружественным с помощью соответствующего "синтаксического 
сахара". И действительно, несколько позже в этой главе будут предложены наши 
собственные простые усовершенствования. 

    expression 
    : :=	monadic-expression  |  dyadic-expression 
    monadic-expression 
    ::=	renaming |  restriction I projection 
    renaming 
    : :=	terra RENAME attribute AS attribute 
    term 
    : :=	relation |   ( expression ) 
    restriction 
    : :=	term WHERE condition 
    projection 
    : :=	term |   term [ attribute-commalist ] 
    dyadic-expression 
    : :=	projection dyadic-operation expression 
    dyadic-opera tion 
    : :=	UNION   I   INTERSECT   |   MINUS   I   TIMES   I   JOIN  |   DIVIDEBY 

    Рис. 6.2. BNF-грамматика для реляционной алгебры 

    Несколько замечаний по грамматике 

    1.  В главе 4 приводилось объяснение условным обозначениям типа 
"commaiist" (что означает список, разделенный запятыми). 
    2.  Обозначения relation (отношение) и attribute (атрибут) определяются 
как идентификаторы, которые представляют собой соответственно имя отношения и 
имя атрибута. 
    3.  Объяснение обозначения condition (условие) приводится ниже в этой главе. 
    В определенной выше грамматике для обеспечения правильного порядка в 
вычислениях сложных выражений необходимо часто использовать скобки. Ниже в 
этой главе описаны некоторые упрощения, во многих случаях позволяющие 
уменьшить общее количество скобок. Об одном из таких упрощений, а именно о 
множественном переименовании, мы поговорим прямо сейчас. Рассмотрим следующий пример: 

    ( S RENAME CITY AS SCITY ) RENAME S# AS SNUM 

    Глава 6. Реляционные операторы: I. Реляционная алгебра 139 

    Как указывалось ранее, внутреннее выражение служит для вычисления 
отношения с телом, таким же как и у отношения S, но имеющим атрибут города с 
именем SCITY, а не CITY; а общее выражение — соответственно для вычисления 
отношения с таким же телом, но дополнительно с измененным именем атрибута 
номера поставщика S# на SNUM. Чтобы можно было переименовать несколько 
атрибутов за один раз, не используя многоуровневые вложенные выражения, 
вводится расширенная версия оператора RENAME, в которой предыдущий пример 
будет выглядеть следующим образом: 

    ( S RENAME CITY AS SCITY, S# AS SNUM ) 

    Иными словами, другой допустимый синтаксис для этой синтаксической 
категории переименования таков: 

    (  term RENAME renarae-ccsmalist ) 

    Здесь обозначение comma11st (как указывалось выше) означает список через 
запятую, а rename означает, что каждый из элементов этого списка представляет 
собой выражение 

    attribute AS attribute 


    6.4. Традиционные операции над множествами 

    Теперь рассмотрим отдельные операции начальной алгебры подробнее, 
используя конкретный синтаксис, представленный в предыдущем разделе. 
    Настоящий раздел касается традиционных операций над множествами, а 
следующий — специальных реляционных операций. 
    Традиционные операции над множествами — это объединение, пересечение, 
вычитание и произведение (точнее, расширенное декартово произведение). Давайте 
сначала рассмотрим объединение. 
    В математике объединение двух множеств является множеством всех элементов, 
принадлежащих или обоим, или одному из исходных множеств. Поскольку отношение 
является, нестрого говоря, множеством кортежей, то, очевидно, можно построить 
объединение двух отношений; результат будет множеством, содержащим все 
кортежи, принадлежащие или обоим, или одному из исходных отношений. Например, 
объединение множества кортежей поставщиков в отношении S и множества кортежей 
деталей в отношении Р является, несомненно, множеством. 
    Однако, хотя такой результат и является множеством, он не является 
отношением; отношения не могут содержать смесь кортежей разных типов, они 
должны содержать однородные кортежи. И конечно, результат тоже должен быть 
отношением, поскольку необходимо, чтобы сохранилось свойство замкнутости. 
Следовательно, объединение в реляционной алгебре не полностью совпадает с 
математическим объединением, вернее, это особая форма объединения, в которой 
требуется, чтобы два исходных отношения, нестрого говоря, имели "одну и ту же 
форму". Это означает, например, что они оба содержат кортежи поставщиков или 
кортежи деталей, а не смесь обоих видов. Если два отношения имеют "одну и ту 
же форму", то их можно объединить и результат объединения будет отношением той 
же формы; иначе говоря, свойство замкнутости будет сохранено. 
    Более точный термин понятия "одна и та же форма" — совместимо по типу.1 
Будем говорить, что два отношения совместимы по типу, если у них идентичные 
заголовки, а точнее, 
    1) если каждое из них имеет одно и то же множество имен атрибутов 
(следовательно, заметьте, они заведомо должны иметь одну и ту же степень); 
    2) если соответствующие атрибуты (т.е. атрибуты с теми же самыми именами в 
двух отношениях) определены на одном и том же домене. 
    1 В предыдущих изданиях этой книги, придерживаясь терминологии [6.2], для 
этого понятия использовался термин union-compatible (дословно — совместимый 
для объединения), который часто встречается в литературе. Причины, побудившие 
нас предпочесть термин type-compatible (совместимо по типу), разъясняются 
далее в этой книге, где также исследуется определение этого термина (и 
связанное с этим ослабление довольно строгих терминов для операций 
объединения, пересечения и вычитания). 

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

    Операции объединения, пересечения и вычитания требуют от операндов 
совместимости по типу. Аргументы, аналогичные приведенным выше для 
объединения, применимы также для пересечения и вычитания. (Операция декартова 
произведения, напротив, такого требования к операндам не выдвигает, хотя и 
имеет собственные требования, как вы скоро убедитесь.) Если необходимо 
выполнить операцию объединения, пересечения или вычитания двух отношений, 
которые почти совместимы по типу, за исключением некоторых различий в именах 
атрибутов, можно использовать оператор RENAME (обсуждаемый выше в этой главе), 
чтобы сделать эти отношения полностью совместимыми по типу, прежде чем 
выполнить необходимую операцию. 
    Теперь можно приступить к определениям традиционных операций над 
множествами, точнее, к тем их разновидностям, которые поддерживаются в 
реляционной алгебре. 

    Объединение 

    Объединением двух совместимых по типу отношений А и В (A UNICN в) 
называется отношение с тем же заголовком, как и в отношениях А и В, и с телом, 
состоящим из множества всех кортежей t, принадлежащих А или В или обоим отношениям. 
    Пример. Пусть отношения А ч В будут такими, как показано на рис. 6.3 
(отношение А представляет поставщиков из Лондона, а отношение В — поставщиков, 
которые, например, поставляют деталь Р1). Тогда выражение A UNION в (см. рис. 
6.3,а) представляет поставщиков, которые или размещаются в Лондоне, или 
поставляют деталь Р1 (либо и то и другое). Обратите внимание, что результат 
имеет три кортежа, а не четыре — повторяющиеся кортежи удаляются по определению. 

    А					В 
    S#	SNAME	STATUS	CITY		S#	SNAME	STATUS	CITY 
    SI S4	Smith Clark	20 20	London London		SI S2	Smith Jones	20 10	London Paris 
    
    
    а)    Объединение (A UNION В) 
    S#	SNAME	STATUS	CITY 
    SI S4 S2	Smith Clark Jones	20 20 10	London London Paris 
    
    
    б)    Пересечение (A INTERSECT В) 
    S#	SNAME	STATUS	CITY 
    SI	Smith	20	London 
    
    
    в)    агаитание (A MINUS В)					г)    Вдоютание (В MINUS A) 
    S#	SNAME	STATUS	CITY		S#	SNAME	STATUS	CITY 
    34	Clark	20	London		32	Jones	10	Paris 
    
    
    Рис. 6.З. Примеры операций объединения, пересечения и вычитания 

    Замечание. Вопрос удаления дубликатов не возникает в других традиционных 
операциях над множествами (пересечение, вычитание и произведение). Фактически 
существует еще только одна операция (помимо объединения), где этот вопрос 
возникает, — проекция. 

    Пересечение 

    Пересечением двух совместимых по типу отношений А и В (A INTERSECT в) 
называется отношение с тем же заголовком, как и в отношениях А и В, и с телом, 
состоящим из множества всех кортежей t, принадлежащих одновременно обоим 
отношениям А и В. Пример. Пусть снова отношения А и В будут такими, как 
показано на рис. 6.3. Тогда выражение д INTERSECT в (см. рис. 6.3,6) 
представляет поставщиков, которые размещаются в Лондоне и поставляют деталь Р1. 

    Глава 6. Реляционные операторы: I. Реляционная алгебра 141 

    Вычитание 

    Вычитанием двух совместимых по типу отношений А и В (A MINUS в) называется 
отношение с тем же заголовком, как и в отношениях А и В, и с телом, состоящим 
из множества всех кортежей t, принадлежащих отношению А и не принадлежащих 
отношению В. 
    Пример. Пусть снова отношения А и В будут такими, как показано на рис. 
6.3. Тогда выражение л MINUS в (см. рис. 6.3,в) представляет поставщиков, 
которые размещаются в Лондоне и не поставляют деталь Р1, а в MINUS л (см. рис. 
6.3,г) представляет поставщиков, которые поставляют деталь Р1 и не размещаются 
в Лондоне. Заметьте, что вычитание учитывает порядок следования точно так же, 
как и в обычной арифметике (например, "5-2" и "2-5" — это не одно и то же). 

    Произведение 

    В математике декартово произведение (или для краткости произведение) двух 
множеств является множеством всех таких упорядоченных пар элементов, что 
первый элемент в каждой паре берется из первого множества, а второй элемент в 
каждой паре берется из второго множества. Следовательно, декартово 
произведение двух отношений должно быть множеством упорядоченных пар кортежей. 
Но опять-таки необходимо сохранить свойство замкнутости', иначе говоря, 
результат должен содержать кортежи, а не упорядоченные пары кортежей. Поэтому 
версия декартова произведения в реляционной алгебре представляет собой 
расширенную форму операции, в которой каждая упорядоченная пара кортежей 
заменяется одним кортежем, образованным из двух сцепленных кортежей этой пары. 
"Сцепление" здесь означает объединение (в смысле теории множеств, а не 
реляционной алгебры); т.е. кортежи { <Al:al>, <K2:a2>, ..., <Лт:ат> } 

    И 

    (  <В1:Ы>,   <В2:Ь2>,   ...,   <Вп:Ьп> } 

    (имена атрибутов показаны для определенности) сцепляются в один кортеж 

    { <Al:al>,   <A2:a2>,   ...,  <fm:aa>,  <В1:Ы>,   <В2:Ь2>,   ...,  <Вп:ЬП> } 

    Другая проблема, возникающая в связи с декартовым произведением, 
заключается в том, что результирующее отношение должно иметь правильно 
сформированный заголовок. Очевидно, что заголовок в своей основе представляет 
просто сцепление двух заголовков исходных отношений. Следовательно, если эти 
два заголовка имеют какие-то общие имена атрибутов, возникает проблема. Если 
допустить такую операцию, то результирующий заголовок будет иметь два 
одинаковых атрибута, а значит, будет "неверно сформированным". Поэтому, если 
нужно построить декартово произведение двух отношений, которые имеют какие-то 
общие имена атрибутов, необходимо прежде для переименования соответствующих 
атрибутов применить оператор RENAME. 
    Итак, декартово произведение двух отношений А и В ( л TIMES в), где А и В 
не имеют общих имен атрибутов, определяется как отношение с заголовком, 
который представляет собой сцепление двух заголовков исходных отношений А и В, 
и телом, состоящим из множества всех кортежей t, таких, что t представляет 
собой сцепление кортежа а, принадлежащего отношению А, и кортежа Ь, 
принадлежащего отношению В. Обратите внимание, что кардинальное число 
результата равняется произведению кардинальных чисел исходных отношений А и В, 
а степень равняется сумме их степеней. 
    Пример. Пусть отношения А и В будут такими, как показано на рис. 6.4 
(отношение А представляет, например, номера всех текущих поставщиков, а 
отношение В— номера всех текущих деталей). Тогда л TIMES в— это все текущие 
пары поставщик-деталь и деталь-поставщик. 

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

    Прежде чем завершить обсуждение этой операции, необходимо указать, что на 
практике явное использование операции декартова произведения требуется только 
для чересчур сложных запросов (см. упражнения и ответы на них в конце главы). 
Другими словами, для реального запроса относительно редко требуется (хотя 
нельзя сказать, что вовсе не требуется) использование операции декартова 
произведения. Эта операция включена в реляционную алгебру главным образом по 
концептуальным соображениям. В частности, как отмечается ниже в этой главе, 
декартово произведение требуется как промежуточный шаг при определении 
операции ^-соединения (а операция 0-соединения используется довольно часто). ~"	'—— 

    А							В 

    S#								P# 

    S1													PI 
    S2													P2 
    S3													P3 
    S4													P4 
    S5													P5 
    P6 
    
    
    Декартово произведение (A TIMES В) 

    S# •"  — '•' "		p#	.... 

    SI		PI		S2	PI			S3	PI		S4		PI		S5    PI 
    SI		P2		S2	P2			S3	P2		S4		P2		S5    P2 
    SI		P3		S2	P3			S3	P3		34		P3		S5    P3 
    SI		P4		S2	P4			S3	P4		S4		P4		S5    P4 
    SI		P5		S2	P5			S3	P5		S4		P5		S5    P5 
    SI		P6		S2	P6			S3	P6		S4		P6		S5    P6 
    
    
    Рис. 6.4. Пример операции декартова произведения 

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

    Несколько синтаксических упрощений 

    Легко проверить, что операция объединения ассоциативна, т.е. если А, В и 
С— произвольные выражения (дающие совместимые по типу отношения), то выражения 

    ( A UNION В ) UNION С 

    И 

    A UNION ( В UNION С ) 

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

    A UNION В UNION С 

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

    A UNION В 

    И 

    В UNION A 

    эквивалентны; точно так же и для операций пересечения и произведения. 

    Глава 6. Реляционные операторы: I. Реляционная алгебра 143 

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

    6.5. Специальные реляционные операции 

    Теперь переключим внимание на специальные реляционные операции: выборку, 
проекцию, соединения (разных видов) и деление. 

    Выборка 

    Как отмечалось в начале этой главы операция выборки также называется 
операцией ограничения, поэтому далее в этой книге будет также употребляться 
термин ограничение, если подразумевается алгебраическая операция. Выборка — 
это сокращенное название Q-выборки, где 0 обозначает любой скалярный оператор 
сравнения (=, *, >, > и т.д.). 6-выборкой из отношения А по атрибутам X и У (в 
этом порядке) 

    A WHERE X 6 Y 

    называется отношение, имеющее тот же заголовок, что и отношение А, и тело, 
содержащее множество всех кортежей I отношения А, для которых проверка условия 
"л: е г" дает значение истина. Атрибуты X и Y должны быть определены на одном 
и том же домене, а оператор должен иметь смысл для этого домена. (Обратите 
внимание, что не все операторы сравнения (0) имеют смысл для всех доменов. 
Например, рассмотрим домен SEX (пол) со значениями "Male" (мужской) и "Female" 
(женский). Этот очевидный пример показывает, что для таких доменов имеют смысл 
только операторы сравнения равно и не равно, а оператор меньше не имеет 
смысла. Мы еще вернемся к данной теме далее в этой книге.) 
    Скалярное литеральное значение может быть указано как вместо атрибута X, 
так и вместо атрибута Y (или, естественно, вместо обоих); на практике это 
обычный случай.1 Например: 

    A WHERE X 9 literal 

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

    1. A WHERE cl AND с2	=	( Л WHERE cl ) INTERSECT ( A WHERE c2 ) 
    2. Л WHERE cl OR c2	s	( Л WHERE cl ) UNION ( A WHERE c2 ) 
    3. A WHERE NOT с	s	A MINUS ( A WHERE с ) 

    Поэтому впредь будем подразумевать, что условие сравнения в выражении 
WHERE для операции выборки содержит произвольное число логических сочетаний 
простых сравнений (с использованием круглых скобок, если необходимо указать 
желаемый порядок вычисления). Если условие может быть истолковано как истина 
или ложь для данного кортежа, то рассматривая такой кортеж как отдельный, это 
условие называют условием выборки. 
    1 Необходимо подчеркнуть, что замена Л" и К литералами в действительности 
просто другая синтаксически сокращенная запись. Например, выборку S WHERE CITY 
= 'London' можно считать сокращением выражения следующего вида: (EXTEND S ADD 
'London' AS LONDON) WHERE CITY = LONDON. (См. обсуждение оператора EXTEND 
далее в этой главе.) 

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

    Итак, мы определили синтаксическое обозначение условия.1 На рис. 6.5 
приведено несколько примеров выборки. 

    S WHERE CITY = 'London1 
    S#	SNAME	STATUS	CITY 
    SI S4	Smith Clark	20 20	London London 
    
    
    Р WHERE WEIGHT < 14 
    P#	PNAME		COLOR	WEIGHT	CITY 
    PI P5	Nut Cam		Red Blue	12 12	London Paris 
    
    
    SP ЩЕКЕ S# = ' SI ' AND P# = ' PI ' 
    S#        P#		CTY 
    SI        PI		300 
    
    
    Рис. 6.5. Примеры операций выборки 

    Проекция 

    Проекцией отношения А по атрибутам X, Y,..., Z, где каждый из атрибутов 
принадлежит отношению А (А [ х, Y, ... , z ]), называется отношение с 
заголовком {X, Y,..., Z} и телом, содержащим множество всех кортежей {Х:х, 
Y:y,..., Z:z}, таких, для которых в отношении А значение атрибута X равно х, 
атрибута Y равно у, ..., атрибута Z равно z. Таким образом, с помощью 
оператора проекции получено "вертикальное" подмножество данного отношения, 
т.е. подмножество, получаемое исключением всех атрибутов, не указанных в 
списке атрибутов, и последующим исключением дублирующих кортежей (подкортежей) 
из того, что осталось. 
    Никакой атрибут не может быть указан в списке атрибутов более одного раза. 
    Обратите внимание на следующее. 
    1. Наш синтаксис позволяет опустить список атрибутов совсем (вместе с 
квадратными скобками). Действие такой операции эквивалентно указанию списка 
всех атрибутов исходного отношения, т.е. такая операция представляет собой 
тождественную проекцию. Другими словами, имя отношения является, конечно, 
допустимым реляционным выражением. 
    2.  Проекция вида R[ ], т.е. такая, в которой список атрибутов не 
пропущен, но пустой, тоже допустима. Она представляет собой "нулевую" проекцию. 
    Несколько примеров проекций показано на рис. 6.6. Обратите внимание, что в 
первом примере (проекция поставщиков по атрибуту CITY), хотя отношение S имеет 
пять кортежей и, следовательно, пять городов, в результате есть только три 
города, поскольку исключены дублирующие кортежи. Аналогичные замечания можно 
сделать и для других примеров. 
    Отметим, что на практике часто бывает удобно указывать не те атрибуты, по 
которым берется проекция, а те, которые проекцией "отбрасываются". Например, 
удобнее сказать: "проекция, исключающая атрибут WEIGHT из отношения Р" вместо 
"проекция отношения Р по атрибутам Р#, PNAME, COLOR и CITY". Однако здесь не 
предлагается никакого конкретного синтаксиса для этой альтернативной, но, 
конечно, эквивалентной версии операции проекции. 

    Естественное соединение 

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

    Глава 6. Реляционные операторы: I. Реляционная алгебра 145 

    "соединение". Мы будем следовать этому, применяя в нашем синтаксисе для 
обозначения естественного соединения ключевое слово JOIN (соединение). Далее 
приводится определение (оно несколько абстрактное, но мы считаем, что читатели 
уже знакомы с естественным соединением на интуитивном уровне по материалу 
главы 3). 

    S [ CITY J 
    CITY 
    London Paris Athens 
    
    
    Р [ COLOR, CITY 1 
    COLOR	CITY 
    Red Green Blue Blue	London Paris Rome Paris 
    
    
    ( S WHERE CITY = 'PARIS' ) [ S# ] 
    S# 
    S2 S3 
    
    
    Рис. 6.6. Примеры операций проекции 

    Пусть отношения А и В имеют заголовки {Х1,Х2,...,Хт, Yl, Y2,...,Yn} и { 
Yl, Y2,..., Yn, Zl, Z2,..., Zp } 
    соответственно; т.е. атрибуты Yl, Y2,..., Yn (и только они) — общие для 
двух отношений; XI, Х2,... ,Хт — остальные атрибуты отношения A; Zl, Z2,..., 
Zp— остальные атрибуты отношения В. Предположим также, что соответствующие 
атрибуты (т.е. атрибуты с одинаковыми именами) определены на одном и том же 
домене. Давайте теперь рассматривать выражения {XI,Х2,... ,Хт}, {Yl, Y2,..., 
Yn} и {Z/, Z2,..., Zp} как три составных атрибута X, Y и Z соответственно. 
Тогда естественным соединением отношений А и В (A JOIN в) называется отношение 
с заголовком {X, Y, 7} и телом, содержащим множество всех кортежей {Х:х, Y:y, 
Z:z}, таких, для которых в отношении А значение атрибута А1 равно х, а 
атрибута Y равно у, и в отношении В значение атрибута Y равно у, а атрибута Z 
равно z. 
    Пример естественного соединения (естественное соединение s JOIN p по 
общему атрибуту CITY) приведен на рис. 6.7. 
    Замечание. Хотелось бы еще раз остановиться на том (хотя это неоднократно 
отмечалось и показано на рис. 6.7), что соединения не всегда выполняются по 
внешнему ключу и соответствующему потенциальному ключу (возможно, 
соответствующему первичному ключу), хотя такие соединения весьма 
распространены и являются важным частным случаем. 
    Соединение, как мы уже определили, обладает и свойством ассоциативности, и 
свойством коммутативности. Отсюда следует, что выражения 

    ( A JOIN В )   JOIN С 
    И 
    A JOIN   (  В JOIN С ) 

    могут быть однозначно упрощены к следующему: 

    A JOIN В JOIN С 

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

    Кроме того, выражения 

    A JOIN В 

    И 

    В JOIN A 

    эквивалентны. 
    
    
    s#	SNAME	STATUS	CITY	P#	PNAME	COLOR	WEIGHT 

    SI	Smith	20	London	PI	Nut	Red	12 
    SI	Smith	20	London	P4	Screw	Red	14 
    SI	Smith	20	London	P6	Cog	Red	19 
    S2	Jones	10	Paris	P2	Bolt	Green	17 
    S2	Jones	10	Paris	P5	Cam	Blue	12 
    S3	Blake	30	Paris	P2	Bolt	Green	17 
    S3	Blake	30	Paris	P5	Cam	Blue	12 
    S4	Clark	20	London	PI	Nut	Red	12 
    S4	Clark	20	London	P4	Screw	Red	14 
    S4	Clark	20	London	P6	Cog	Red	19 
    
    
    Рис, 6.7, Естественное соединение s JOIN p 

    Отметим также, что если отношения А и В не имеют общих имен атрибутов, то 
выражение A JOIN в эквивалентно д TIMES в (т.е. естественное соединение 
превращается в этом случае в декартово произведение). 

    6-соединение 

    Теперь займемся операцией 6-соединение. Эта операция предназначается для 
тех случаев (сравнительно редких, но, тем не менее, всем известных), когда нам 
нужно соединить вместе два отношения на основе некоторых условий, отличных от 
эквивалентности. Пусть отношения А и В не имеют общих имен атрибутов (как и в 
рассмотренной выше операции декартова произведения) и 9 определяется так же, 
как и в операции выборки. Тогда 0-соединением отношения А по атрибуту X с 
отношением В по атрибуту Y называется результат вычисления выражения 

    ( Д TIMES В )   WHERE X Q  Y 

    Другими словами, 0-соединение — это отношение с тем же заголовком, что и 
при декартовом произведении отношений А и В, и с телом, содержащим множество 
кортежей t, таких что t принадлежит этому декартову произведению и вычисление 
условия "XQ У" дает значение истина для этого кортежа. Атрибуты А" и Y должны 
быть определены на одном и том же домене, а операция должна иметь смысл для 
этого домена. 
    В качестве примера предположим, что нам необходимо вычислить 
боль-ше-соединение отношения S по атрибуту CITY с отношением Р по атрибуту 
CITY (предполагается, что ">" имеет смысл для сравнения названий городов и 
интерпретируется просто как "далее в алфавитном порядке"). Соответствующим 
выражением реляционной алгебры будет 

    ( ( S RENAME CITY AS SCITY ) TIMES 
    ( P RENAME CITY AS PCITY ) ) WHERE SCITY > PCITY 

    Результат показан на рис. 6.8. Конечно, достаточно было бы переименовать 
лишь один из двух атрибутов CITY. Единственный смысл двойного переименования — 
это симметрия. 
    Заметьте, что 9-соединение — это не примитивная операция; она всегда 
эквивалента двум операциям: нахождению расширенного декартова произведения 
двух отношений (при необходимости с переименованием соответствующих атрибутов) 
и последующему выполнению указанной выборки из полученного результата. 

    Глава 6. Реляционные операторы: I. Реляционная алгебра 147 

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

    s#	SNAME	STATUS	SCITY	P#	PNAME	COLOR	WEIGHT	PCITY 

    S2	Jones	10	Paris	PI	Nut	Red	12	London 
    S2	Jones	10	Paris	P4	Screw	Red	14	London 
    S2	Jones	10	Paris	P6	Cog	Red	19	London 
    S3	Blake	30	Paris	PI	Nut	Red	12	London 
    S3	Blake	30	Paris	P4	Screw	Red	14	London 
    S3	Blake	30	Paris	P6	Cog	Red	19	London 

    Рис. 6.8. Больше-соединение отношений поставщиков и деталей по атрибуту города 

    S JOIN P, 

    эквивалентно следующему более сложному выражению: 

    ( ( S TIMES (P RENAME CITY AS PCITY ) ) WHERE CITY = PCITY ) [ S#, SNAME, 
STATUS, CITY, P#, PNAME, COLOR, WEIGHT ] 


    Деление 

    Пусть отношения А и В имеют заголовки 

    {Х1,Х2,...,Хт, Yl, Y2, ..., Yn} 

    и 

    { Yl, Y2,..., Yn } 

    соответственно, т.е. атрибуты Yl, Y2, ... , Yn — общие для двух отношений, 
и отношение А имеет дополнительные атрибуты XI, Х2, ... ,Хт, а отношение В не 
имеет дополнительных атрибутов. (Отношения А и В представляют соответственно 
делимое и делитель.) Предположим также, что соответствующие атрибуты (т.е. 
атрибуты с одинаковыми именами) определены на одном и том же домене. Пусть 
теперь выражения {XI, Х2, ... ,Хт} и {Yl, Y2, ... , Yn} обозначают два 
составных атрибута X и Y соответственно. Тогда делением отношений А на В (д 
DIVIDEBY в) называется отношение с заголовком {X} и телом, содержащим 
множество всех кортежей {Х:х}, таких что существует кортеж {Х:х, Y:y}, который 
принадлежит отношению А для всех кортежей {Y:y}, принадлежащих отношению В. 
Нестрого это можно сформулировать так: результат содержит такие .Y-значения из 
отношения А, для которых соответствующие F-значения (из А) включают все 
F-значения из отношения В. 
    На рис. 6.9 показаны некоторые простые примеры деления. В каждом случае 
делимое (отношение DEND) — это проекция отношения SP по атрибутам S# и Р#; а 
делители (отношения DOR) — такие, как показано на рисунке. В частности, 
обратите внимание на последний пример, в котором делителем является отношение, 
содержащее номера всех известных в данный момент деталей; в результате, 
очевидно, получим номера поставщиков, поставляющих все эти детали. Как видно 
из этого примера, оператор DIVIDEBY полезен именно для запросов такого рода. 
Более того, если запрос на обычном языке включает слово "все" ("получить 
поставщиков, поставляющих все детали"), тогда почти наверняка понадобится 
операция деления. 

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

    Прежде чем завершить раздел, необходимо отметить, что следует быть 
осторожным при использовании этой операции; в частности, трудности возникают в 
связи с пустыми отношениями. Улучшенная форма оператора DIVIDEBY PER позволяет 
избежать этих трудностей, но, к сожалению, она сложнее первоначальной. Ее 
описание можно найти в комментариях к [6.4]. Стоит отметить, что запросы типа 
деления часто проще описываются в терминах реляционных сравнений (об этом речь 
идет несколько ниже). 

    DEND					52 S2 S3 S4 S4 S4	PI P2 P2 P2 P4 P5 

    S#	p# 

    SI SI SI SI SI SI	PI P2 P3 P4 P5 P6 
    
    
    DOR			DOR 
    P# ~P1				P#		DOR   1 P#    1 
    P2 P4		PI P2 P3 P4 P5 P6 
    
    
    
    
    
    
    DEND DIVIDEBY DOR 
    
    
    S#				S# SI S4		( S#    | 
    SI S2 
    
    
    Рис. 6.9. Примеры деления 


    6.6. Примеры 

    В этом разделе представлено несколько примеров использования реляционной 
алгебры для выражения словесных запросов в виде формулы. Читателю 
рекомендуется проверить их на примерных данных рис. 3.8. 
    Замечание. Каждый из этих операторов можно дополнить завершающим 
оператором присвоения и присвоить значение выражения какому-либо именованному 
отношению. Для краткости обычно этот шаг опускается. 
    6.6.1. Получить имена поставщиков, которые поставляют деталь Р2 

    (   (  SP JOIN S   )   WHERE P# =   'Р21   )    [  SNAME  ] 

    Пояснение. Первое естественное соединение отношений SP и S осуществляется 
по номерам поставщиков и в результате дополняет (концептуально) каждый кортеж 
отношения SP соответствующей информацией поставщика (т.е. соответствующими 
значениями атрибутов SNAME, STATUS и CITY). Затем из этого соединения просто 
выбираются такие кортежи, в которых значение атрибута Р# равно Р2. И наконец, 
выполняется проекция этой выборки по атрибуту SNAME. Конечный результат имеет 
единственный атрибут SNAME. 

    Глава 6. Реляционные операторы: I. Реляционная алгебра 149 

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

    { ( ( Р WHERE COLOR = 'Red1 ) JOIN SP ) [ S# ] JOIN S ) [ SNAME ] 

    И снова в результате получаем единственный атрибут SNAME. Вот другая 
формулировка того же запроса: 

    ( ( ( Р WHERE COLOR = 'Red' ) [ Р* ] JOIN SP ) JOIN S ) [ SNAME ] 

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

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

    (   (  SP   [  S#,   Р#]   DIVIDEBY Р   [  Р#   ]   JOIN S  )    [  SNAME  ] 

    И вновь в результате получаем единственный атрибут SNAME. 
    Замечание. Трактовать смысл этого выражения как "имена поставщиков, 
которые поставляют все детали" несколько некорректно. Смотрите объяснения в 
комментариях к [6.4]. 
    6.6.4. Получить номера поставщиков, поставляющих по крайней мере все те 
детали, которые поставляет поставщик S2 

    SP   [  S#,   Р*   ]   DIVIDEBY   (  SP WHERE S# =   'S2'   }    [  P#  ] 

    В результате получаем единственный атрибут S#. 
    6.6.5. Получить все пары номеров поставщиков, размещенных в одном городе 

    ( ( ( S RENAME S# AS FIRSTS* ) [ FIRSTS», CITY ] JOIN ( S RENAME S# AS 
SECONDS* ) [SECONDS*, CITY ] ) 
    WHERE FIRSTS* < SECONDS* ) [ FIRSTS*, SECONDS* ] 

    В результате получаем отношение из двух атрибутов — FIRSTS# и SECONDS*. 
Конечно, достаточно было бы переименовать лишь один атрибут в одном из 
операндов соединения. 
    6.6.6. Получить имена поставщиков, которые не поставляют деталь Р2 

    ( ( S [ S* ] MINUS ( SP WHERE P# = 'P2' ) [ S* ] ) 
    JOIN S ) [SNAME] 

    В результате получаем единственный атрибут SNAME. 
    Разберем последний пример несколько подробнее, чтобы проиллюстрировать еще 
один момент. Не всегда просто представить себе, как выразить данный запрос в 
виде одной вложенной формулы (особенно если запрос сложный). Однако это и не 
обязательно. Вот пошаговое решение нашей проблемы: 

    Т1	= S [ S* ] ; 
    Т2	= SP WHERE Р* = 'Р2' ; 
    ТЗ	= Т2 [ S* ] ; 
    Т4	= Tl MINUS ТЗ ; 
    Т5	= Т4 JOIN S ; 
    Т6	= Т5 [ SNAME ] ; 

    Отношение Т6 содержит необходимый результат. 
    Пояснение. Здесь знак ":=" означает оператор присвоения отношений 
(подробнее обсуждается ниже в этой главе). Для примера будем подразумевать, 
что имена отношений вида Ti используются системой для обращения к временным 
отношениям, которые автоматически создаются, когда им впервые присваиваются 
значения, и автоматически уничтожаются в некоторое подходящее время (например, 
в конце сеанса). Затем, если система включает возможность отсрочки вычислений 
(как, например, это делает система PRTV [6.8]), то разбиение запроса на 
последовательность небольших шагов таким способом не будет требовать абсолютно 
никаких нежелательных затрат производительности. Вместо этого весь запрос 
можно выполнить следующим образом. 

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

    1.  Предположим, что за приведенной последовательностью шагов следует 
запрос отображения на экран отношения Т6 (с помощью оператора DISPLAY нашего 
гипотетического языка). В запросе отображения на экран предполагается, что 
система не может отложить вычисление на какое-то время, а вместо этого должна 
как-то вычислить значение Т6. 
    2.  Для того чтобы вычислить значение Т6, которое является проекцией Т5 по 
атрибуту SNAME, система должна сначала вычислить значение Т5; чтобы вычислить 
значение Т5, которое является соединением Т4 и S, система должна сначала 
вычислить значение Т4 и т.д. Иными словами, система должна эффективно 
вычислять исходные вложенные выражения, точно так же, как пользователь, в 
первую очередь, должен эффективно писать такие вложенные запросы. 
    В следующем разделе вы кратко ознакомитесь с общими вопросами вычисления 
таких вложенных выражений (к этой теме мы еще вернемся далее в книге). 

    6.7. Зачем нужна алгебра 

    Итак, в предыдущих разделах описана реляционная алгебра, т.е. набор 
операторов для отношений. Речь идет о следующих операторах: выборка, проекция, 
произведение, объединение, пересечение, вычитание, соединение (естественное и 
9-соединение) и деление плюс оператор переименования атрибутов RENAME. (За 
исключением RENAME, эти операторы составляют набор, впервые определенный 
Коддом в [6.2].) Также представлен возможный синтаксис для этих операций, 
который использовался во многих приведенных здесь примерах. 
    Как отмечалось выше в этой главе, восемь операторов Кодда не представляют 
минимального набора операторов (они задумывались не с этой целью), так как не 
все из них примитивны, их можно определить в терминах других операторов. 
Например, естественное соединение — это проекция выборки произведения. 
Фактически три операции из этого набора, а именно соединение, пересечение и 
деление, можно определить через остальные пять (к этому мы еще вернемся в 
конце главы). Эти пять операций (выборка, проекция, произведение, объединение 
и вычитание) можно рассматривать как примитивные в том смысле, что ни одна из 
них не выражается через другие. Поэтому минимальный набор будет состоять из 
этих пяти примитивных операций. Однако на практике другие три операции (в 
особенности соединение) настолько часто используются, что имеет смысл 
обеспечить их непосредственную поддержку, несмотря на то что они не примитивны. 
    Теперь пришло время объяснить один важный момент. До сих пор 
предполагалось (хотя явно это и не указывалось), что главное назначение 
алгебры — это только выборка данных. Однако это не так. Основная цель алгебры 
— обеспечить запись выражений. Такие выражения, в свою очередь, хотя и 
предполагают различное применение, включая, конечно, и выборку, но, 
безусловно, не ограничены лишь этой одной функцией. В приведенном ниже списке 
указаны некоторые возможные применения таких выражений. (В основном, конечно, 
такие выражения представляют отношения, а эти отношения, в свою очередь, 
определяют область выборки, обновления и других операций, как показано в списке.) 
    •  Определение области выборки, т.е. определение данных для их выбора, как 
результата операции выборки. 
    •  Определение области обновления, т.е. определение данных для их вставки, 
изменения или удаления, как результата операции обновления. 
    •  Определение (именованных) виртуальных отношений, т.е. определение 
данных для их визуализации через представления (подробнее это будет 
обсуждаться в последующих главах книги). 

    Глава 6. Реляционные операторы: I. Реляционная алгебра	151 

    •  Определение снимка, т.е. определение данных для сохранения в виде 
"мгновенного снимка" отношения (подробнее это будет обсуждаться в последующих главах). 
    •  Определение правил безопасности, т.е. определение данных, для которых 
осуществляется контроль доступа (подробнее это будет обсуждаться в последующих главах). 
    •  Определение требований устойчивости, т.е. определение данных, которые 
входят в область для некоторых операций управления одновременным доступом 
(подробнее это будет обсуждаться в последующих главах). 
    •  Определение правил целостности, т.е. некоторых особых правил, которым 
должна удовлетворять база данных, наряду с общими правилами (или 
"метаправилами"), представляющими часть реляционной модели и применяемыми к 
каждой базе данных (подробнее это будет обсуждаться в последующих главах). 
    В общем выражения служат для символического высокоуровневого представления 
намерений пользователя (например, некоторого определенного запроса). И именно 
потому, что эти выражения символические и высокоуровневые, ими можно 
манипулировать в соответствии с многочисленными правилами преобразования. 
Например, выражение 

    (   (  SP JOIN S  )   WHERE Р# =   'Р2'   )    [  SNAME  ] 

    ("имена поставщиков, поставляющих деталь Р2") можно преобразовать в 
логически эквивалентное, но, возможно, более рациональное выражение 

    (   (  SP WHERE Р# =   'Р21   )   JOIN S  )    [  SNAME ] 

    (Вопрос для самопроверки, В каком смысле последнее выражение, возможно, 
более рационально? Почему только "возможно"?) 
    Таким образом, алгебра служит хорошим базисом для оптимизации (чтобы 
вспомнить, что такое оптимизация, обратитесь к главе 3). Следовательно, если 
пользователь выразил свой запрос с помощью первого из двух приведенных выше 
выражений, то оптимизатор должен преобразовать его во второе выражение перед 
выполнением (в идеале производительность не должна зависеть от формы, в 
которой пользователь выражает запрос). К этой теме мы еще вернемся в ходе 
дальнейшего изложения. 
    В заключение отметим, что благодаря своей фундаментальной природе алгебра 
часто используется в качестве критерия возможностей выражения пользовательских 
намерений для некоторого определенного реляционного языка (например, такого 
как SQL). В общем, язык называют реляционно полным [6.2], если его 
возможности, по крайней мере, соответствуют возможностям, обеспечиваемым 
алгебраическими операциями, т.е. если выражения этого языка позволяют 
определить каждое отношение, которое может быть определено с помощью 
алгебраических выражений. Понятие реляционной полноты подробнее обсуждается в 
следующей главе. 

    6.8. Операции расширения и подведения итогов 

    Многие авторы предлагали новые алгебраические операторы после определения 
Коддом первоначальных восьми. В этом разделе детально рассматриваются два 
таких оператора— EXTEND (расширение) и SUMMARIZE (подведение итогов), которые 
удачно дополняют основной набор восьми операторов. При этом, в основном 
схематически, повторяются описания статьи Дарвена [4.7], которая, в свою 
очередь, подверглась большому влиянию со стороны работ Тодда и других авторов 
по системе PRVT [6.7-6.9]. 

    Операция расширения 

    Читатель, возможно, заметил, что в описанной нами алгебре нет средств для 
скалярных вычислений. Конечно, на практике такие возможности необходимы. 
Например, может понадобиться запросить из базы данных арифметическое 
выражение, такое как WEIGHT*454, или сослаться на такое значение в выражении 
WHERE при выборке 

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

    (вспомним, что вес в нашем примере приведен в фунтах; выражение WEIGHT*454 
переводит этот вес в граммы). Для обеспечения таких возможностей и 
предназначена операция расширения. Точнее, с помощью этой операции из 
определенного отношения (по крайней мере концептуально) создается новое 
отношение; оно похоже на начальное, но содержит дополнительный атрибут, 
значения которого получены посредством некоторых скалярных вычислений. 
Например, можно написать: 

    EXTEND P ADD   ( WEIGHT *  454   )   AS GMWT 

    С помощью этого выражения создается новое отношение с таким же заголовком, 
как и у отношения Р, за исключением дополнительного атрибута GMWT. Каждый 
кортеж этого отношения совпадает с соответствующим кортежем отношения Р, но 
содержит еще дополнительное значение GMWT, вычисляемое в соответствии с 
указанным выражением (рис. 6.10). 

    р#	PNAME	COLOR	WEIGHT	CITY	GMWT 

    ' Р1	Nut	Red	12	London	5448 
    Р2	Bolt	Green	17	Paris	7718 
    РЗ	Screw	Blue	17	Rome	7718 
    Р4	Screw	Red	14	London	6356 
    Р5	Cam	Blue	12	Paris	5448 
    Р6	Cog	Red	19	London	8626 

    Рис. 6.10. Пример операции расширения 

    Теперь можно использовать атрибут GMWT в операциях проекции, выборки и 
т.д. Например, так: 

    ( EXTEND P ADD ( WEIGHT * 454 ) AS GMWT ) WHERE GMWT > 10000 

    Замечание. Конечно, более дружественный пользовательский язык позволяет 
вставлять выражения непосредственно с помощью оператора WHERE: 

    Р WHERE ( WEIGHT * 454 ) > 10000 

    Однако такая возможность — это просто синтаксическое усовершенствование. 
    Можно включить в синтаксис, приведенный на рис. 6.2, операцию EXTEND, 
добавив новый вид унарных выражений со следующим синтаксисом: 

    EXTEND term ADD scalar-expression AS attribute 

    Например: 

    EXTEND A ADD exp AS  Z 

    Результатом этого выражения (обратите внимание, что это выражение, а не 
команда или оператор) будет отношение с заголовком, эквивалентным заголовку 
отношения Л, расширенному новым атрибутом Z', который подсчитывается 
вычислением скалярного выражения ехр для кортежа отношения А. При этом 
отношение А не должно иметь атрибута Z и выражение ехр не должно ссылаться на 
атрибут Z. Заметьте, что кардинальное число результата равно кардинальному 
числу отношения А, а степень результата равна степени отношения А плюс единица. 
    Приведем еще несколько примеров. 

    1. EXTEND S ADD 'Supplier1 AS TAG 

    Это выражение эффективно дополняет каждый кортеж отношения S символьным 
значением "Supplier" (конечно, скалярный литерал (символьное значение) 
является простым случаем скалярного выражения). 

    2.    EXTEND   (  Р JOIN SP  )   ADD   ( WEIGHT  * QTY )   AS SHIPWT 

    ' В системе должен быть определен домен для атрибута Z. Обсуждение этого 
вопроса (и многих связанных с ним) будет продолжено далее в этой книге. 

    Глава 6. Реляционные операторы: I. Реляционная алгебра 153 

    Операнд term оператора EXTEND может быть произвольным реляционным 
выражением, заключенным в скобки. 

    3.  ( EXTEND S ADD CITY AS SCITY ) [S#, SNAME, STATUS, SCITY ] 

    Имя атрибута, такое как CITY, — также допустимое скалярное выражение. 
Заметьте, что этот пример равносилен следующему: 

    S RENAME CITY AS SCITY 

    Иными словами, оператор RENAME не примитивен! Он может быть определен 
через оператор EXTEND. 

    4. EXTEND S ADD COUNT ( ( SP RENAME S# AS X ) WHERE X = S# ) AS NP 

    Результат этого выражения показан на рис. 6.11. 
    
    s#	SNAME	STATUS	CITY	NP 

    SI	Smith	20	London	6 
    S2	Jones	10	Paris	2 
    S3	Black	30	Paris	1 
    S4	Clark	20	London	3 
    S5	Adams	30	Athens	0 
    
    
    Рис. 6.11. Еще один пример операции расширения 

    Пояснения: 
    • Для данного поставщика в отношении S выражение 
    (   (  SP RENAME S# AS X  )   WHERE X = S#   ) 
    дает множество поставок, соответствующих этому поставщику. 
    • Затем "итоговая функция" COUNT применяется для этого множества поставок 
и возвращает соответствующее кардинальное число (которое является, конечно, 
скалярным значением). 
    Атрибут NP в результирующем отношении представляет количество деталей, 
поставляемых поставщиком, который идентифицируется соответствующим значением 
S#. Обратите внимание, в частности, на значение NP для поставщика S5; 
множество кортежей отношения SP для этого поставщика пусто, поэтому функция 
COUNT возвращает нуль. 
    Замечание. Как указывалось ранее, функция COUNT— это пример итоговой 
функции (т.е. функции, берущей в качестве аргумента множество значений и 
возвращающей одно значение). Функции зим (сумма), AVG (среднее значение), МАХ 
(максимальное значение) и MIN (минимальное значение) — это хорошо известные 
примеры итоговых функций. Если аргумент такой функции будет пустым множеством, 
то функция COUNT (как объяснено выше) возвращает нуль, функция зим также 
возвращает нуль; функции МАХ и мш возвращают максимальное и минимальное 
значения соответствующего домена, а функция AVG генерирует исключительную 
ситуацию. Вернемся к оператору EXTEND: подвыражения, подобные 

    (   (  SP RENAME S# AS X  )   WHERE X = S#   ) 

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

    ( MATCHING expression ) 

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

    (где expression может быть произвольным реляционным выражением) — это 
выражение, допустимое в качестве аргумента для итоговой функции, используемой 
в операторе EXTEND, со следующей интерпретацией. Пусть оператор EXTEND имеет вид 

    EXTEND Rl ADD agg-fun   ( MATCHING R2 )   AS   ... 
    Пусть Y— набор общих_ атрибутов отношений Rl и R2. Тогда выражение 

(MATCHING R2) по определению является сокращением выражения 
    (   (  R2 RENAME  Y AS X )  WHERE X =  Y ) 

    для некоторого соответствующего (в общем случае произвольного) имени X. С 
учетом этого упрощения общее выражение первоначального запроса выглядит 
следующим образом: 

    EXTEND S ADD COUNT ( MATCHING SP ) AS NP 

    5.  И наконец, можно также ввести сокращение для множественной операции 
EXTEND, как показано в следующем примере (выше в этой главе обсуждалось 
множественное переименование): 

    ( EXTEND P ADD CITY AS PCITY, ( WEIGHT * 454 ) AS GMWT ) 


    Операция подведения итогов 

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

    SUMMARIZE SP BY ( Р# ) ADD SUM ( QTY ) AS TOTQTY 

    вычисляется отношение с заголовком {P#,TOTQTY}, в котором существует один 
кортеж для каждого значения Р# в отношении SP; в этом кортеже содержится 
значение Р# и соответствующее общее количество деталей (рис. 6.12). Другими 
словами, отношение Р концептуально "перегруппировано" в множества кортежей (по 
одному множеству для каждого значения Р#), и из каждой группы в общий 
результат сгенерирован один кортеж.1 
    
    р#	TOTCTY 
    Р1	600 
    Р2	1000 
    РЗ	400 
    Р4	500 
    Р5	500 
    Р6	100 

    Рис. 6.12. Пример выполнения операции SUMMARIZE 

    В терминах синтаксиса рис. 6.2 введем новый вид,унарных выражений: 

    SUMMARIZE term BY   (  attribute-commalist ) 
    ADD aggregate-expression AS attribute 

    Например: 

    SUMMARIZE A BY   {  Al,   A2,    . . .,   An  )   ADD exp AS Z 

    Здесь A1,A2,... ,An— отдельные атрибуты отношения А. Результатом этого 
выражения (обратите внимание, что приведенный пример является выражением, а не 
ко
    1 В действительности в предыдущем издании этой книги (как и в языке SQL — 
см. главу 8) использовалось ключевое слово GROUPBY вместо BY, но слово GROUPBY 
имеет несколько процедурный под
    текст, и в любом случае слово BY короче. 

    Глава 6. Реляционные операторы: I. Реляционная алгебра 155 

    мандой или оператором) будет отношение с заголовком {А1,А2, ...,Ап, Z}1 и 
с телом, содержащим все такие кортежи /, которые являются кортежами проекции 
отношения А по атрибутам Al, A2,..., An, расширенного значением для нового 
атрибута Z; такое новое значение Z подсчитывается вычислением итогового 
выражения ехр по всем кортежам отношения А, которое имеет те же самые значения 
для атрибутов А1,А2,... ,Ап, что и кортеж л Список attribute-commaiist не 
должен включать атрибут с именем Z, а выражение ехр не должно ссылаться на 
атрибут Z. Заметьте, что кардинальное число результата равно кардинальному 
числу проекции отношения А по атрибутам Al, A2,..., An, а степень результата 
равна степени такой проекции плюс единица. 
    Вот другой пример, который показывает, что операнд term оператора 
SUMMARIZE может быть произвольным реляционным выражением, заключенным в 
круглые скобки: 

    SUMMARIZE ( Р JOIN SP ) BY ( CITY ) ADD COUNT AS NSP 

    Результат будет подобен следующему: 

    CITY	NSP 
    London	5 
    Paris	6 
    Rome	1 

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

    1. SUMMARIZE SP BY ( ) ADD SUM ( QTY ) AS GRANDTOTAL 

    В этом примере атрибутов, по которым подводится итог, нет вообще. 
Предположим на некоторое время, что отношение SP содержит по крайней мере один 
кортеж и все кортежи отношения имеют "одинаковое значение" по пустому 
множеству атрибутов, т. е. итоговое вычисление производится только один раз 
для всего отношения. Таким образом, вычисление всего выражения сводится к 
одному отношению с одним атрибутом и одним кортежем; атрибут называется 
GRANDTOTAL, а единственное скалярное значение в единственном результирующем 
кортеже является общим для всех значений атрибута QTY в исходном отношении SP. 
    Если, с другой стороны, исходное отношение SP не имеет кортежей совсем, то 
нет групп, а следовательно, нет и результирующих кортежей, т.е. результирующее 
отношение также будет пустым. Таким образом, операция SUMMARIZE имеет 
следующий (незначительный) недостаток: ее нельзя использовать для получения 
итога (например, с помощью функции COUNT) пустого множества. 

    SUMMARIZE SP BY ( S# ) ADD COUNT AS NP 

    2. 
    Результат этого примера будет таким: 

    S#           NP SI              6 S2             2 S3             1 S4     
         3 

    Как видите, результат не включает кортеж для поставщика S5 (с количеством 
поставляемых деталей, равным нулю) несмотря на то, что поставщик действительно 
поставляет ноль деталей. Причина, конечно, заключается в том, что поставщика 
S5 нет в отношении SP. Поэтому общий результат не совсем очевиден или, по 
    1 Как и в случае с оператором EXTEND, в системе должен быть определен 
домен для нового атрибута Z. И опять обсуждение этого вопроса (и многих 
связанных с ним) будет продолжено далее в этой книге. 

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

    крайней мере, его очевидность можно оспорить. (Конечно, вы уже видели 
способ получения аналогичного результата, включающего поставщика S5. Если вы 
его подзабыли, вернитесь и просмотрите примеры оператора EXTEND.) Заметьте, 
что для функции COUNT, в отличие от других итоговых функций, не требуется 
никаких аргументов. Строго говоря, функция COUNT не является необходимой, 
поскольку она эквивалентна зима). 
    3.   Рассмотрим запрос "Получить города, в которых хранится более пяти 
красных деталей": 

    ( ( SUMMARIZE ( P WHERE COLOR = 'Red' ) 
    BY { CITY ) ADD COUNT AS N ) WHERE N > 5 ) [ CITY ] 

    Теперь предположим, что мы изменили запрос следующим образом: "Получить 
города, в которых хранится пять красных деталей или меньше". Простая замена 
">" на "<" в предыдущем выражении 

    ( ( SUMMARIZE ( P WHERE COLOR = 'Red1 ) 
    BY ( CITY ) ADD COUNT AS N ) WHERE N < 5 ) [ CITY ] 

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

    Р   [  CITY ]   MINUS xyz 

    Здесь xyz — выражение, приведенное выше для первого запроса. 
    Замечание. Проблема, показанная в этом примере, в действительности не 
является проблемой самой операции SUMMARIZE: она вызвана тем фактом, что 
аргумент этой операции (выборка красных деталей отношения Р) уже исключает 
детали, которые имеют не красный цвет. Однако этот факт не делает результат 
более очевидным. 
    4.  И наконец, мы можем ввести сокращение для множественной операции 
подведения итогов, как показано в следующем примере (выше в этой главе 
приводились обсуждения множественного переименования и множественного расширения): 

    ( SUMMARIZE SP BY ( Р# ) ADD SUM ( QTY ) AS TOTQTY, 
    AVG ( QTY ) AS AVGQTY ) 

    В заключение отметим еще два немаловажных момента. 
    5.  В операции SUMMARIZE (как и в операции DIVIDEBY) возникают затруднения 
при использовании пустых отношений. К сожалению, пересмотренная форма этого 
оператора, в которой устранены проблемы с пустыми отношениями, значительно 
сложнее первоначального оператора. Эта форма описана в комментариях к [6.3]. 
    6.  Возможно, читатель понимает, что оператор SUMMARIZE не примитивен — 
его можно сымитировать с помощью оператора EXTEND (при этом будут 
использоваться определения итоговых функций; дальнейшее обсуждение по этому 
вопросу приводится в главе 7). Однако оператор SUMMARIZE часто требуется на 
практике и его введение вполне оправдано. 

    6.9. Операторы обновления 

    Реляционная модель (точнее, ее часть, связанная с операторами) кроме 
реляционной алгебры может включать также операции реляционного присвоения. 
Несколько примеров таких операций уже приводилось выше в этой главе при 
обсуждении пошаговой формулировки запроса (некоторые примеры также приводились 
и в предыдущих главах книги). Вот синтаксис этих операций: target := source ; 
    Здесь source и target— реляционные выражения, представляющие совместимые 
по типу отношения (на практике отношение target называется, как правило, 
базовым отношением). Вычисленное значение source присваивается отношению 
target, заменяя его старое значение. 

    Глава 6. Реляционные операторы: I. Реляционная алгебра	157 

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

    S  := S UNION { {   < S#	: 'S6'    >, 
    < SNAME	: 'Baker' >, 
    < STATUS :  50     >, 
    < CITY	: 'Madrid' > } } ; 
    SP := SP MINUS ( {    < S#	'SI' >, 
    < P#	'PI' >, 
    < QTY	300 >}} ; 

    С помощью первого присвоения в отношение S вставляется кортеж поставщика 
S6, а с помощью второго— из отношения SP удаляется кортеж поставки детали Р1 
поставщиком S1, И если таким способом удалось сымитировать операции INSERT и 
DELETE, то, конечно, можно сымитировать и операцию UPDATE, сначала удалив, а 
затем вставив нужный кортеж. (Между прочим, обратите внимание на литералы 
(обозначения) кортежей и отношений в этом примере. Такие литералы должны 
поддерживаться любой реальной реляционной системой.) 
    Однако использование таким способом операций UNION и MINUS вместо явных 
операций INSERT И DELETE H6 ВПОЛН6 удовлетворительно, ПОТОМу ЧТО ОПСрЗЦИИ 
UNION И MINUS 
    не позволяют должным образом обрабатывать ошибки, т.е. они допускают 
ситуации, которые воспринимаются операциями INSERT и DELETE как ошибки. В 
частности, при выполнении операции UNION не пресекается попытка вставки 
кортежа, дублирующего уже существующий, а при выполнении операции MINUS не 
отвергается удаление несуществующего кортежа. Поэтому на практике в 
реляционных системах существуют явные операции INSERT, DELETE и UPDATE. Ниже 
представлен синтаксис этих операций. 
    •   INSERT. Оператор вставки имеет следующий вид: 

    INSERT source INTO target ; 

    Здесь source и target — это реляционные выражения, представляющие 
совместимые по типу отношения (на практике отношение target является просто 
именованным отношением). Значение отношения source вычисляется, и все кортежи 
результата вставляются в отношение target. Пример: 

    INSERT ( S WHERE CITY = 'London' ) INTO TEMP ; 

    Здесь отношение TEMP совместимо по типу с отношением S. 
    •   UPDATE. Оператор обновления имеет следующий вид: 

    UPDATE target assignment-commalist ; 

    Каждое присвоение (assignment) имеет форму 
    attribute := scalar-expression 
    Здесь target— реляционное выражение, а каждый атрибут attribute 
принадлежит отношению, которое является результатом вычисления указанного 
выражения. Все кортежи в результирующем отношении обновляются в соответствии с 
указанными операторами присвоения. Например: 

    UPDATE P WHERE COLOR = 'Red' 
    CITY := 'Paris' ; 

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

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

    •  DELETE. Оператор удаления имеет следующий вид: 

    DELETE target ; 

    Здесь target — реляционное выражение; все кортежи в результирующем 
отношении удаляются. Например: 

    DELETE S WHERE STATUS < 20 ; 

    Как и в случае с оператором обновления, выражение target часто будет 
просто ограничивающим условием для некоторого именованного отношения, как в 
предложенном примере. 
    В дальнейшем изложении еще будут обсуждаться ситуации, когда выражение 
target сложнее, чем в приведенных примерах (это касается операций INSERT, 
DELETE и UPDATE и реляционных выражений вообще). Обратите особое внимание на 
то, что эти операции действуют на уровне множеств. Например, с помощью 
операции DELETE удаляется множество кортежей из целевого отношения. 
    К сожалению, мы часто говорим, например, об обновлении отдельного кортежа 
в отношении, но нужно ясно представлять, что: 
    1) на самом деле речь идет об обновлении множества кортежей в отношении 
(просто множество в данном случае имеет кардинальное число, равное единице); 
    2) иногда обновление множества кортежей с кардинальным числом один невозможно! 
    Предположим, например, что отношение поставщиков имеет целостное 
ограничение, в соответствии с которым поставщики S1 и S4 должны иметь 
одинаковый статус. Тогда любое обновление "на уровне кортежа" при попытке 
изменить статус одного из этих кортежей будет отвергнуто. Обновление обоих 
кортежей должно быть выполнено одновременно, как в следующем примере: 

    UPDATE S WHERE S# = 'SI1 OR S# = 'S4' STATUS := STATUS + 5 ; 


    Замечание о значении отношений 

    Как отмечалось в главе 4, каждое отношение имеет ассоциируемое с ним 
значение или предикат, и пользователи должны обращать внимание на эти 
предикаты, чтобы правильно использовать базу данных. Заметьте, что сказанное 
относится как к выборке данных, так и к их обновлению. Однако вопрос возникает 
прежде всего в связи с обновлением, поскольку, как объяснялось в главе 4, 
предикат — это критерий допустимости обновления для данного отношения, с 
помощью которого можно установить, например, будет ли корректной определенная 
операция обновления (как вы действительно убедились при обсуждении операций 
обновления в приведенном выше примере). 
    Предикаты для базовых отношений предполагаются известными — они содержат, 
главным образом, всякие ограничения целостности (например, ограничения 
потенциальных ключей, внешних ключей и, возможно, другие ограничения), 
предъявляемые к данному отношению. Ну а как же насчет производных отношений? 
Для этого, очевидно, нам нужен такой набор правил, которые позволяют 
установить предикат для результата произвольной реляционной операции, если 
известен предикат или предикаты для входных данных этой операции. 
    На самом деле очень просто определить такой набор правил — они 
непосредственно следуют из определений операций. Например, если А и В — два 
произвольных совместимых по типу отношения, а их соответствующие предикаты — 
РА и РВ, то предикат PC для выражения (назовем его С) A INTERSECT в будет, 
очевидно, (РЛ) AND (рв>; т.е. кортеж t будет принадлежать С, если и только 
если PA(t) — истина, и PB(f) — истина. Так, например, если мы определяем С как 
представление и пытаемся вставить кортеж t в это представление, то кортеж t 
должен удовлетворять предикату для А и предикату для В, иначе операция вставки 
не будет выполнена, (далее в этой книге мы еще вернемся к обсуждению 
обновлений представлений.) 

    Глава 6. Реляционные операторы: I. Реляционная алгебра	159 

    Вот еще один пример: предикат для отношения, являющегося результатом 
операции выборки 

    R WHERE condition 

    будет такой: (PR) то (condition), где PR — предикат для отношения R. 
    Формулировку    предикатов,    отвечающих    другим    операторам    
реляционной алгебры, оставляем в качестве упражнения для пользователя. 

    6.10. Реляционные сравнения 

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

    egression 9 egression 

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

    = (равно) 
    *• (не равно) 
    < (подмножество) 
    < (собственное подмножество) 
    > (надмножество) 
    > (собственное надмножество) 

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

    Приведем примеры. 

    1.  s [ CITY ] = Р [ CITY ] 
    Значение. Совпадает ли проекция отношения S по атрибуту CITY с проекцией 
отношения Р по атрибуту CITY? 
    2.  s [ s# j = SP [ s# ] 
    Значение (несколько перефразированное). Есть ли поставщики не поставляющие деталей? 
    Этот новый вид условия допустим для использования в операциях выборки 
(выборки в алгебраическом смысле).1 Например: 

    S WHERE ( ( SP RENAME S# AS X ) WHERE X = S# ) [ P# ] = P [ P# ] 

    При вычислении этого выражения получаем отношение, содержащее кортежи 
поставщиков, поставляющих все детали. 
    1 Однако обратите внимание, что новые условия не являются условиями 
выборки в терминах определения, данного выше в этой главе. На самом деле наши 
объяснения умышленно упрощены. В действительности необходимо сделать 
следующее. Вначале нужно сделать допустимыми атрибуты, значения которых 
являются отношениями (и это нужно сделать без нарушения требований 
нормализации!). Далее необходимо усовершенствовать оператор EXTEND так, чтобы 
он мог генерировать такие атрибуты. После этого можно использовать эти 
атрибуты для сравнения при выборке обычным образом. Более подробно этот вопрос 
будет обсуждаться в последующих главах книги. 

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

    Пояснения'. 
    •  Для данного поставщика выражение 

    (   (  SP RENAME S# AS X  )   WHERE X = S#  )    [  P#  ] 

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

    5 WHERE   ( MATCHING SP )    [  Р#  ]   = Р   [  Р#  ] 

    Еще несколько упрощений 
    На практике часто требуется определить, является ли данное отношение 
пустым (т.е. не содержащим ни одного кортежа). Поэтому имеет смысл ввести 
сокращение. Определим такую функцию, возвращающую логическое значение: 

    IS_EMPTY   (  expression ) 

    Эта функция возвращает истину, если вычисленное значение expression 
пустое, и ложь в противном случае. 
    Также часто требуется проверить, есть ли данный кортеж / в данном 
отношении R. Предположим, можно построить отношение, содержащее только один 
данный кортеж, заключив его в фигурные скобки; тогда нам подойдет следующее сравнение: 

    {   t }  < R 

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

    t IN R 

    Здесь IN заменяет оператор принадлежности, обычно обозначаемый е. 

    6.11. Резюме 

    Данная глава посвящается реляционной алгебре. В начале главы обсуждалась 
важность замкнутости и вложенных выражений; затем выяснилось, что при 
серьезном подходе к понятию замкнутости необходимы правила наследования имен 
атрибутов. Здесь же вскользь были упомянуты правила наследования потенциальных ключей. 
    Начальная алгебра состоит из восьми операций: набора традиционных операций 
объединения, пересечения, вычитания и произведения и набора специальных 
реляционных операций выборки, проекции, соединения и деления. К этому 
изначальному набору операций мы добавили операции RENAME (переименование), 
EXTEND (расширение) и SUMMARIZE (подведение итогов). Некоторые из этих 
операций требуют, чтобы два оператора были совместимы по типу (ранее такие 
отношения назывались "совместимыми для объединения"). Здесь же подчеркивалось, 
что эти операции не все примитивны (некоторые из них можно определить 
посредством других). Далее было показано, как эти операции можно комбинировать 
в выражения, используемые для выборки, обновления и др. Также кратко 
обсуждалась идея преобразования этих операций с целью оптимизации (подробнее 
эта идея будет обсуждаться далее в книге). Рассматривалась возможность 
пошагового подхода при выполнении сложных запросов. 
    Реляционная модель также включает в себя операцию реляционного присвоения, 
которую можно использовать в качестве основы для операций обновления. 
Отмечалось, что эти операции выполняются на уровне множеств и должны 
контролироваться с помощью предиката для рассматриваемого отношения. И 
наконец, обсуждалась идея реляционных сравнений, которые часто упрощают 
выражение запросов. 

    Глава 6. Реляционные операторы: I. Реляционная алгебра	161 
    6 Введение в системы баз данных 

    Упражнения 

    В первых упражнениях рассматриваются различные теоретические аспекты 
алгебры. В последующих упражнениях читателю предлагается сформулировать 
некоторые запросы в виде выражений реляционной алгебры. (Эти упражнения также 
можно решать и "наоборот": посмотреть алгебраическое выражение в ответе и по 
нему составить словесный запрос.) 
    6.1. Мы упоминали, что операции объединения, пересечения, произведения и 
(естественного) соединения обладают свойством коммутативности и 
ассоциативности. Проверьте эти утверждения. 
    6.2. Из первоначального набора восьми операций пять (объединение, 
вычитание, произведение, выборку и проекцию) можно рассматривать как 
примитивные. Дайте определения естественного соединения, пересечения и (что 
значительно сложнее) деления в терминах этих примитивных операций. 
    6.3. Рассмотрим выражение л JOIN я Если у отношений А и В заголовки 
разобщены (т.е. в заголовках нет общих атрибутов), то это выражение 
эквивалентно такому: л TIMES в. А какому выражению оно будет эквивалентно, 
если заголовки одинаковые! 
    6.4. Покажите, что пять примитивных операций, которые обсуждались в этой 
главе, действительно примитивны, т.е. что никакую из них нельзя выразить через 
четыре другие. 
    6.5. В обычной арифметике умножение и деление — взаимообратные операции. 
Будут ли операции TIMES и DIVIDEBY взаимообратными в реляционной алгебре? 
    6.6. Дана обычная база данных поставщиков и деталей; чему равно выражение 

    S JOIN SP JOIN P. 

    Предостережение. Здесь есть ловушка! 
    6.7. Пусть А — отношение степени п. Сколько существует различных проекций 
отношения А? 
    6.8. В обычной арифметике существует специальное число 1, обладающее свойством 

    n*l=l*n=n 

    для любого числа л. Мы говорим, что 1 является нейтральным элементом по 
отношению к операции умножения. Существует ли отношение, обладающее 
аналогичными свойствами единицы в реляционной алгебре? Если существует, то какое? 
    6.9. В обычной арифметике существует специальное число 0, обладающее свойством 

    л*0 = 0*п = 0 

    для любого числа п. Существует ли отношение, обладающее аналогичными 
свойствами нуля в реляционной алгебре? Если существует, то какое? 
    6.10. Выясните, как ведут себя алгебраические операции, описанные в этой 
главе, на отношениях, которые получаются в ответах к двум предыдущим упражнениям. 
    6.11. Пусть А и В — два произвольных отношения. Укажите потенциальные 
ключи для следующих отношений: 
    а) произвольная выборка А; 
    б) произвольная проекция А; 
    в) A TIMES в; 
    г) A UNION в; 

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

    Д) A INTERSECT BJ 
    е) A MINUS в; ж) A JOIN.в; 
    3) A DIVIDEBY В; 
    и) произвольное (по-разному) расширение А; к) произвольное подведение 
итогов в А. 
    Предполагается, что в каждом случае отношения А и В удовлетворяют 
необходимым для рассматриваемой операции условиям (например, для операции 
UNION они совместимы по типу). 
    6.12. Выше в этой главе мы говорили, что реляционное свойство замкнутости 
так же важно, как и арифметическое свойство замкнутости. Однако в арифметике 
существует одна неприятная ситуация, в которой нарушается свойство 
замкнутости, а именно деление на нуль. Существует ли аналогичная ситуация в 
реляционной алгебре? 

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

    В следующих упражнениях вам предлагается по словесному запросу к базе 
данных поставщиков и деталей составить соответствующее алгебраическое 
выражение или последовательность реляционных операций присвоения (на ваш 
выбор), необходимых для выполнения этого запроса. Если понадобится, можно 
также использовать реляционные сравнения. Для удобства ниже повторно 
приводится (в общих чертах) структура базы данных: 
    S        ( S#, SNAME, STATUS, CITY ) 
    PRIMARY FEY ( S# ) P ( P#, PNAME, COLOR, WEIGHT, CITY ) 
    PRIMARY KEY ( P# ) J ( J#, JNAME, CITY ) 
    PRIMARY KEY ( J# ) SPJ ( S#, P#, J#, OTY ) 
    PRIMARY KEY ( S#, P#, J# ) 
    FOREIGN KEY ( St ) REFERENCES S 
    FOREIGN KEY ( PI ) REFERENCES P 
    FOREIGN KEY ( J# ) REFERENCES J 
    6.13. Получить полную информацию обо всех проектах. 
    6.14. Получить полную информацию обо всех проектах в Лондоне. 
    6.15. Получить номера поставщиков, которые обеспечивают проект Л. 
    6.16. Получить все отправки, где количество находится в диапазоне от 300 
до 750 включительно. 
    6.17. Получить все сочетания "цвета деталей—города деталей". 
    Замечание. Здесь и в последующих упражнениях термин "все" используется в 
значении "все, представленные в настоящий момент в базе данных", а не "все возможные". 
    6.18. Получить все такие тройки "номера поставщиков-номера деталей-номера 
проектов", для которых выводимые поставщик, деталь и проект размещены в одном городе. 
    6.19. Получить все такие тройки "номера поставщиков-номера деталей-номера 
проектов", для которых выводимые поставщик, деталь и проект не размещены в 
одном городе. 

    Глава 6. Реляционные операторы: I. Реляционная алгебра	163 

    6.20. Получить все такие тройки "номера поставщиков-номера деталей-номера 
проектов", для которых никакие из двух выводимых поставщиков, деталей и 
проектов не размещены в одном городе. 
    6.21. Получить номера деталей, поставляемых поставщиком в Лондоне. 
    6.22. Получить номера деталей, поставляемых поставщиком в Лондоне для 
проекта в Лондоне. 
    6.23. Получить все пары названий городов, для которых поставщик из первого 
города обеспечивает проект во втором городе. 
    6.24. Получить номера деталей, поставляемых для всех проектов, 
обеспечиваемых поставщиком из того же города, где размещен проект. 
    6.25. Получить номера проектов, обеспечиваемых по крайней мере одним 
поставщиком не из того же города. 
    6.26. Получить все такие пары номеров деталей, которые обе поставляются 
одновременно одним поставщиком. 
    6.27. Получить общее число проектов, обеспечиваемых поставщиком S1. 
    6.28. Получить общее количество деталей Р1, поставляемых поставщиком S1. 
    6.29. Для каждой детали, поставляемой для проекта, получить номер детали, 
номер проекта и соответствующее общее количество. 
    6.30. Получить номера деталей, поставляемых для некоторого проекта со 
средним количеством больше 320. 
    6.31. Получить имена проектов, обеспечиваемых поставщиком S1. 
    6.32. Получить цвета деталей, поставляемых поставщиком S1. 
    6.33. Получить номера деталей, поставляемых для какого-либо проекта в Лондоне. 
    6.34. Получить номера проектов, использующих по крайней мере одну деталь, 
имеющуюся у поставщика S1. 
    6.35. Получить номера поставщиков, поставляющих по крайней мере одну 
деталь, поставляемую по крайней мере одним поставщиком, который поставляет по 
крайней мере одну красную деталь. 
    6.36. Получить номера поставщиков со статусом, меньшим чем у поставщика S1. 
    6.37. Получить номера проектов, город которых стоит первым в алфавитном 
списке городов. 
    6.38. Получить номера проектов, для которых среднее количество 
поставляемых деталей Р1 больше, чем наибольшее количество любых деталей, 
поставляемых для проекта J1. 
    6.39. Получить номера поставщиков, поставляющих деталь Р1 для некоторого 
проекта в количестве, большем среднего количества деталей Р1 в поставках для 
этого проекта. 
    6.40. Получить номера проектов, для которых не поставляются красные детали 
поставщиками из Лондона. 
    6.41. Получить номера проектов, полностью обеспечиваемых поставщиком S1. 
    6.42. Получить номера деталей, поставляемых для лондонских проектов. 
    6.43. Получить номера поставщиков, поставляющих одну и ту же деталь для 
всех проектов. 
    6.44. Получить номера проектов, обеспечиваемых по крайней мере всеми 
деталями поставщика S1. 
    6.45. Получить все города, в которых расположен по крайней мере один 
поставщик, одна деталь или один проект. 

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

    6.46. Получить номера деталей, поставляемых либо лондонским поставщиком, 
либо для лондонского проекта. 
    6.47. Получить пары "номер поставщика-номер детали", такие, что данный 
поставщик не поставляет данную деталь. 
    6.48. Получить все пары номеров поставщиков, скажем, Sx и Sy, такие, что 
оба эти поставщика поставляют в точности одно и то же множество деталей. 
(Выражаю благодарность г-ну Фатма Мили (Fauna Mill) из Окландовского 
Университета (Рочестер, Мичиган), предложившему эту задачу.) 

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

    6.1. Codd E.F. A Relational Model of Data for Large Shared Data Banks // 
CACM. — 1970. — 13, № 6. (Переиздано: Milestones of Research — Selected Papers 
1958-1982 (CACM 25th Anniversary Issue) // CACM. — 1983. — 26, № 1.) 
    Первая статья Кодда о реляционной модели, в которой даны определения 
алгебраических операций, перечисленных ниже. Интересно отметить, что 
определения выборки и соединения отличались от современных определений, а 
список операций включал операции связи и композиции, которые в настоящее время 
редко используются. Далее предполагается, что X, Y и т.д. представляют 
атрибуты или при необходимости сочетание атрибутов. 
    • Операция перестановки— переупорядочение атрибутов отношения слева 
направо; эта операция предназначалась для использования исключительно на 
внутреннем уровне системы, поэтому, естественно, такое упорядочение атрибутов 
не ёимеет никакого отношения к пользователю. 
    • Операция выборки— для данных отношений А{Х, Y} и B{Y] выборка из 
отношения А по В определяется как такое максимальное подмножество отношения А, 
что A[Y] будет подмножеством (не обязательно собственным подмножеством) 
отношения В. 
    • Операция проекции более или менее соответствует сегодняшнему представлению. 
    • Несколько видов операции соединения (рассматриваются ниже). 
    • Операция связи — дано отношение А{Х1,Х2,... ,Хп}, связью отношения А 
будет выборка кортежей отношения А, для которых Л[Ли]=Л[Л7] — выборка в том 
смысле, в каком этот термин использовался в данной главе, а не в смысле 
приведенного выше определения. 
    • Операция композиции— для данных отношений А{Х, Y} и B{Y, Z} композиция 
отношений А к В представляет собой проекцию по множеству атрибутов {X, Z} 
некоторого соединения отношения А с отношением В по атрибуту Y. 
    Уточним некоторые вопросы относительно операции соединения. Даны отношения 
А{Х, Y} и B{Y, Z}, в статье соединение отношений А и В определяется как 
отношение С{Х, Y,Z}, такое, что С[Х, Y]=A и C[Y,Z\=B. Естественное соединение 
(называемое в статье линейным естественным соединением для того, чтобы 
отличать его от другого вида соединения, называемого в статье циклическим 
соединением) — это важный частный случай, и он в общем не является единственно 
возможным. Заметьте, что 0-соединения (в отличие от "линейных" соединений), 
т.е. соединения, в которых используются операторы скалярного сравнения, 
отличные от оператора "равно", не рассматриваются. 
    6.2. Codd E.F. Relational Completeness of Data Base Sublanguages // Data 
Base Systems, Courant Computer Science Symposia Series 6. — Englewood Cliffs, 
N.J.: Prentice-Hall, 1972. 

    Глава 6. Реляционные операторы: I. Реляционная алгебра 165 

    Статья включает формальное определение исходной версии реляционной 
алгебры, которая близка к версии, рассмотренной в настоящей главе. Определены 
операторы объединения, пересечения, вычитания, расширения, декартова 
произведения, проекции, 9-соединения (и естественного соединения), деления и 
6-выборки. Ниже приведены принципиальные различия в определениях статьи и 
рассмотренной в этой главе версии. 
    • Операция проекции: в статье для данного атрибута исходного отношения 
допускается любое число вхождений в результирующее отношение (а не 
ограничивается одним вхождением). 
    • Операция выборки: в статье допускается произвольное скалярное сравнение 
двух значений атрибутов (в более общем случае — двух подкортежей) данного 
кортежа, но не разрешается сравнение значения атрибута такого кортежа с литералом. 
    • Наименование атрибута: вопрос об именах атрибутов результирующего 
отношения в статье не обсуждается совсем. Предполагается, что атрибуты 
отношения упорядочены слева направо и, следовательно, могут быть 
идентифицированы по их порядковому номеру в соответствии с расположением. 
    •Дополнительные  сведения: в статье не обсуждаются операции EXTEND, 
SUMMARIZE, реляционные сравнения и операции обновления. 
    6.3. Darwen H. Private communication. — 1992. 
    Предлагается обобщенная версия операции SUMMARIZE, которая решает 
определенные проблемы, рассмотренные в этой главе. Основная идея заключается в 
замене заключенного в круглые скобки списка атрибутов в операторе BY 
реляционным выражением 

    SUMMARIZE term BY relational-expression 
    ADD aggregate-expression AS attribute Например: 
    SUMMARIZE SP BY S   [  S#  ]   ADD COUNT AS NP 

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

    SUMMARIZE A BY В ADD ехр AS  Z 

    определяется следующим образом: 
    • Отношение В должно быть совместимо по типу с некоторой проекцией 
отношения А, т.е. каждый атрибут отношения В должен быть атрибутом отношения 
А. Пусть атрибутами такой проекции будут AI, A2,..., An. 
    • Заголовок результата содержит все атрибуты отношения В плюс новый 
атрибут Z. 
    • Заголовок результата содержит все такие кортежи (, которые являются 
кортежами отношения В, расширенного значением для нового атрибута Z; это новое 
значение атрибута Z подсчитывается вычислением итогового выражения ехр по всем 
кортежам отношения А, которые имеют те же самые значения для атрибутов Al, 
A2,..., An, что и кортеж t. 
    Основное различие между пересмотренным оператором SUMMARIZE и версией, 
описанной выше в этой главе, состоит в том, что результат имеет то же самое 
кардинальное число, что и отношение В. Но тогда возможны следующие ситуации: 
    • Если множество всех кортежей отношения А, которые имеют те же самые 
значения для атрибутов А1,А2,... ,Ап, что и кортеж /, пустое, то итоговое 
выражение ехр будет применяться к пустому множеству значений. Как уже 
указывалось в этой главе, для функций COUNT и SUM результат будет равен ну

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

    лю. Для функции МАХ он будет равен "минус бесконечности" (где "минус 
бесконечность" — это наименьшее значение в соответствующем домене). Для 
функции MIN он будет равен "плюс бесконечности" (определяется аналогично). Для 
функции AVG будет возникать исключительная ситуация. 
    • Если отношение В не просто совместимо по типу с некоторой проекцией 
отношения А, а фактически является такой проекцией, как в примере 

    SUMMARIZE SP BY SP [ S# ] ADD COUNT AS NP 

    то мы фактически возвращаемся к первоначальному оператору SUMMARIZE. 
    В частности, обратите внимание, что с этой пересмотренной формой оператора 
SUMMARIZE операция 

    SUMMARIZE SP BY TABLE_DEE ADD SUM ( QTY ) AS GRANDTOTAL 

    будет выполняться, т.е. возвращать корректный ответ, а именно нуль, даже 
если отношение SP будет пустым (сравните ситуацию с оператором SUMMARIZE, 
описанную в настоящей главе). См. главу 4, где обсуждается отношение TABLE_DEE. 
    6.4. Darwen H., Date C.J. Into the Great Divide // C.J. Date and Hugh 
Darwen. Relational Database Writings 1989-1991. — Reading, Mass.: 
Addison-Wesley, 1992. 
    Оператор деления, как определено выше в этой главе, применяется к делимому 
отношению и отношению-делителю, которые удовлетворяют следующему требованию: 
заголовок делителя является собственным подмножеством отношения делимого. В 
этой статье (благодаря Стефану Тодду) обсуждается обобщение оператора деления, 
который применяется к любой паре какого бы то ни было отношения. Такой 
оператор определяется следующим образом. Для данных отношений А{X, Y} и B{Y, 
Z} выражение 

    A DIVIDEBY В 

    дает отношение с заголовком {X, 2} и телом, состоящим из всех кортежей 
{Х:х, Z:z}, таких что кортеж {Х:х, Y:y} содержится в отношении А для всех 
кортежей { Y:y, Z:z}, содержащихся в отношении В. Предположим, например, что у 
нас есть два отношения (SP{S#, P#} и PJ{P#, J#}), где SP показывает, какими 
поставщиками какие детали поставляются, a PJ показывает, какие детали в каком 
проекте используются. Тогда выражение 

    SP DIVIDEBY PJ 

    дает отношение с заголовком {S#, J#}, показывающее такие пары номеров 
поставщиков и номеров проектов, в которых указанный поставщик поставляет все 
детали, используемые в указанном проекте. Более того, выражение 

    PJ DIVIDEBY SP 

    дает отношение с заголовком {J#, S#}, показывающее такие пары номеров 
проектов и номеров поставщиков, в которых указанный проект использует все 
детали, поставляемые указанным поставщиком. 
    По крайней мере, так было задумано. В статье показано, что ни 
первоначальная версия операции деления Кодда, ни обобщенная версия Тодда не 
дают полного решения проблемы (данные выше описания двух выражений DIVIDEBY 
нельзя назвать исчерпывающими). В статье также показано, что деление Тодда не 
является в полной мере совместимым дополнением деления Кодда; более того, если 
эти операторы усовершенствовать так, чтобы они могли решать поставленные 
задачи, то их нельзя будет назвать операторами "деления"! 
    Чтобы разобраться, почему оператор DIVIDEBY полностью не решает проблему, 
для решения которой он предназначался, давайте возвратимся к первоначальной 
версии оператора, предложенной Коддом. Рассмотрим запрос 

    Глава 6. Реляционные операторы: I. Реляционная алгебра	167 

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

    SP   [ S#,   Р#  ]   DIVIDEBY РР   [  Р#  ] 

    Теперь предположим (и это действительно соответствует нашим примерным 
данным), что фиолетовых деталей нет и отношение РР пустое, а значит, будет 
пустой и проекция этого отношения по атрибуту Р#. Но, если фиолетовых деталей 
нет, значит, каждый поставщик поставляет их все — даже поставщик S5 в наших 
примерных данных, не поставляющий деталей вообще! А поставщики, не 
поставляющие деталей, не представлены в отношении SP, значит, получить 
результат, включающий таких поставщиков, с помощью операции DIVIDEBY невозможно. 
    Эту проблему можно решить, определив новый оператор "деления по". Пусть 
отношения А, А В и В имеют соответственно заголовки {X}, {X, Y} и {?}. Тогда 
частным деления А на В по АВ (оператор A DIVIDEBY в PER AB) будет отношение с 
заголовком {X} и телом, состоящим из всех кортежей {Х:х}, таких что кортеж 
{Х:х, Y:y} принадлежит АВ для всех кортежей {У:у}, принадлежащих В, или в 
сокращенной форме: 

    А.Х WHERE FORALL В EXISTS АВ ( А.Х = АВ.Х AND АВ. Y = B.Y ) 

    (операторы FORALL и EXISTS разъясняются в главе 7). Теперь запрос 
"Получить номера поставщиков, которые поставляют все фиолетовые детали" можно 
выразить просто (и корректно): 

    S   [  S#  ]   DIVIDEBY РР   [  Р#   ]   PER SP   [  S#,   P#  ] 

    Таким образом решается проблема операции деления, предложенной Коддом. 
Решение проблемы деления по версии Тодда аналогично. 
    Замечание. Очевидно, можно было бы расширить определение оператора 
"деления по", чтобы заголовки могли быть надмножествами {X}, {X, Y} и {У} 
соответственно. Однако здесь это обсуждаться не будет. 
    6.5. Goldstein R.C., Strnad A.J. The MacAIMS Data Management System // 
Proc. 1970 ACM SICFIDET Workshop on Data Description and Access. — 1970. 
    6.6. Strnad A.J. The Relational Approach to the Management of Data Bases 
// Proc. IFIP Congress. — Ljubljana, Yugoslavia, 1971. 
    Система MacAIMS [6.5, 6.6] — один из самых ранних примеров системы, 
поддерживающей «-арные отношения и языки уровня множеств. Она использует 
алгебраический язык и обладает двумя весьма интересными особенностями. 
    • Структура хранения может быть разной для хранимых отношений. Каждый тип 
структуры управляется компонентом, называемым "модулем реляционной стратегии", 
специальным для такой структуры, которая скрывает детали хранения от других 
частей системы (и конечно, от пользователя). 
    • Атрибуты хранились как "множества элементов данных". Каждому элементу 
данных (т.е. значению атрибута) присваивается уникальный ссылочный номер, а 
все ссылки к элементам данных внутри отношения осуществляются через ссылочный 
номер. Алгоритм присвоения ссылочных номеров следующий: если а и Ь принадлежат 
одному и тому же множеству элементов данных, тогда ссылочный номер для а будет 
больше для Ь, если и только если а больше, чем Ь. Вследствие этого любая 
операция сравнения между двумя элементами данных (из того же самого множества 
элементов данных) может быть выполнена непосредственно на соответствующих 
ссылочных номерах; кроме того, само реальное сравнение, вероятно, более эф

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

    фективно, поскольку ссылки имеют фиксированную длину, в то время как 
элементы данных могут иметь и переменную длину. Этот момент особенно важен с 
учетом того, что такие сравнения являются операциями, которые, наверняка, 
наиболее часто выполняются внутри этой системы (как, вероятно, и во всякой 
системе баз данных). 
    6.7. Notley M.G. Peterlee IS/1 System // IBM (UK) Scientific Centre Report 
UKSC-0018.— 1972. 
    См. комментарии к [6.8]. 
    6.8. Todd S.J.P. The Peterlee Relational Test Vehicle — A System Overview 
// IBM Sys. J. — 1976. — 15, №4. 
    Peterlee Relational Test Vehicle (PRTV) — это экспериментальная система, 
разработанная в научном центре IBM UK, Петерли, Англия. Она была разработана 
на основе более ранней системы IS/I [6.7]. В ней поддерживались «-арные 
отношения и версия алгебры под названием ISBL (Information System Base 
Language — базовый язык информационных систем). Эта версия алгебры 
основывалась на предложениях, изложенных в [6.9]. Идеи, изложенные в этой 
главе относительно результирующих имен атрибутов и операторов, основанных на 
согласованных именах атрибутов, идут еще от алгебры ISBL и предложений статьи 
[6.9]. Система PRTV обладала тремя важными свойствами. 
    • В ней были реализованы сложные методы преобразования выражений (это еще 
будет обсуждаться далее в этой книге). 
    • Она включала средство отложенного вычисления, что важно как для 
оптимизации, так и для поддержки именованных виртуальных отношений (т.е. представлений). 
    • Она обеспечивала "функцию расширяемости", т.е. возможность расширять 
систему, добавляя определенные пользователем вычислительные функции. 
    6.9. Hall P.A.V., Hitchcock P., Todd S.J.P. An Algebra of Relations for 
Machine Computation // Conference Record of the 2nd ACM Symposium on 
Principles of Programming Languages. — Palo Alto, Calif, 1975. 
    6.10. Furtado A.L., Kerschberg L. An Algebra of Quotient Relations // 
Proc. 1977 ACM SIGMOD Intern. Conf. on Management of Data. — Toronto, Canada, 1977. 
    Представлена пересмотренная версия реляционной алгебры для оперирования 
непосредственно с "относительными отношениями" ("quotient relations"). Дано 
отношение R, относительное отношение можно получить из отношения R путем 
группировки его кортежей на основе некоторого его атрибута (так же, как в 
операторе BY операции SUMMERIZE, описанной в этой главе). Например, 
относительное отношение, полученное из отношения поставщиков S на основе 
значений атрибута CITY — это множество из трех групп кортежей: в одной 
содержатся два кортежа поставщиков из Лондона, в другой — два кортежа 
поставщиков из Парижа, в третьей — один кортеж поставщика из Атена. Авторы 
утверждают, что работа непосредственно с такими относительными отношениями 
приводит к упрощению формулировок запросов и потенциально к более эффективной 
реализации системы. 
    6.11. Merrert Т.Н. The Extended Relational Algebra, A Basis for Query 
Languages // B. Shneiderman (ed.). Databases: Improving Usability and 
Responsiveness. — New York, N.Y.: Academic Press, 1978. 
    Целью этой статьи является введение кванторов в алгебру — не просто 
исчисления кванторов существования и кванторов всеобщности (об этом в главе 
7), а более общих кванторов "количество" и "соотношение". С помощью этих 
кванторов можно выразить такие условия, как "по крайней мере три", "не более 
половины", "нечетное число" и т.д. 

    Глава 6. Реляционные операторы: I. Реляционная алгебра	169 

    6.12. Hall P.A.V. Relational Algebra, Logic and Functional Programming // 
Proc, 1984 ACM SIGMOD Intern. Conf. on Management of Data. — Boston, Mass., 1984. 
    В статье представлена функциональная интерпретация реляционной алгебры с 
целью (как говорится в статье) изложить теоретические основы так называемых 
"языков четвертого поколения" (4GL) и интегрировать функциональные, логические 
и реляционные языки таким образом, чтобы они могли совместно использовать 
технологию реализации. Автор утверждает, что, хотя логическое программирование 
и базы данных уже на протяжении некоторого времени сближаются друг с другом, 
во время написания функциональных или аппликативных языков мало обращается 
внимания на требования баз данных или технологии. Поэтому статья главным 
образом вносит вклад в сближение между ними. 
    6.13. Klug A.  Equivalence of Relational Algebra and Relational Calculus 
Query Languages Having Aggregate Functions // JACM. — 1982. — 29, № 3. 
    В статье определяется множество расширений реляционной алгебры и 
реляционного исчисления для включения поддержки итоговых функций (для алгебры 
это нечто подобное оператору SUMMARIZE, описанному выше в этой главе) и 
демонстрируется равносильность двух расширенных языков. 

    Ответы к некоторым упражнениям 

    6.2. Операция соединения JOIN уже рассматривалась выше в этой главе. 
Операция пересечения INTERSECT может быть определена так: 

    A INTERSECT В в A MENUS   (Л MINUS В ) ИЛИ 
    Л INTERSECT В s В MINUS   (В MINUS A ) 

    Эти два равносильных выражения хотя и допустимы, но несколько 
неудовлетворительны, поскольку A INTERSECT в— симметричное выражение 
относительно А и В, а остальные два выражения не симметричны. А вот для 
сравнения симметричный вариант: 

    ( A MINUS ( Л MINUS В ) ) UNICN ( В MINUS ( В MINUS Л ) ) 

    Замечание. Если дано, что отношения А и В совместимы по типу, то 

    Л INTERSECT В з Л JOIN В 

    Теперь о делении. Пусть А, В, Хи Y— обозначения, введенные нами при 
обсуждении операции DIVIDEBY выше в этой главе. Тогда 

    Л DIVIDEBY В = Л [ X ] MINUS 
    ( ( Л [ X ] TIMES В ) MINUS Л ) [ X } 

    Отметим, что поскольку операцию JOIN можно определить в терминах операции 
TIMES и операция TIMES является частным случаем операции JOIN, то операцию 
JOIN можно рассматривать как примитивную вместо операции TIMES. 
    Отметим также, что, если разрешено использовать дополнения отношений, мы 
бы могли рассматривать операции UNION и INTERSECT как примитивные и определить 
операцию MINUS через них. Обозначим NOT (R) как дополнение к отношению R, т.е. 
множество всех возможных кортежей, которые совместимы по типу с отношением R, 
но не принадлежат ему. Тогда: 

    Л MINUS В s NOT ( ( NOT ( Л ) ) UNION { Л INTERSECT В ) ) 

    6.3. л INTERSECT в (см. выше ответ к упр. 6.2). 
    6.4. Мы даем только интуитивное "доказательство". 

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

    • Произведение — это единственный оператор, увеличивающий количество 
атрибутов, а значит, его нельзя сымитировать любыми другими операторами. 
Поэтому произведение — примитивная операция. 
    • Проекция — это единственный оператор, уменьшающий количество атрибутов, 
а значит, его нельзя сымитировать любыми другими операторами. Поэтому проекция 
— примитивная операция. 
    • Объединение — единственный оператор, увеличивающий количество кортежей, 
кроме произведения, но произведение, кроме этого, также увеличивает количество 
атрибутов. Пусть отношения АиВ должны быть объединены. Обратите внимание, что 
отношения А и В должны быть совместимы по типу и в их объединении должны быть 
те же самые атрибуты, что и в них самих. Если мы образуем произведение 
отношений А и В, а затем используем проекцию, чтобы уменьшить множество 
атрибутов в произведении до множества атрибутов в отношении А (или В), мы 
просто снова вернемся к исходному отношению А (или В). Следовательно, 
произведение не может быть использовано для моделирования операции 
объединения, а значит, операция объединения примитивна. 
    • Вычитание не может быть смоделировано через произведение (поскольку 
операция произведения увеличивает количество кортежей), через объединение 
(аналогично) или через проекцию (поскольку проекция сокращает количество 
атрибутов). Также оно не может быть смоделировано с помощью выборки, поскольку 
вычитание реагирует на значения во втором отношении, которого не может быть 
при выборке (в силу природы условия выборки). Следовательно, операция 
вычитания также примитивна. 
    • Выборка является единственной операцией, которая позволяет сравнивать 
значения атрибутов с определенными литералами (т.е. значениями, которые не 
являются частью какого-либо отношения). Следовательно, операция выборки также примитивна. 
    6.5. Не совсем. Оператор DIVIDEBY, возможно, больше похож на целочисленное 
деление в обычной арифметике (т.е. он игнорирует остаток). Пусть заданы два 
отношения А т В, тогда формирование декартова произведения отношений А и В и 
затем деления результата отношением В даст нам снова отношение А: 

    (  A TIMES В )   DIVIDEBY В = А 

    Однако деление отношения А отношением В и затем формирование декартова 
произведения результата с отношением В даст отношение, которое может быть 
идентично отношению А, но более вероятно, что оно будет некоторым собственным 
подмножеством отношения А: 

    (  A DIVIDEBY В )   TIMES В < А 

    Давайте условимся последнее обстоятельство в данный момент считать 
"псевдообратным свойством". Тогда можно сказать, что результат деления 
отношения А отношением В является таким максимальным подмножеством проекции 
А[Х] (где X— это множество общих атрибутов в отношениях А и В), что 
сохраняется псевдообратное свойство. 
    Отметим, что аналогичное свойство не сохраняется для операции DIVIDEBY 
PER, описанной в [6.4]. 
    6.6. Ловушка заключается в том, что операция JOIN использует атрибуты CITY 
так же, как и атрибуты S# и Р# (в силу нашего определения оператора JOIN). 
Результат будет подобен следующему: 

    Глава 6. Реляционные операторы: I. Реляционная алгебра	171 

    s#	SNAME	STATUS	CITY	P#	QTY	PNAME	COLOR	WEIGHT 
    SI	Smith	20	London	PI	300	Nut	Red	12 
    SI	Smith	20	London	P4	200	Screw	Red	14 
    SI	Smith	20	London	P6	100	Cog	Red	19 
    S2	Jones	10	Paris	P2	400	Bolt	Green	17 
    S3	Black	30	Paris	P2	200	Bolt	Green	17 
    S4	Clark	20	London	P4	200	Screw	Red	14 

    6.7. 2". Это количество включает идентичную проекцию (т.е. проекцию по 
всем п атрибутам, которая дает результат, идентичный исходному отношению А) и 
"нулевую" проекцию (т.е. проекцию по никаким атрибутам совсем, которая дает в 
результате TABLE_DUM, если исходное отношение А пустое, и TABLE_DEE в 
противном случае). 
    6.8. Да, есть такое отношение, а именно TABLE_DEE. Отношение TABLE_DEE 
(далее для краткости DEE) — аналог номер один по отношению к умножению в 
обычной арифметике, поскольку 

    R TIMES DEE = DEE TIMES R = R 

    для всех отношений R. Иначе говоря, DEE — это нейтральный элемент для 
операции TIMES (и конечно, для операции JOIN). 
    6.9. Не существует отношения, ведущего себя относительно операции TIMES в 
точности аналогично нулю относительно умножения. Однако поведение отношения 
TABLE_DUM (или сокращенно DUM) несколько сходно с поведением нуля, так как для 
всех отношений R 

    R TIMES DUM = DUM TIMES R = пустое отношение с тем ЖЕ 

    самым заголовком, что и у R 
    6.10. Отношениями, которые совместимы с DEE и DUM при объединении, 
пересечении и вычитании, являются сами отношения DEE и DUM. В результате мы имеем: 

    UNION	DEE	DUM 
    DEE	DEE	DEE 
    DUM	DEE	DUM 
    INTERSECT	DEE	DUM 
    DEE	DEE	DUM 
    DUM	DUM	DUM 
    MINUS	DEE	DUM 
    DEE	DUM	DEE 
    DUM	DUM	DUM 

    В случае вычитания первый операнд показан слева в таблице, а второй вверху 
таблицы (для других операторов, конечно, операнды могут меняться между собой). 
Обратите внимание, как это напоминает таблицы истинности для логических 
операций ИЛИ, И, И НЕ соответственно; конечно, такое совпадение не случайно. 
Рассмотрев затем выборку и проекцию, мы получим: 
    • Любая выборка из отношения DEE дает отношение DEE, если значение условия 
выборки равно истине, и DUM, если оно равно лжи. 
    • Любая выборка из отношения DUM дает отношение DUM. 
    • Проекция любого отношения по пустому множеству атрибутов дает отношение 
DUM, если исходное отношение пустое, и отношение DEE в противном случае. В 
частности, проекция отношения DEE или отношения DUM, обязательно по пустому 
множеству атрибутов, возвращает исходное отношение. 
    В следующих замечаниях по делению подразумевается обобщенная форма 
оператора деления Тодда, которая рассматривается в [6.4]. 
    • Любое отношение R, делимое отношением DEE, в результате дает отношение R. 
    • Любое отношение R, делимое отношением DUM, в результате дает пустое 
отношение с тем же заголовком, что и у отношения R. 

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

    • Отношение DEE, делимое любым отношением R, в результате дает отношение R. 
    • Отношение DUM, делимое любым отношением R, в результате дает пустое 
отношение с тем же заголовком, что и у отношения R. 
    • Любое непустое отношение, делимое на себя, в результате дает отношение 
DEE. Пустое отношение, делимое на себя, в результате дает отношение DUM. 

    Операции расширения и суммирования: 

    • Расширение отношения DEE или отношения DUM для добавления новых 
атрибутов дает отношение с одним атрибутом и тем же количеством кортежей, что 
и в исходном отношении. 
    • Суммирование отношения DEE или отношения DUM (обязательно по пустому 
множеству атрибутов) дает отношение с одним атрибутом и тем же количеством 
кортежей, что и в исходном отношении. 
    6.11. Здесь мы имеем дело, конечно, с "не зависимыми от времени" 
потенциальными ключами. Имея в виду это предостережение, мы предлагаем в 
качестве "первого эскиза" множества ответов следующее: 
    а) любая выборка из отношения А наследует все потенциальные ключи 
отношения Л; 
    б) если проекция включает любой из потенциальных ключей К отношения А, то 
К — потенциальный ключ проекции. В противном случае потенциальным ключом 
является комбинация всех атрибутов проекции; 
    в) каждая комбинация К потенциального ключа КА отношения А и 
потенциального ключа KB отношения В является потенциальным ключом произведения 
A TIMES Б, 
    г) потенциальным ключом объединения A UNION в является комбинация всех атрибутов; 
    д) оставлено в качестве упражнения для читателя (пересечение — не 
примитивная операция); 
    е) каждый потенциальный ключ отношения А является потенциальным ключом для 
результата вычитания A MINUS я, 
    ж) мы оставляем общий случай в качестве упражнения для читателя 
(естественное соединение — не примитивная операция). Однако заметим, что в 
частном случае, где соединяющий атрибут в отношении А является потенциальным 
ключом А, каждый потенциальный ключ отношения В является потенциальным ключом соединения; 
    з) оставлено в качестве упражнения для читателя (деление — не примитивная операция); 
    и) каждый потенциальный ключ отношения А является и потенциальным ключом 
для произвольного расширения А; 
    к) потенциальным ключом для операции подведения итогов отношения А 
является множество атрибутов, определенных в операторе BY. 
    Однако большинство упомянутых операторов в определенных ситуациях можно 
некоторым образом усовершенствовать. Например: 
    • Сочетание атрибутов {S#, P#, J#} не является потенциальным ключом для 
выборки SPJ WHERE s# = 'si1; им является сочетание (Р#, J#}. 
    • Если отношение А, имеющее заголовок {X, Y, Z} и единственный 
потенциальный ключ X, удовлетворяет "функциональной зависимости" Y -» Z (эти 
обозначения описываются в главе 9), то Y является потенциальным ключом 
проекции отношения А по атрибутам Y и Z. 

    Глава 6. Реляционные операторы: I. Реляционная алгебра	173 

    • Если отношение А и отношение В оба являются выборкой из отношения С, то 
каждый потенциальный ключ отношения С является потенциальным ключом 
объединения л UNION в. 
    И т.д. Более подробно вопрос о наследовании потенциальных ключей 
обсуждается далее в книге. 
    6.12. Нет! 
    6.13. а 
    6.14. J WHERE CITY = 'London1 
    6.15. ( SPJ WHERE J# = 'Jl1 ) [ S# ] 
    6.16. SPJ WHERE QTY > 300 AND QTY < 750 
    6.17. P [ COLOR, CITY ] 
    6.18. ( S JOIN P JOIN J ) [ S#, P#, J# ] 
    6.19. ( ( ( S RENAME CITY AS SCITY ) TIMES ( P RENAME CITY AS PCITY ) 
TIMES ( J RENAME CITY AS JCITY ) ) WHERE SCITY # PCITY OR PCITY Ф JCITY OR 
JCITY Ф SCITY ) [ S#, P#, J# ] 
    6.20. ( ( ( S RENAME CITY AS SCITY ) TIMES ( P RENAME CITY AS PCITY ) 
TIMES ( J RENAME CITY AS JCITY ) ) WHERE SCITY Ф PCITY AND PCITY * JCITY AND 
JCITY * SCITY } [ S#, P#, J# ] 
    6.21. ( SPJ JOIN ( S WHERE CITY = 'London' ) } [ P# ] 
    6.22. (( SPJ JOIN ( S WHERE CITY = 'London')) [ P#, J# ] 
    JOIN ( J WHERE CITY = 'London' ) ) [ P# ] 
    6.23. ( ( S RENAME CITY AS SCITY ) JOIN SPJ JOIN 
    ( J RENAME CITY AS JCITY) ) [SCITY, JCITY ] 
    6.24. ( J JOIN SPJ JOIN S ) [P# ] 
    6.25. ( ( ( J RENAME CITY AS JCITY ) JOIN SPJ JOIN ( S RENAME CITY AS 
SCITY ) ) 
    WHERE JCITY * SCITY ) [ J# ] 
    6.26. ( ( ( SPJ [ S#, P# ] RENAME S# AS XS#, P# AS XP# ) ) TIMES 
    ( ( SPJ [ S#, P# ] RENAME S# AS YS#, P# AS YP# ) ) ) WHERE XS# = YS# AND  
XP# < YP# ) [ XP#, YP# ] 
    6.27. ( SUMMARIZE ( ( SPJ WHERE S# = 'SI' ) [ J# ] ) BY () 
    ADD COUNT AS N ) [ N ] 
    Как уже отмечалось, это выражение, к сожалению, не будет возвращать нуль 
(точнее, отношение из одного атрибута и одного кортежа, содержащего числовое 
значение нуль), если поставщик S1 не обеспечивает проектов; вместо этого 
выражение возвратит пустое отношение. Поэтому мы предлагаем следующее более 
точное решение: 

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

    ( EXTEND ( S WHERE S# = 'SI1 ) ADD COUNT ( ( MATCHING SPJ ) [ P# ] ) AS N 
) [ N ] 
    6.28. ( SUMMARIZE ( SPJ WHERE S# = 'SI' AND P# = 'Pi') ) BY () 
    ADD SUM ( QTY ) AS Q ) [ Q ] 

    Следующее решение более точное (почему?). Обратите внимание на синтаксис 
аргумента зим. 

    ( EXTEND ( S WHERE S# = 'SI' ) ADD SUM ( ( MATCHING SPJ ) WHERE P# = 'PI', 
QTY ) 
    AS Q ) [ Q ] 
    6.29. SUMMARIZE SPJ BY ( P#, J# ) ADD SUM ( QTY ) AS Q 
    6.30. { ( SUMMARIZE SPJ BY ( P#, J# ) 
    ADD AVG ( QTY ) AS Q ) 
    WHERE Q > 320 ) [ P# ] 
    6.31. ( J JOIN ( SPJ WHERE S# = 'SI' ) ) [ JNAME ] 
    6.32. ( P JOIN ( SPJ WHERE S# = 'SI' ) ) [ COLOR ] 
    6.33. ( SPJ JOIN ( J WHERE CITY = 'London' ) ) [ P# ] 
    6.34. ( SPJ JOIN ( SPJ WHERE S# = 'SI' ) [ P# ] ) [ J# ] 
    6.35. ( ( ( SPJ JOIN ( P WHERE COLOR = 'Red' ) [ P# ] ) 
    [ S# ] JOIN SPJ ) t P# ] JOIN SPJ ) [ S# ] 
    6.36. ( ( S [ S#, STATUS ] RENAME S# AS XS#, STATUS AS XSTATUS ) TIMES 
    ( S [ S#, STATUS ] RENAME S# AS YS#, STATUS AS YSTATUS ) ) WHERE XS# = 
'SI' AND XSTATUS > YSTATUS ) [ YS# ] 
    6.37. J [ J# ] MINUS 
    ( ( J [ J#, CITY ] RENAME CITY AS XCITY ) 
    TIMES J [ CITY ] ) WHERE XCITY > CITY ) [ J# ] 
    6.38. ( ( ( SUMMARIZE ( SPJ WHERE P# = 'PI' ) BY ( J# ) 
    ADD AVG ( QTY ) AS QX TIMES ( SUMMARIZE ( SPJ WHERE J# = 'Jl' ) BY ( ) 
    ADD MAX ( QTY ) AS QY ) [ QY ] ) WHERE QX > QY ) [ J# ] 

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

    ( EXTEND ( SPJ WHERE P# = 'PI' ) ADD AVG ( ( SPJ RENAME J# AS ZJ# ) 
    WHERE ZJ# = J# AND P# = 'PI', QTY ) AS QX ) 
    [ J#, QX ] TIMES 
    ( EXTEND ( SPJ WHERE J# = 'Jl' ) 
    ADD MAX (( SPJ WHERE J# = 'Jl', QTY ) AS QY ) [ QY ] ) WHERE QX > QY ) [ 
J# ] 

    Глава 6. Реляционные операторы: I. Реляционная алгебра	175 

    6.39. ( ( ( ( ( SPJ WHERE P# = 'PI' ) [ S#, J#, QTY J ) 
    RENAME; j# AS xj#, QTY AS XQ } TIMES ( SUMMARIZE ( SPJ WHERE P# = 'PI1 ) 
BY ( J# ) 
    ADD AVG ( QTY ) AS Q ) ) WHERE XJ# = J# АЮ XQ > Q ) [ S# ] 
    6.40. J [ J# ] MINUS 
    ( ( S WHERE CITY = 'London1 ) [ S# ] 
    JOIN SPJ JOIN ( P WHERE COLOR = 'Red' ) ) [ J# ] 
    6.41. J [ J# ] MINUS ( SPJ WHERE S# *• 'SI' ) [ J# ] 
    6.42. ( P WHERE ( MATCHING SPJ ) f J# J > 
    ( J WHERE CITY = 'London' ) [ J# ] ) [ P# ] 
    6.43. ( SPJ [ S#, P#, J# ] DIVIDEBY J [ J# ] ) [ S# ] 

    Замечание. В этом решении предполагается, что отношение SPJ не пустое. 

    6.44. ( J WHERE ( MATCHING SPJ ) [ P# ] > 
    ( SPJ WHERE S# = 'SI' ) [ P# ] ) [ J# ] 
    6.45. S [ CITY ] UNION P [ CITY ] UNION J [ CITY ] 
    6.46. ( SPJ JOIN ( S WHERE CITY = 'London1 ) ) [ P# J 
    UNION ( SPJ JOIN ( J WHERE CITY = 'London1 ) ) [ P# J 
    6.47. ( S TIMES P ) [ S#, P# ] MINUS SP [ S#, P# ] 
    6.48. Мы приводим два решения этой проблемы. Первое, предложенное Хугом 
Дарвеном (Hugh Darwen), для простоты приводится в пошаговой форме с комментариями. 

    Т1 := ( SP RENAME S# AS SA ) [ SA, P# ] ; 
    /* Tl {SA,P#} : поставщик SA поставляет деталь Р# */ T2 := ( SP RENAME S# 
AS SB ) [ SB, P# ] ; 
    /* T2 (SB,P#) : поставщик SB поставляет деталь Р# */ T3 := Tl f SA ] 
    /* ТЗ {SA) : поставщик SA поставляет некоторую деталь */ T4 := Tl [ SB ] 
    /* T4 (SB) : поставщик SB поставляет некоторую деталь */ Т5 := Tl TIMES Т4 
    /* Т5 {ЗА,SB,Р#) : поставщик ЗА поставляет некоторую деталь 
    и поставщик SB поставляет деталь Р# */ Т6 := Т2 TIMES ТЗ 
    /* Т6 {ЗА,SB, Р#} : поставщик SB поставляет некоторую деталь 
    и поставщик SA поставляет деталь Р# */ Т7 := Tl JOIN T2 
    /* TV {SA,SB,Р#} : поставщики SB и SA поставляют деталь Р# */ Т8 := ТЗ 
TIMES T4 
    /* Т8 {SA,SB} : поставщик SB поставляет некоторую деталь 
    и поставщик ЗА поставляет некоторую деталь */ 

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

    Т9 := SP [ Р# ] ; 
    /* T9 {P#} : деталь Р# поставляется некоторым поставщиком */ Т10 := Т8 
TIMES T9 
    /* Т10 {SA,SB,P#} : 
    поставщик SA поставляет некоторую деталь, поставщик SB поставляет 
некоторую деталь и деталь Р# поставляется некоторым поставщиком */ Til := T10 
MINUS T7 
    /* Til {SA,SB,P#} : деталь Р# поставляется, 
    но не поставщиками SA и SB одновременно */ Т12 := Т6 INTERSECT Til 
    /* Т12 {SA,SB,P#) : деталь Р# поставляется поставщиком SA, 
    но не поставляется поставщиком SB */ Т13 := Т5 INTERSECT Til 
    /* Т13 {SA,SB,P#} : деталь Р# поставляется поставщиком SB, 
    но не поставляется поставщиком SA */ Т14 := Т12 [ SA, SB ] ; 
    /* Т14 { SA, SB } : 
    поставщик SA поставляет некоторую деталь, не поставляемую поставщиком SB 
*/ Т15 := Т13 [ SA, SB ] ; 
    /* Т15 { SA, SB } : 
    поставщик SB поставляет некоторую деталь, не поставляемую поставщиком SA 
*/ Т16 := Т14 UNION T15 ; 
    /* Т15 {SA,SB} : некоторая деталь поставляется поставщиком SA 
    или поставщиком SB, но не обоими одновременно */ Т17 := Т7 [ SA, SB ] ; 
    /* Т17 { SA, SB } : 
    некоторую деталь поставляют одновременно поставщики SA и SB */ Т18 := Т17 
MINUS T16 ; 
    /* Т18 {SA,SB} : 

    некоторую деталь поставляют одновременно поставщики SA и SB, и нет 
деталей, поставляемых SA и не поставляемых SB, и нет деталей, поставляемых SB 
и не поставляемых SA — значит, поставщики SA и SB поставляют одни и те же 
детали 
   */ Т19 := Т18 WHERE SA < SB ; 
    /* приводим отношение в порядок */ 
    Во втором решении (которое значительно проще!) используются реляционные 
сравнения. Обозначим через RA отношение S, в котором атрибут S# переименован в 
атрибут SA, а затем взята проекция по этому атрибуту, аналогично определено 
отношение RB. Тогда требуемый результат можно получить с помощью следующего выражения: 

    Глава 6. Реляционные операторы: I. Реляционная алгебра	177 

    ( RA TIMES RB ) WHERE   { SP WHERE S# = SA ) [ P# ] = 
    ( SP WHERE S# = SB ) [ Pt ] AND     SA < SB 

    Цель последней выборки (SA < SB) в обоих решениях — просто немного 
привести в порядок результат. В частности, исключить пары вида (Sa, Sa) и 
одновременное появление пар вида (Sa, Sb) и (Sb, Sa). 

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

