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

Наконец, отметим, что если отнощения А и В не имеют общих атрибутов, то операция А JOIN В эквивалентна операции А TIMES В [5.5], т.е. в таком случае естественное соединение вырождается в декартово произведение. По этой причине в версии языка Tutorial D, описанной в [3.3] оператор TIMES не поддерживается.

6.5. npHiviepbi

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

6.5.1. Получить имена поставщиков детали с номером Р2

( ( SP JOIN S ) WHERE Pt = Pt {P2) ) ) { SNAME }

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

6.5.2. Получить имена поставщиков по крайней мере одной красной детали

( ( ( Р WHERE COLOR = COLOR ( Red ) )

JOIN SP ) { St } JOIN S ) { SNAME }

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

( ( ( Р WHERE COLOR = COLOR ( Red )){?#}

JOIN SP ) JOIN S ) { SNAME }

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

6.5.3. Получить имена поставщиков всех типов деталей

( { S { S# } DIVIDEBY Р { Pt } PER SP { S#, P# } )

JOIN S) { SNAME }

И вновь в результате получаем единственный атрибут SNAME. Глава 6. Реляционная алгебра 209

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

S { S# } DIVIDEBY ( SP WHERE Si = S# ( S2 ) ) { Pi }

PER SP { S#, PI }

В результате получаем единственный атрибут SI.

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

( ( ( S RENAME S# AS SA ) { SA, CITY } JOIN ( S RENAME SI AS SB ) { SB, CITY } ) WHERE SA < SB ) { SA, SB }

В результате получаем отношение из двух атрибутов - SA и SB. Конечно, достаточно было бы переименовать лишь один атрибут в одном из операндов соединения. Мы переименовали оба атрибута для симметрии.

Замечание. Предполагается, что для типа Si определен оператор < . Условие SA<SB необходимо по следующим двум причинам.

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

Чтобы избежать наличия в результате одновременно двух пар вида (X, у) и (у, х)

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

WITH ( S RENAME S AS SA ) { SA, CITY } AS Tl, ( S RENAME S# AS SB ) { SB, CITY } AS T2, Tl JOIN T2 AS T3 T3 WHERE SA < SB AS T4 : T4 { SA, SB }

Благодаря использованию предложения WITH громоздкие выражения можно записать в пошаговой форме, не нарушая при этом принципов непроцедурности реляционной алгебры. Мы продолжим обсуждение этого вопроса в следующем примере.

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

( ( S { S# } MINUS ( SP WHERE P# = Pi ( P2 ) ) { S# } )

JOIN S ) { SNAME }

В результате получаем единственный атрибут SNAME.

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

WITH S { SI } AS Т1,

SP WHERE P# = P# ( P2 ) AS T2,

T2 { S# } AS T3,

Tl MINUS T3 AS T4,

T4 JOIN S AS T5,

T5 { SNAME } AS T6 :

Отнощение Т6 содержит требуемый результат.

Пояснение. Предполагается, что имена, которые вводятся с помощью предложения WITH, т.е. имена вида Ti, в этом примере локальны по отношению к содержащему их выражению. Затем, если система поддерживает возможность отсрочки вычислений (как, например, это делает система PRTV [6.9]), разбиение запроса на последовательность небольших шагов предложенным способом абсолютно не будет связано с какими-либо нежелательными издержками в плане производительности. В действительности весь запрос можно будет выполнить следующим образом.

Выражения, предшествующие двоеточию, не требуют немедленного вычисления; система просто должна помнить о них вместе со всеми именами, введенными с помощью соответствующих операторов AS.

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

Для того чтобы вычислить значение Т6, которое является проекцией отношения Т5 по атрибуту SNAME, система должна сначала вычислить значение отношения Т5. Но чтобы вычислить значение отношения Т5, которое является соединением отношений Т4 и S, система должна предварительно вычислить значение отношения Т4 и т.д. Иными словами, система должна эффективно вычислять исходные вложенные выражения точно так, как пользователь, в первую очередь, должен эффективно писать такие вложенные запросы.

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

6.6. Зачем нужна реляционная алгебра

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