Главная » SQL, Базы данных » ОРИГИНАЛЬНАЯ АЛГЕБРА СЕМАНТИКА

0

7.9.  Объединение

В математике объединение двух множеств представляет собой множество всех элементов, принадлежащих либо к одному из них, либо к обоим заданным  множествам. Поскольку любое отношение представляет собой (или, скорее, содержит) множество (а именно множество кортежей), оно, безусловно,  позволяет формировать объединение двух таких множеств; результатом является множество, состоящее из всех кортежей, присутствующих либо в одном, либо в обоих из заданных отношений. Например, объединение множества кортежей поставщиков, которые в настоящее время присутствуют в переменной отношения S, и множества кортежей деталей, присутствующих в настоящее время в переменной отношения Р, безусловно, представляет собой множество.

Но хотя этот результат можно назвать множеством, он не является  отношением; от ношения не могут содержать смесь кортежей разных типов,  поскольку они должны включать однотипные кортежи. А нам требуется, чтобы результат представлял собой от ношение, поскольку необходимо сохранить реляционное свойство замкнутости. Поэтому объединение в реляционной алгебре  не полностью соответствует общему определению объединения в математике; скорее, оно является объединением особого рода, в котором два входных отношения должны принадлежать к одному типу. Это означает, например, что оба отношения должны содержать кортежи поставщиков или кортежи деталей, но не смесь кортежей этих двух типов. Если же два отношения принадлежат к одному и тому же типу, то может быть получено их объединение, а результат также будет представлять со бой отношение того же типа; иными словами, сохраняется свойство замкнутости.

Примечание. По традиции в большинстве литературных источников по базам данных (включая первые издания этой книги) для обозначения того требования, что оба отношения должны принадлежать к одному и тому же типу, применялся термин совместимость по объединению (union compatibility). Но этот термин нельзя назвать очень удачным по целому ряду причин; наиболее важной из них является то, что указанное требование

не распространяется только на объединение.

Поэтому определение операции реляционного объединения должно быть таким: если даны отношения а и b одного и того же типа, то объединение этих отношений a UNION b является отношением того же типа с телом, которое состоит из всех кортежей t, присутствующих в а или b или в обоих отношениях.

Пример. Предположим, что отношения А и B  имеют вид, показанный на рис. 7.2 (оба они получены из текущего значения переменной отношения поставщиков S; вообще говоря, в А приведены данные о поставщиках из Лондона, а в в — данные о поставщиках, которые поставляют деталь Р1). В таком случае в объединение A UNION в (см. рис. 7.2, а) входят поставщики, которые либо находятся в Лондоне, либо поставляют деталь Р1, либо соответствуют обоим этим условиям. Обратите внимание на то, что в результате содержатся три кортежа, а не четыре; по определению отношения никогда не содержат дубликаты кортежей   (поэтому,  неформально  выражаясь,  из  результатов  операции  объединения "устраняются дубликаты"). Кстати, следует отметить, что единственной не рассмотренной

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

Рис. 7.2. Примеры операций объединения, пересечения и разности

Между прочим, обратите внимание на то, что определение операции объединения базируется на понятии равенства кортежей. Приведем еще одно, но эквивалентное определение, в котором этот нюанс подчеркивается очень  ясно  (измененная формулировка отмечена курсивным шрифтом): если даны отношения а и b одного и того же типа, то объединение этих отношений a  UNION  b является отношением того же типа с телом, состоящим из всех кортежей t, таких, что t равен некоторому кортежу из а или b или из обоих отношений {т.е. является его дубликатом). Как вскоре станет очевидно, аналогичные замечания касаются непосредственно операций пересечения и разности.

Пересечение

Как и для объединения, и фактически по той же причине, для реляционной операции пересечения требуется, чтобы ее операнды принадлежали к одному и тому же типу. Если даны отношения а и b одного и того же типа, то  пересечением этих отношений а INTERSECT b является отношение того же типа с телом, состоящим из всех кортежей t, таких, что t присутствует одновременно в а и b.

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

Разность

Как и для объединения и пересечения, для реляционной операции разности требуется, чтобы ее операнды принадлежали к одному и тому же типу. Если даны отношения а и b одного и того же типа, то разностью этих отношений a MINUS b (в указанном порядке), является отношение того же типа с телом, состоящим  из  всех кортежей t, таких, что t присутствует в а, но не в b.

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

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

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

{   Al   al,   A2   а2,    . . . ,   Am  am   }

И

{    B1  b1,    B2  b2,     …,    Bn bn    }

то теоретико-множественное объединение этих двух кортежей представляет собой приведенный ниже единственный кортеж.

{   Al   al,   A2   а2,     …,   Am  am,   Bl  bl,   B2   b2,     …,   Bn bn   }

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

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

1 В языке Tutorial D требуется, чтобы перед каждым из приведенных ниже выражений стояло ключевое СЛОВО TUPLE.

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

Итак, определим (реляционное) декартово произведение a TIMES b отношений а и b, не имеющих общих атрибутов, как отношение, заголовок которого представляет собой (теоретико-множественное) объединение заголовков отношений а и b, а тело состоит из всех кортежей t, таких, что t является (теоретико-множественным) объединением кортежа, принадлежащего к  отношению а, и кортежа, принадлежащего к отношению b. Следует отметить, что кардинальность результата равна произведению кардинальностей входных отношений, а и b, а степень результата — сумме степеней входных отношений.

Пример. Предположим, что отношения А и   B  показаны на рис. 7.3  (неформально выражаясь, отношение А содержит все текущие номера поставщиков, а в — все текущие номера  деталей).  В  таком  случае  декартово   произведение  A  TIMES  В  (которое показано в нижней части данного рисунка) включает в себя все текущие пары номеров поставщиков и номеров деталей.

Рис. 7.3. Пример декартова произведения

Сокращение

Допустим, что отношение а имеет атрибуты X и Y (и, возможно, другие атрибуты), а 0 является таким оператором ( как правило, "=", "≠", ">", "<" и т.д.), что логическое выражение X θ Y является правильно построенным и при определенных значениях X и Y приобретает истинностное значение (TRUE или FALSE). В таком случае 6-сокращением (или просто сокращением) отношения а по атрибутам X и Y (в указанном порядке), которое

задано с помощью приведенного ниже выражения, является отношение с тем же  заголовком, что и в отношении а, и с телом, состоящим из всех кортежей отношения а, таких что выражение X θ Y для рассматриваемого кортежа принимает значение TRUE.

a WHERE  X  θ  Y

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

a WHERE p

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

Рис. 7.4. Примеры применения операции сокращения Из этого следуют приведенные ниже выводы.

1.  Выражение р, которое следует за ключевым словом WHERE, безусловно, является

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

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

на рис. 7.4, являются простыми. А ниже для сравнения приведен пример, в котором используется непростое условие сокращения.

S WHERE ( ( SP RENAME S# AS X ) WHERE X = S# ) { P# } = P { P# }

Этот пример более подробно рассматривается ниже в данном разделе, вслед за описанием оператора деления.

3.  Заслуживают внимания следующие эквивалентные выражения.

a WHERE p1 OR p2 ≡ (a WHERE p1 ) UNION ( a WHERE p2 )

a WHERE p1 AND р2 ( a WHERE p1 ) INTERSECT ( a WHERE p2 )

a WHERE NOT ( р ) ≡ a MINUS ( a WHERE p )

Проекция

Предположим,  что  отношение  а  имеет  атрибуты  х,  Y,  .  .  .,  Z  (и,  возможно, другие атрибуты). В таком случае проекция отношения а по  атрибутам X, у, …, z, которая определяется с помощью следующего выражения

а   {   X,   Y,    . . . ,   Z   }

является отношением, соответствующим описанным ниже требованиям.

Его заголовок формируется из заголовка отношения а путем удаления всех атрибутов, не указанных в множестве {  X,   Y,  . . . ,    z  }.

Тело состоит из всех кортежей {  Х х ,    У у,   …,   z  z  }, таких что в отношении а присутствует кортеж со значением х атрибута X, у атрибута Y… и z атрибута Z.

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

Из этого следует приведенные ниже выводы.

1.            Ни один из атрибутов не может быть указан в разделенном запятыми списке имен атрибутов больше одного раза (объясните, почему).

2.            На практике часто удобно иметь возможность указывать не атрибуты, по которым должна быть сформирована проекция, а скорее те атрибуты, которые "должны быть отброшены" (т.е. удалены) после выполнения операции проекции. Например, вместо использования формулировки "получить проекцию отношения Р по атри бутам Р#, PNAME, COLOR И CITY", МОЖНО ИСПОЛЬЗОВаТЬ формулировку "ИСКЛЮЧИТЬ с помощью операции проекции атрибут WEIGHT ИЗ отношения р" как показано ниже.

Р  {  ALL  BUT WEIGHT  }

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

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

Соединение

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

X1,    Х 2,     . . . ,     Xm,    Y1,    Y2,     . . . ,     Yn

Y l ,    Y 2 ,                                        . . . ,     Y n ,    Zl,    Z2,                                        . . . ,     Zp

ЭТО означает, что два рассматриваемых отношения имеют общее множество атрибутов Y, состоящее из атрибутов Yl,  Y2 ,   . . . ,   Yn (и только из этих атрибутов), другие атрибуты отношения а образуют множество х, состоящее из атрибутов X1,   Х2, Xm, а другие атрибуты отношения b образуют множество z, состоящее из атрибутов Z1, Z2,   . .

. ,   Zp. Необходимо сделать приведенные ниже замечания.

■     Можно и нужно предположить без потери точности, что благодаря наличию оператора переименования атрибутов RENAME НИ ОДИН ИЗ атрибутов xi (i  =  1, 2,    . . . ,   m) не имеет такого же имени, как любой из атрибутов z j (j   =  1,   2,

…,   Р).

■     Каждый атрибут Yk (к  =   1,   2,    . . .,   n) имеет одинаковый тип в обоих отно шениях, а и Ь (поскольку в противном случае он по определению не должен рас сматриваться как общий атрибут).

Те пе рь множества { XI, Х 2 , . . . ,  X m } , { Y l , Y 2 , . . . ,  Y n } и {   Zl,  Z2,

. . ., Zp } могут рассматриваться, соответственно, как три составных атрибута х, Y и z.

В таком случае (естественное) соединение а и b выражается следующим образом.

a JOIN b

Оно представляет собой отношение с заголовком { X, Y, Z } и телом, состоящим из всех таких кортежей { X х, Y у, z z }, что любой из этих кортежей присутствует и в отношении а, со значением х атрибута х и значением у атрибута Y, и в отношении b, со значением у атрибута Y и значением z атрибута Z.

Пример естественного соединения (естественное соединение s JOIN P по  общему атрибуту CITY) приведен на рис. 7.6.

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

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

Рис. 7.5. Примеры применения операции проекции

Рис. 7.6. Естественное соединение S JOIN P

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

■     Если п =   0 (а это означает, что отношения а и b не имеют общих атрибутов), то операция a JOIN b вырождается2 в операцию a TIMES b.

■     Если m =  p  =   0 (а это означает, что отношения а и b относятся к одинаковому типу), то операция a JOIN b вырождается в операцию a INTERSECT b.

2 Именно по этой причине версия языка Tutorial D, которая определена в [3.3], не включает непосредственной поддержки для оператораTIMES.

Теперь перейдем к изучению операции 9-соединения. Эта операция предназначена для тех случаев (сравнительно редких, но тем не менее достаточно важных), когда возникает необходимость соединить два отношения на основе некоторого оператора сравнения, отличного от сравнения на равенство. Предположим, что отношения а и b удовлетворяют требованиям для декартова произведения (т.е. не имеют общих имен атрибутов); пусть а имеет атрибут X и b — атрибут У, а х, y и θ удовлетворяют требованиям для 8соединения. В таком случае операция 6-соединения отношения а по атрибуту X с отношением b по атрибуту y определена как результат вычисления следующего выражения.

(   a  TIMES   b   )   WHERE  X  9  У

Иными словами, результатом становится отношение с тем же заголовком, как и у декартова произведения а и b, и с телом, состоящим из множества всех кортежей t, таких что t присутствует в этом декартовом произведении, и выражение X θ У принимает значение TRUE для данного кортежа t.

В качестве примера предположим, что необходимо вычислить соединение по оператору "больше" отношения s по атрибуту CITY с отношением р по атрибуту CITY (итак, в данном случае 0 имеет вид ">", а поскольку атрибуты CITY определены как принадлежащие к типу CHAR, то оператор ">" просто означает "больше в алфавитном порядке"). Соответствующее реляционное выражение приведено ниже.

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

) WHERE SCITY > PCITY

Обратите внимание на то, что в данном примере выполняется переименование атрибутов. (Безусловно, было бы достаточно переименовать только один из двух атрибутов CITY; единственная причина переименования обоих состоит в стремлении обеспечить равнозначность этих атрибутов.) Результат применения всего этого выражения приведен на рис. 7.7.

Рис. 7.7. Соединение по оператору "больше" отношений поставщиков и деталей по городам Если 0 представляет собой операцию проверки на равенство ("="), то 0-соединение

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

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

S  JOIN  P

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

{ ( S TIMES ( P RENAME CITY AS PCITY ) ) WHERE CITY = PCITY )

{ ALL BUT PCITY }

Примечание. В языке Tutorial D не предусмотрена непосредственная поддержка операции 8-соединения, поскольку на практике необходимость в ней не возникает достаточно часто и она так или иначе не относится к типу примитивных операций (т.е. может быть определена в терминах других операций, как было показано выше).

Деление

В [7.4] определены две разные операции "деления", которые именуются, соответственно, малым делением (Small Divide) и большим делением (Great  Divide). В языке Tutorial D малым делением является операция <divide>, в которой выражение <реr> состоит только из одного реляционного выражения <relation exp>, а большим делением — операция <divide>, в которой <реr> состоит из заключенного в круглые скобки и разделенного запятыми списка из двух выражений <relation exp>. Приведенное ниже описание относится только к малому делению, причем лишь к конкретной ограниченной форме малого деления; подробное описание операции большого деления и дополнительные сведения об операции малого деления приведены в [7.4].

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

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

XI,   Х2,    . . . ,

Хm И

Yl,    Y2,     …,    Yn

Здесь ни один из атрибутов xi (i = 1, 2, . . ., m) не имеет одинакового  имени с любым из атрибутов Yj (j = 1, 2, . . ., п). Пусть отношение с  имеет  следующие атрибуты:

XI,     Х 2 ,                                         . . . ,                                        X m ,     Y l ,     Y 2 ,                                         . . . ,                                        Y n

ЭТО означает, что с имеет заголовок, представляющий собой (теоретико-множественное) объединение заголовков а и Ь. Будем рассматривать множества { XI, Х2, …, Хт } и { Yl, Y2, . . ., Yn }, соответственно, как составные атрибуты х и Y. В таком случае операция деления а на b по с (где а — делимое, Ъ — делитель, а с — посредник) может быть представлена с помощью следующего выражения.

a DIVIDEBY b PER с

Оно представляет собой отношение с заголовком { X } и телом, состоящим из всех кортежей { X х }, присутствующих в а, причем таких, что кортеж { х х, Y  у } присутствует в с для всех кортежей { Y у }, присутствующих в b. Иными словами, неформально выражаясь, данный результат состоит из тех значений X, присутствующих в а, для которых соответствующие значения Y в с включают все значения Y из b. Обратите внимание на то, что и в этом определении применяется понятие равенства кортежей!

На рис. 7.8 приведены некоторые примеры деления. В каждом случае делимое (DEND) представляет собой проекцию текущего значения переменной отношения S по атрибуту S#; посредник (MED) в каждом случае является проекцией текущего значения переменной отношения SP по атрибутам S# и Р#; а три делителя (DOR) являются такими, как указано на этом рисунке. В частности, заслуживает особого внимания последний пример, в котором делителем служит отношение, содержащее номера всех деталей, известных в настоящее время; результат (что вполне очевидно) показывает номера тех поставщиков, которые поставляют все эти детали. На основании данного примера можно сделать вывод, что оператор DIVIDEBY предназначен для запросов подобного общего характера; в действительности, каждый раз, когда версия запроса на естественном языке содержит

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

Рис. 7.8. Примеры деления

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

S WHERE ( ( SP RENAME S# AS X ) WHERE X = S# ) { p# } =                                           P { P# }

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

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

(   (  SP RENAME  S#  AS  X  )  WHERE X  =  S#  )   {  P#  }

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

Затем это множество сравнивается с множеством всех известных в настоящее время номеров деталей.

2.  Соответствующий кортеж поставщика появляется в результате, если и только если эти два множества равны.

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

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

У читателя вполне может сложиться впечатление, что вариант с реляционным сравнением концептуально проще для использования. И действительно, возникают некоторые сомнения по поводу того, нужно ли было вообще определять оператор DIVIDEBY, если реляционная модель уже включает реляционные сравнения, но дело в том, что она таковые не включает.

7.10.   .  ПР ИМ ЕР Ы

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

7.5.1.Определить имена поставщиков, которые поставляют деталь Р2

{ ( SP JOIN S ) WHERE Р# = Р# (‘Р2′) ) { SNAME }

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

7.5.2.     Определить имена поставщиков, которые поставляют по меньшей мере одну деталь красного цвета

{ ( ( Р WHERE COLOR = COLOR (‘Red’) )

JOIN SP ) { S# } JOIN S ) { SNAME }

Единственным атрибутом результата снова становится SNAME. Кстати сказать, ниже приведена еще одна, эквивалентная формулировка того же запроса.

( ( ( Р WHERE COLOR = COLOR (‘Red’) ) { P# } JOIN SP ) JOIN S ) { SNAME }

Итак, данный пример иллюстрирует такую важную особенность, что часто существует несколько разных способов формулировки некоторого запроса. Обсуждение определенных следствий из этого факта приведено в главе 18.

7.5.3.     Определить имена поставщиков, которые поставляют все детали

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

JOIN S ) { SNAME }

Еще одна формулировка этого запроса приведена ниже.

( S WHERE

( ( SP RENAME S# AS X ) WHERE X = S# ) { P# } = P { P# } )   { SNAME }

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

7.5.4.    Определить номера поставщиков, поставляющих, по меньшей мере, все детали, поставляемые поставщиком S2

S { S# } DIVIDEBY ( SP WHERE S# = S# (‘S2′) ) { P# }

PER SP { S#, P# }

Результат имеет единственный атрибут, s#

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

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

В данном случае результат включает два атрибута, SA и SB (фактически было бы достаточно переименовать только один из двух атрибутов S#, но здесь переименованы оба атрибута, чтобы не подчеркивать различия между ними). Предполагается, что для типа s# определен оператор "<". Условие сокращения SA  < SB выполняет следующие два назначения:

■  устраняет пары номеров поставщиков в форме (х, х);

■  гарантирует, что в результате не появятся обе пары, и ( х , у ), и (у,х).

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

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 позволяет формировать большие, сложные выражения и при этом никоим образом не нарушает непроцедурный характер реляционной алгебры. Эта тема будет продолжена в описании, которое следует за очередным примером.

7.5.6.Определить имена поставщиков, которые не поставляют деталь Р2

( ( S { S# } MINUS ( SP WHERE P# = P# (‘P2′) ) { S# } ) JOIN S ) { SNAME }

Результат содержит единственный атрибут, SNAME.

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

WITH S { S# } AS Tl,

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   :

T6

Пояснение. Предполагается, что имена, введенные с помощью конструкции  WITH (т.е. в данном примере имена в форме Ti), являются локальными по  отношению к оператору, содержащему эту конструкцию. Итак, если система  поддерживает режим "отложенного вычисления" (как, например, система  PRTV  [7.9]), то разбивка всего запроса на последовательность шагов в такой форме не оказывает отрицательного влияния на производительность. Данный  запрос фактически обрабатывается, как описано ниже.

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

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

3  В действительности, скалярная форма оператора WITH уже использовалась в определении оператора DIST (см. раздел 5.5 главы 5), а в разделе 6.5 главы 6 была показана его  реляционная  форма в расширении сокращения UPDATE.

После достижения этой точки система больше не может откладывать вычисление и должна каким-то образом рассчитать требуемое значение (т.е. значение T6).

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

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

Источник: Дейт К. Дж., Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — 1328 с.: ил. — Парал. тит. англ.

По теме:

  • Комментарии