«Boston • San Francisco • New York London • Toronto • Sydney • Tokyo • Singapore • Madrid Mexico City • Munich • Paris • Cape Town • Hong Kong • Montreal Введение в системы баз данных К. Дж. Дейт Москва • Санкт-Петербург ...»

Впоследствии Лакруа (Lacroix) и Пиротт (Pirotte) [8.7] предложили альтернативную версию исчисления, называемую исчислением доменов, в которой переменные области значений принимают значения из доменов, т.е. являются переменными, изменяемыми на доменах, а не на отношениях. (Данный термин нелогичен, ведь если исчисление доменов называется так по указанной причине, то по той же причине исчисление кортежей следовало бы назвать исчислением отношений.) В литературе предлагается множество языков исчисления доменов. Наиболее известным из них, пожалуй, является QBE (Query-By-Example — язык запросов по образцу), который впервые описан в [8.14]; в действительности язык QBE является смешанным, поскольку в нем присутствуют и элементы исчисления кортежей. Существует несколько коммерческих реализаций языка QBE, или "QBE-подобного" языка. В общих чертах исчисление доменов будет описано в разделе 8.7, а сам язык QBE вкратце рассматривается в разделе 8.8.

Примечание. Стремясь сделать эту главу короче, мы умышленно опускаем подробное описание некоторых вопросов, касающихся реляционного исчисления (таких как группирование и разгруппирование), которые имеют свои аналоги в реляционной алгебре (см. главу 7). Мы также опускаем рассмотрение соответствующих версий реляционных операторов обновления. Все эти сведения представлены в [3.3].

8.2. ИСЧИСЛЕНИЕ КОРТЕЖЕЙ Как и при описании реляционной алгебры в главе 7, сначала введем для реляционного исчисления конкретный синтаксис, взяв за образец (хотя умышленно не совсем точный) версию исчисления языка Tutorial D, определенного в приложении А книги [3.3], а затем перейдем к обсуждению семантики. В следующем подразделе обсуждается синтаксис, а в остальных — семантика.

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

292 Часть II. Реляционная модель Начнем с повторения синтаксиса параметра, приведенного в главе 7.

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

Параметр может использоваться как < tuple exp>, но лишь в определенном контексте, а именно:

перед точкой в уточняющем выражении ;

сразу после квантора в параметре ;

как операнд в параметре ;

как параметр или как выражение (или операнд с выраже Параметр может использоваться как параметр, но только в определенных контекстах, а именно:

как операнд параметра ;

как параметр или как выражение (или операнд с выражением ) в параметре.

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

Мы не приводим здесь подробного описания параметра < tuple exp>, полагая, что общее представление о нем можно получить, изучая примеры. Но по причинам, которые в данном случае не имеют большого значения, здесь используется немного иной синтаксис по сравнению с предыдущими главами.

Параметр присутствует непосредственно в выражении (т.е. параметр следует сразу за ключевым словом WHERE).

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

Примечание по терминологии. В контексте реляционного исчисления (в версии исчисления доменов или исчисления кортежей) логические выражения часто называют правильно построенными формулами (Well-Formed Formula — WFF, что произносится как "вэфф"). Далее мы также будем часто пользоваться этой терминологией.

::= EXISTS | FORALL В реляционной алгебре, рассмотренной в главе 7, параметр представлял собой одну из форм параметра, однако здесь, как уже было указано, он определяется иначе.

::-... определение см. в тексте данной главы Все ссылки на переменные области значений, помещенные непосредственно в значение параметра, должны быть свободными в пределах данного параметра Примечание. Выражение является сокращением от "prototype tuple" {кортеж-прототип); Этот термин — удачный, но не стандартный.

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

RANGEVAR SX RANGES OVER S

; RANGEVAR SY RANGES OVER

S ; RANGEVAR SPX RANGES

OVER SP ; RANGEVAR SPY

RANGES OVER SP ; RANGEVAR

PX RANGES OVER P ;

RANGEVAR SU RANGES OVER

( SX WHERE EXISTS SPX ( SPX.S# = SX.S# AND 294 Часть II. Реляционная модель В последнем примере переменная области значений SU принимает значения из объединения множества кортежей поставщиков, находящихся в Лондоне, и множества кортежей поставщиков детали с номером Р1. Обратите внимание, что в определении переменной области значений SU используются переменные области значений sx и SPX.

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

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

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

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

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

Пусть v — переменная области значений, а р и q — правильно построенные формулы.

Тогда имеем следующее.

Ссылки на переменную v в правильно построенной формуле типа NOT p свобод ны или связаны в зависимости от того, свободны или связаны они в формуле р.

Ссылки на переменную V в правильно построенной формуле типа (р AND q) и (р OR q) свободны или связаны, соответственно, в зависимости от того, свобод ны или связаны они в формулахр и q.

Ссылки на переменную V, которые являются свободными в правильно построен ной формуле р, связаны в правильно построенных формулах типа EXISTS V (p) И FORALL V(p). Другие ссылки на переменные области значений в формуле р яв ляются свободными или связанными в правильно построенных формулах типа EXISTS V(p) и FORALL v(p) в соответствии с тем, свободны или связаны они в Для полноты необходимо добавить следующие замечания.

Единственная ссылка на переменную V в значении параметра V является свободной в пределах этого параметра.

Единственная ссылка на переменную V в значении параметра V. А является свободной в пределах этого параметра.

Если ссылка на переменную V является свободной в некотором выражении ехр, то эта ссылка будет также свободной в любом выражении ехр", непосредственно содержащем выражение ехр как подвыражение, если только в выражении ехр' не введен квантор, под действием которого эта ссылка становится связанной.

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

Простые сравнения SX.S# = S# {'S1') SX.S# = SPX.S# SPX.P# PX.P# Здесь все ссылки на переменные SX, РХ и SPX являются свободными.

Простые операции сравнения, объединенные с помощью логических выражений РХ.WEIGHT < WEIGHT ( 15.5 ) AND PX.CITY = 'Oslo' NOT ( SX.CITY = 'London' ) SX.S# = SPX.S# AND SPX.P# PX.P# PX.COLOR = COLOR ('Red') OR PX.CITY = 'London' Здесь также все ссылки на переменные sx, РХ и SPX являются свободными.

Правильно построенные формулы с кванторами EXISTS SPX ( SPX.S# = SX.S# AND SPX.P# = P# ('P2') ) FORALL PX ( PX.COLOR = COLOR ('Red') ) В этих примерах ссылки на переменные SPX и РХ являются связанными, а ссылка на переменную SX остается свободной. Подробнее данные примеры описаны ниже, в подразделе "Кванторы".

Кванторы Существует два квантора2: EXISTS и FORALL. Квантор EXISTS является квантором существования, a FORALL — квантором всеобщности. По сути, если выражение р — правильно построенная формула, в которой переменная v свободна, то выражения EXISTS V ( р FORALL V ( р ) также являются допустимыми правильно построенными формулами, но переменная V в них обеих связана. Первая формула означает следующее: "Существует по меньшей мере одно значение переменной V, при котором формула р становится истинной". Вторая формула означает следующее: "Формула р является истинной при всех значениях переменной V".

Предположим, например, что переменная V принимает значения из множества "Члены Термин "квантор" происходит от латинского слова "quantum", которое, вообще говоря, означает "количество". Вместо ключевых слов EXISTS и FORALL, соответственно, часто используются символы ("обратное Е") и V ("перевернутое А").

296 Часть II. Реляционная модель сената США в 2003 году", и предположим также, что выражение р — следующая правильно построенная формула: "V— женщина" (разумеется, мы не пытаемся использовать здесь формальный синтаксис). Тогда выражение EXISTS V(p) будет допустимой правильно построенной формулой, имеющей значение TRUE {истина); выражение FORALL v(p) также будет допустимой правильно построенной формулой, но ее значение будет равно FALSE {ложь), поскольку не все члены сената— женщины.

Теперь рассмотрим квантор существования EXISTS более внимательно. Еще раз обратимся к примеру, приведенному в конце предыдущего раздела.

EXISTS SPX ( SPX.S# = SX.S# AND SPX.P# = P# ('P2') ) Из приведенных выше рассуждений следует, что эта правильно построенная формула может быть прочитана следующим образом.

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

Каждая ссылка на переменную SPX в этом примере является связанной. Единственная ссылка на переменную SX свободна.

Формально квантор существования EXISTS определяется как повторно применяемая операция OR (ИЛИ). Другими словами, если, во-первых, r — это отношение с кортежами tl, t2,..., tm, во-вторых, V—это переменная области значений, принимающая значения из данного отношения, и, в третьих, p(V) — это правильно построенная формула, в которой переменная V используется как свободная переменная, то правильно построенная формула вида эквивалентна следующей правильно построенной формуле.

В частности, следует отметить, что если отношение R пустое (т.е. т=0), то данное выражения принимает значение FALSE.

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

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

EXISTS V ( V.A > 1 OR V.C = 4 ) : TRUE Теперь рассмотрим квантор всеобщности FORALL, ДЛЯ чего вернемся к соответствующему примеру, приведенному в конце предыдущего раздела.

FORALL РХ ( РХ.COLOR = COLOR ('Red') ) Эта правильно построенная формула может быть прочитана следующим образом.

Для всех кортежей РХ, скажем, в текущем значении переменной отношения Р, значение атрибута COLOR в кортеже РХ равно Red.

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

Подобно тому, что квантор EXISTS был определен как результат многократного применения операции OR, квантор существования FORALL определяется как результат многократного применения операции AND (И). Другими словами, если обозначения r, V и р (V) имеют тот же смысл, что и в приведенном выше определении квантора EXISTS, TO правильно построенная формула вида равносильна следующей правильно построенной формуле.

В частности, следует отметить, что если отношение r пустое, то данное выражение принимает значение TRUE. В качестве примера рассмотрим отношение R, содержащее те же кортежи, что и в предыдущем примере, касающемся квантора EXISTS. Тогда приведенные ниже выражения будут иметь указанные значения.

FORALL V ( V.A = 1 AND V.C > 2 ) : TRUE Примечание. Оба квантора поддерживаются просто для удобства. С точки зрения логики нет необходимости поддерживать оба квантора, так как приведенное ниже тождество показывает, что любой из них может быть определен в терминах другого.

FORALL V ( р ) = NOT EXISTS V ( NOT p ) Неформально говоря, выражение "все значения V удовлетворяют формуле р" есть не что иное, как и выражение "нет таких значений V, которые бы не удовлетворяли формуле р". Например, (истинное) утверждение "Для любого целого х существует целое у, такое, что у > х" равносильно утверждению "Не существует целого х, такого, что не существует целого у, такого, что у > х" (иначе говоря, не существует наибольшего целого числа).

Однако одни утверждения проще выразить в терминах квантора FORALL, а другие — в терминах квантора EXISTS; вернее, если один из кванторов недоступен, то иногда возникает необходимость использовать двойное отрицание (как показано в предыдущем примере). Поэтому с точки зрения практики желательно, чтобы поддерживались оба квантора.

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

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

Теперь рассмотрим другую формулу WFF.

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

Кроме того, заслуживает внимания то, что окончательное значение первоначальной правильно построенной формулы не может быть определено, если не известно значение, указанное с помощью ссылки на свободную переменную х. В отличие от этого, правильно построенная формула, в которой все ссылки на переменные являются связанными, всегда имеет определенное значение, TRUE ИЛИ FALSE.

Дополнительная терминология. Правильно построенная формула, в которой все переменные связаны, называется закрытой правильно построенной формулой. Открытая правильно построенная формула— это формула, которая не является закрытой, т.е. такая формула, которая содержит по крайней мере одну ссылку на свободную переменную.

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

::=... определение см. в тексте данной главы Напоминаем также, что следующие синтаксические правила теперь несколько упрощены.

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

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

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

SX.S# WHERE SX.CITY = 'London' Здесь ссылка на переменную SX в кортеже-прототипе является свободной. Ссылка на переменную SX в конструкции WHERE также свободна, поскольку ссылка на ту же переменную области значений (обязательно свободную) имеется и в значении параметра этого выражения.

Приведем другой пример ("Получить имена поставщиков детали с номером Р2"; см.

обсуждение квантора существования EXISTS в подразделе "Кванторы" этого раздела).

SX.SNAME WHERE EXISTS SPX ( SPX.S# = SX.S# AND Здесь все ссылки на переменную SX являются свободными, тогда как все ссылки на переменную SPX (в конструкции WHERE) являются связанными, как и должно быть, поскольку на них нет ссылок в кортеже-прототипе.

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

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

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

б) Ссылка на атрибут области значений без конструкции AS по сути является сокращенным обозначением ссылки, включающей такую конструкцию, в которой новое имя атрибута совпадает со старым.

300 Часть II. Реляционная модель Следовательно, без потери общности кортеж-прототип можно рассматривать как разделенный запятыми список ссылок на атрибуты в виде vi. Aj AS Bj, заключенный в фигурные скобки. Обратите внимание, что не все ссылки Vi, повидимому, будут различными, и не обязательно должны отличаться друг от друга все ссылки Aj, а ссылки в j должны быть разными.

Пусть V1, V2,..., Vm — различные переменные области значений, присутствую щие в кортеже-прототипе, областями значений которых являются, соответственно, отношения rl, r2,..., rm. Допустим, что r 1', r2',..., rm' — это новые отно шения, полученные после переименования атрибутов в конструкции AS, a r' — это декартово произведение отношений r 1', r2',..., rm'.

Пусть отношение r — это сокращение отношения r', удовлетворяющее правиль но построенной формуле в конструкции WHERE.

Примечание. Здесь предполагается, что на предыдущем шаге были также переименованы атрибуты, упоминающиеся в конструкции WHERE; в противном случае правильно построенная формула в конструкции WHERE может не иметь смысла.

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

Конечное значение реляционной операции, заданной параметром, определяется как проекция отношения r по всем заданным атрибутам Bj.

В следующем разделе будет приведено несколько примеров подобных выражений.

8.3. ПРИМЕРЫ Представляем несколько примеров использования реляционного исчисления кортежей для формулирования запросов. В качестве упражнения рекомендуется решить эти задачи средствами реляционной алгебры (для сравнения и сопоставления). В некоторых случаях примеры являются повторением примеров из главы 7 (эти случаи обозначены специально).

8.3.1. Определить номера поставщиков из Парижа со статусом, большим { SX.S#, SX.STATUS } WHERE SX.CITY = 'Paris' AND SX.STATUS > 8.3.2. Найти все пары номеров таких поставщиков, которые находятся в одном городе (повторение примера 7.5.5) Обратите внимание, что конструкции AS в кортеже-прототипе используются для присваивания имен атрибутам результата. Следовательно, эти имена недоступны для использования в конструкции WHERE, и потому вторая операция сравнения в конструкции WHERE записана как sx.s# < SY.S#, а не в виде SA < SB.

8.3.3. Получить полную информацию о поставщиках детали с номером Р (модифицированная версия примера 7.5.1) SX WHERE EXISTS SPX ( SPX.S# = SX.S# AND SPX.P# = P# ('P2') ) Обратите внимание на использование имени переменной области значений в кортеже-прототипе. Этот пример является сокращенной записью следующего выражения.

{ SX.S#, SX.SNAME, SX.STATUS, SX.CITY } WHERE EXISTS SPX ( SPX.S# = SX.S# AND SPX.P# = P# ('P2') ) 8.3.4. Определить имена поставщиков по крайней мере одной детали красного цвета (повторение примера 7.5.2) SX.SNAME WHERE EXISTS SPX ( SX.S# = SPX.S# AND.

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

SX.SNAME WHERE EXISTS SPX ( EXISTS PX ( SX.S# = SPX.S# AND Предваренная (или пренексная) нормальная форма по своей сути не является более (или менее) правильной по сравнению с другими формами, но после ее усвоения можно убедиться, что в большинстве случаев она представляет собой наиболее естественный метод формирования запросов. Кроме того, она позволяет уменьшить количество используемых скобок, как показано ниже. Например, рассмотрим следующую правильно построенную формулу.

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

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

SX.SNAME WHERE EXISTS SPX EXISTS PX ( SX.S# = SPX.S# AND Однако для ясности во всех остальных примерах будем по-прежнему показывать все скобки.

302 Часть II. Реляционная модель 8.3.5. Найти имена поставщиков по крайней мере одной детали, поставляемой поставщиком с номером S WHERE EXISTS SPX ( EXISTS SPY ( SX.S# = SPX.S# AND 8.3.6. Получить имена поставщиков всех типов деталей (повторение примера 7.5.3) SX.SNAME WHERE FORALL РХ ( EXISTS SPX ( SPX.S# = SX.S# AND Эквивалентное выражение можно записать без использования KBaHTopaFORALL.

SX.SNAME WHERE NOT EXISTS PX ( NOT EXISTS SPX

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

SX.SNAME WHERE NOT EXISTS SPX

Обратите внимание, как просто это решение можно получить из решения примера 8.3.3.

8.3.8. Определить номера поставщиков, по крайней мере, тех деталей, которые поставляет поставщик с номером S2 (повторение примера 7.5.4) SX.S# WHERE FORALL SPX ( SPX.S# S# ('S2') OR Переформулируем этот запрос в соответствии со следующим выражением: "Получить номера таких поставщиков sx, что для всех поставок детали SPX, независимо то того, выполнена ли эта поставка поставщиком S2 или нет, существует поставка SPY детали SPX поставщиком sx". Чтобы упростить формулировку таких сложных запросов, как этот, введем другое синтаксическое соглашение, называемое явной синтаксической формой для оператора логической импликации. Если р и q— правильно построенные формулы, то выражение логической импликации вида также будет правильно построенной формулой с семантикой, идентичной семантике следующей формулы.

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

SX.S# WHERE FORALL SPX ( IF SPX.S# = S# ('S2') THEN Дадим словесную формулировку этого запроса: "Получить номера таких поставщиков SX, что для всех поставок SPX, если существует поставка SPX поставщиком с номером S2, то существует поставка SPY всех типов деталей, входящих в поставку SPX, поставщиком sx".

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

RANGEVAR PU RANGES OVER

( РХ.Р# WHERE PX.WEIGHT > WEIGHT ( 16.0 ) ), В эквивалентном выражении реляционной алгебры здесь могло бы использоваться явное объединение.

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

РХ.Р# WHERE PX.WEIGHT > WEIGHT ( 16.0 ) OR EXISTS SPX ( SPX.P# = PX.P# AND SPX.S# = S# ('S2') )

8.4. СРАВНИТЕЛЬНЫЙ АНАЛИЗ РЕЛЯЦИОННОГО ИСЧИСЛЕНИЯ И

РЕЛЯЦИОННОЙ АЛГЕБРЫ

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

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

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

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

{ SX.SNAME, SX.CITY } WHERE EXISTS JX FORALL PX EXISTS SPJX

Здесь SX, PX, JX и SPJX — переменные области значений, принимающие значения, соответственно, из переменных отношения s, P, J и SPJ. Теперь покажем, как можно вычислить это выражение, чтобы достичь требуемого результата.

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

SX. Все кортежи отношения s — 5 кортежей.

РХ. Все кортежи отношения р — 6 кортежей.

JX. Кортежи отношения J, в которых CITY = ' Athens'—2 кортежа..

SPJX. Кортежи отношения SPJ, в которых QTY QTY (50) — 24 кортежа.

Этап 2. Строим декартово произведение диапазонов, выбранных на первом этапе. Результат представлен ниже.

(И т.д.) Все произведение содержит 5*6*2*24 = 1 440 кортежей.

Примечание. Для экономии места здесь это отношение полностью не приводится. Мы также не переименовывали атрибуты (хотя это следовало бы сделать во избежание двусмысленности), а просто расположили их в таком порядке, чтобы было видно, какой атрибут s# относится, например, к отношению S, а какой — к отношению SPJ. Это также сделано для сокращения изложения.

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

JX.J# = SPJX.J# AND PX.P# = SPJX.P# AND SX.S# = SPJX.S# Поэтому из произведения исключаются кортежи, для которых значение атрибута s# из отношения поставщиков не равно значению атрибута s# из отношения поставок, или значение атрибута Р# из отношения деталей не равно значению атрибута Р# из отношения поставок, или значение атрибута J# из отношения проектов не равно значению атрибута J# из отношения поставок. Затем получаем подмножество декартова произведения, состоящее (как оказалось) только из десяти кортежей.

306 Часть II. Реляционная модель (Это отношение представляет собой наглядный пример соединения по эквивалентности.) Этап 4. Применяем кванторы в порядке справа налево следующим образом.

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

Для квантора FORALL V делим текущий промежуточный результат на отношение "с областью значений, полученной с помощью операции сокращения", соответст вующее отношению V, которое было получено выше. При выполнении этой опе рации также будут исключены все атрибуты отношения r.j Примечание. Под делением здесь подразумевается оригинальная операция Кодда (см. аннотацию к [7.4]).

В нашем примере имеем следующие кванторы.

EXISTS JX FORALL PX EXISTS SPJX

Таким образом, затем выполняются следующие операции.

EXISTS SPJX. Исключение с помощью операции проекции атрибутов перемен ной отношения SPJ (SPJ.S#, SPJ.P#, SPJ. J# и SPJ.QTY). В результате получа ем следующее, FORALL PX. Деление полученного результата на отношение Р. В результате имеем следующее.

EXISTS JX. Исключение с помощью операции проекции атрибутов отношения J (J. J#, J. JNAME и J. CITY). В результате получаем следующее.

Этап 5. Получение проекции результата этапа 4 в соответствии со спецификациями в кортеже-прототипе. В нашем примере кортеж-прототип имеет следующий вид.

(SX.SNAME, SX.CITY) Значит, конечный результат вычислений будет таков.

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

Этим мы завершаем обсуждение данного примера. Конечно, можно намного улучшить используемый алгоритм (см. главу 18, в частности, аннотацию к [18.4]). И хотя многие подробности в пояснениях были опущены, этот пример вполне адекватно отражает общую идею работы алгоритма редукции.

Кстати, теперь можно объяснить одну (не единственную) из причин того, почему Кодд определил ровно восемь алгебраических операторов. Эти восемь операторов образуют удобный целевой язык, который может служить средством возможной реализации реляционного исчисления. Другими словами, для заданного языка, построенного на основе реляционного исчисления (подобно языку QUEL), один из возможных подходов к реализации заключается в том, что организуется получение запроса в том виде, в каком он предоставлен пользователем. По существу, он будет являться просто выражением реляционного исчисления, к которому затем можно будет применить определенный алгоритм редукции, чтобы получить эквивалентное алгебраическое выражение. Это алгебраическое выражение, разумеется, будет включать набор алгебраических операций, которые, безусловно, будут реализуемыми по определению. (Следующий этап состоит в оптимизации полученного алгебраического выражения, о чем речь пойдет в главе 18.) Также следует отметить, что восемь алгебраических операторов Кодда являются мерой оценки выразительной мощи любого языка баз данных. Это обстоятельство уже кратко упоминалось в главе 7, в конце раздела 7.6, а сейчас пришло время обсудить его подробнее.

Прежде всего, отметим, что некоторый язык принято называть реляционно полным, если он по своим возможностям, по крайней мере, не уступает реляционному исчислению. Иначе говоря, для этого необходимо, чтобы любое отношение, которое можно определить с помощью реляционного исчисления, можно было определить и с помощью некоторого выражения рассматриваемого языка [7.1]. (В главе 7 отмечалось, что "реляционно полный" означает "не уступающий по возможностям реляционной алгебре", а не исчислению, но, как читатель вскоре убедится, это одно и то же. По сути, из самого существования алгоритма редукции Кодда немедленно следует, что реляционная алгебра обладает реляционной полнотой.) Реляционную полноту можно рассматривать как основную меру выразительной мощи языков баз данных в самом общем случае. В частности, так как реляционное исчисление и реляционная алгебра обладают реляционной полнотой, они могут служить основой для проектирования не уступающих им по выразительности языков без необходимости явно 308 Часть II. Реляционная модель прибегать к использованию циклов. Это замечание особенно важно, если язык предназначается для конечных пользователей, хотя оно также существенно, если язык предназначается для использования прикладными программистами.

Далее, поскольку алгебра обладает реляционной полнотой, для доказательства того, что некоторый язык L также обладает реляционной полнотой, достаточно показать, что в языке L есть аналоги всех восьми алгебраических операций (на самом деле достаточно показать, что в нем есть аналоги пяти примитивных операций) и что операнды любой операции языка L могут быть представлены произвольными выражениями языка L (соответствующего типа). Язык SQL — это пример языка, реляционную полноту которого можно доказать описанным способом (упр. 8.9). Язык QUEL — еще один пример подобного языка. В действительности на практике часто проще показать то, что в языке есть эквиваленты операций реляционной алгебры, чем то, что в нем существуют эквиваленты выражений реляционного исчисления. Именно поэтому реляционная полнота обычно определяется в терминах алгебраических выражений, а не в терминах выражений реляционного исчисления.

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

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

Вернемся к вопросу об эквивалентности алгебры и исчисления. Мы на примере показали, что любое выражение исчисления можно преобразовать в его некоторый алгебраический эквивалент, а значит, алгебра, по меньшей мере, не уступает по своей мощности исчислению. Можно показать обратное: каждое выражение реляционной алгебры можно преобразовать в эквивалентное выражение реляционного исчисления, а значит, исчисление, по меньшей мере, не уступает по своей мощности реляционной алгебре. Полное доказательство этих утверждений можно найти, например, в книге Ульмана (Ullman) [8.13]. Отсюда следует, что реляционная алгебра и реляционное исчисление логически эквивалентны.

8.5. ВЫЧИСЛИТЕЛЬНЫЕ ВОЗМОЖНОСТИ Несмотря на то, что ранее об этом не упоминалось, в определенном нами реляционном исчислении уже есть аналоги алгебраических операторов EXTEND и SUMMARIZE ПО перечисленными ниже причинам.

Одной из допустимых форм кортежа-прототипа является параметр < tuple se lector inv> ("вызов селектора кортежа"), компонентами которого могут быть произвольные выражения.

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

8.5.1. Определить номера и вес в граммах всех типов деталей, вес которых { РХ.Р#, РХ.WEIGHT * 454 AS GMWT } Обратите внимание, что спецификация AS в кортеже-прототипе (как и в примере 8.3.2) дает имя соответствующему атрибуту результата. Поэтому такое имя недоступно для использования в конструкции WHERE и выражение РХ. WEIGHT * 454 должно быть указано в двух местах.

8.5.2. Выбрать сведения обо всех поставщиках и обозначить каждого из них литеральным значением "Supplier" 8.5.3. Получить полные сведения о каждой поставке, включая общий вес { SPX, PX.WEIGHT * SPX.QTY AS SHIPWT } WHERE PX.P# = SPX.P# 8.5.4. Для каждой детали получить номер детали и общий объем поставки в 8.5.5. Определить общее количество поставляемых деталей

SUM ( SPX, QTY ) AS GRANDTOTAL

8.5.6. Для каждого поставщика получить номер поставщика и общий объем { SX.S#, COUNT ( SPX WHERE SPX.S# = SX.S# ) AS #_OF_PARTS } 8.5.7. Указать названия таких городов, в которых хранятся детали, что в них находится больше пяти деталей красного цвета

RANGEVAR PY RANGES OVER P ;

PX.CITY WHERE COUNT ( PY WHERE PY.CITY = PX.CITY

8.6. СРЕДСТВА ЯЗЫКА SQL Как уже говорилось в разделе 8.4, реляционный язык может быть основан как на реляционной алгебре, так и на реляционном исчислении. Что же лежит в основе языка SQL?

К сожалению, ответом будет "частично и то, и другое, а частично ни то, ни другое...".

310 Часть II. Реляционная модель Когда язык SQL только разрабатывался, предполагалось что он будет отличаться как от реляционной алгебры, так и от реляционного исчисления [4.8]. Действительно, именно этим мотивировалось введение в язык конструкции IN (см. пример 8.6.10, приведенный ниже). Однако со временем выяснилось, что язык SQL нуждается в определенных средствах как реляционной алгебры, так и исчисления, поэтому он был расширен для включения этих функций4. На сегодняшний день ситуация складывается таким образом, что язык SQL в чем-то похож на реляционную алгебру, в чем-то на реляционное исчисление, а в чем-то отличается от них обоих. Таким положением дел объясняется, почему в главе 7 мы отложили обсуждение средств обработки данных языка SQL до настоящей главы. (Мы предоставляем читателю в качестве упражнения определить, какая часть языка SQL основана на алгебре, какая на исчислении, а какая ни на том, ни на другом.) Запросы в языке SQL формулируются в виде табличных выражений < table exp>, которые в принципе могут иметь очень высокую степень сложности. Здесь мы не будем углубляться во все эти нюансы, а просто рассмотрим несколько примеров, раскрывающих наиболее важные моменты. В качестве основы для примеров взяты определения таблиц SQL для базы данных поставщиков и деталей, представленные в главе 4 (см.

рис. 4.1).

8.6.1. Указать цвета деталей и названия городов для деталей, которые имеют вес свыше 10 фунтов и хранятся в городах, отличных от Парижа SELECT PX.COLOR, PX.CITY

FROM P AS PX

Необходимо отметить следующее.

1. Как было указано в главе 5, в языке SQL в качестве оператора проверки на нера венство используется символ "о". Операторы "меньше или равно" и "больше или равно", соответственно, записываются как"< = " и ">=".

2. Спецификация Р AS PX в конструкции FROM по сути представляет собой опреде ление (в стиле исчисления кортежей) переменной области значений с именем РХ, областью значений которой является текущее значение таблицы Р. Само имя (а не переменную!) РХ принято называть именем корреляции, а областью его определе ния, неформально говоря, является табличное выражение, в котором появляется его определение, исключая любое внутреннее выражение, в котором определена другая переменная области значений с тем же именем (см. пример 8.6.12).

Вследствие этого, как отмечается в аннотации к [4.19], конструкцию IN можно полностью удалить из языка без потери его функциональности! В этом есть некоторая ирония, поскольку благодаря именно указанной конструкции в названии данного языка, в переводе означающего "язык структурированных запросов" (Structured Query Language), появилось слово "структурированный" (Structured). В действительности именно эта конструкция способствовала тому, что в первую очередь для работы с базами данных был применен язык SQL, и лишь затем реляционная алгебра и реляционное исчисление.

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

SELECT P.COLOR, P.CITY WHERE P.CITY 'Paris' AND P.WEIGHT > WEIGHT { 10.0 ) ;

Основная идея состоит в том, что должно быть разрешено использовать имя таблицы для обозначения неявно заданной переменной области значений, которая принимает значения из рассматриваемой таблицы (разумеется, при том условии, что результаты не допускают неоднозначного толкования). Например, конструкцию FROM P в данном примере можно рассматривать как сокращенную запись конструкция FROM P AS P. Другими словами, необходимо четко понимать, что уточняющее имя Р (например) в выражении P.COLOR в конструкциях WHERE и SELECT обозначает не саму таблицу Р, а переменную области значений Р, которая принимает свои значения из одноименной таблицы.

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

SELECT COLOR, CITY

FROM P WHERE CITY 'Paris' AND WEIGHT > WEIGHT ( 10.0 ) ;

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

5. В интерактивных запросах SQL может также использоваться конструкция ORDER BY, уже упоминавшаяся в главе 4 в связи с объявлением DECLARE CURSOR, как показано ниже.

SELECT P.COLOR, P.CITY WHERE P.CITY 'Paris' AND P.WEIGHT > WEIGHT ( 10.0 ) ORDER BY CITY DESC ; /* Следует о 6. Напоминаем, что допускается использование сокращения SELECT *, о котором также упоминалось в главе 4.

WHERE P.CITY 'Paris' За исключением тех случаев, которые указаны в разделе 4.6 главы 4.

312 Часть II. Реляционная модель Символ "*" в выражении SELECT * представляет собой сокращенное обозначение разделенного запятыми списка имен всех столбцов таблицы (или таблиц), указанной в конструкции FROM. В этом списке имена столбцов находятся в том же порядке, в котором они расположены в соответствующей таблице (или таблицах). Следует отметить, что такую сокращенную запись особенно удобно использовать в интерактивных запросах, поскольку при этом уменьшается количество нажатий клавиш. Однако при использовании этой конструкции во внедренных операторах SQL (т.е. в операторах языка SQL, внедренных в программу на другом языке) существует скрытая опасность, поскольку в подобных случаях символ "*" может приобрести совсем другое значение (например, после добавления в таблицу столбца или его удаления с помощью оператора ALTER TABLE).

7. {Более важная информация по сравнению с приведенной в предыдущих пунктах!) Обратите внимание, что для используемого нами в примерах набора данных этот запрос будет возвращать четыре строки, а не две, несмотря на то, что три из них будут совершенно идентичны. В языке SQL не предусмотрено удаление излишних дублирующихся строк из результата оператора SELECT, пока пользователь явно не потребует этого с помощью ключевого слова DISTINCT, как показано ниже.

SELECT DISTINCT P.COLOR, P.CITY

WHERE P.CITY 'Paris' Данный вариант запроса будет возвращать уже две строки, а не четыре.

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

Одно из следствий этого факта состоит в том, что основные операторы SQL являются не реляционными операторами в полном смысле этого слова, а аналогами реляционных операторов, предназначенных для работы с мультимножествами. Другим следствием является то, что теоремы и их побочные результаты, которые являются справедливыми в реляционной модели (например, о преобразовании выражений, [6.6]), не обязательно выполняются в языке SQL.

8.6.2. Для всех деталей указать номер детали и вес в граммах (упрощенная версия SELECT Р.Р#, P.WEIGHT * 454 AS Спецификация AS GMWT вводит соответствующее имя столбца результата для "вычисленного столбца". Таким образом, два столбца результирующей таблицы будут называться р# и GMWT. Если бы спецификация AS GMWT была опущена, то соответствующий ;

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

8.6.3. Получить все комбинации данных о поставщиках и деталях, находящихся в одном городе В языке SQL существует несколько способов формулирования этого запроса. Приведем три самых простых.

1 SELECT S.*, P.P#, P.PNAME, P.COLOR, P.WEIGHT WHERE S.CITY = P.CITY ;

2 S JOIN P USING CITY ;

3 S NATURAL JOIN P ;

Результатом в каждом случае6 будет естественное соединение таблиц S и Р (по атрибуту города CITY).

Первая формулировка заслуживает более подробного обсуждения. Именно она, единственная из трех предложенных вариантов, допустима в первоначальной версии языка SQL (явная операция JOIN была введена в стандарте SQL: 1992). Концептуально можно рассматривать реализацию этой версии запроса следующим образом.

Во-первых, после выполнения конструкция FROM МЫ получаем декартово произведение S TIMES P. (Строго говоря, перед вычислением произведения следовало бы позаботиться о переименовании столбцов. Для простоты мы этот вопрос не рас сматриваем. Напоминаем также, что, как следует из сказанного в разделе 7.7, де картовым произведением единственной таблицы t является сама таблица t.) Во-вторых, после выполнения конструкция WHERE МЫ получаем сокращение этого произведения, в котором два значения атрибута CITY В каждой строке равны (иначе говоря, выполнено соединение таблиц поставщиков и деталей по эквивалентности атрибутов с обозначением города).

В-третьих, после выполнения конструкция SELECT мы получаем проекцию выбор ки по столбцам, указанным в конструкции SELECT. Конечным результатом становится естественное соединение указанных таблиц.

Следовательно, неформально говоря, в языке SQL конструкция FROM соответствует декартову произведению, конструкция WHERE — операции сокращения, а конструкции SELECT-FROM-WHERE, вместе взятые, — проекции сокращения произведения (но, как было указано выше, рассматриваемая "проекция" не обязательно устраняет дубликаты).

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

SELECT DISTINCT S.CITY AS SCITY, P.CITY AS

PCITY FROM S JOIN SP USING S# JOIN P USING

Обратите внимание, что приведенный ниже оператор является неправильным (объясните, почему).

В стандарте SQL:2003, по-видимому, будет предусмотрено требование, чтобы вторая и третья формулировки включали префикс "SELECT * FROM".

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

SELECT DISTINCT S.CITY AS SCITY, P.CITY AS PCITY FROM S

NATURAL JOIN SP NATURAL JOIN P ;

Ответ. Поскольку во втором соединении он включает столбец CITY как столбец, по которому выполняется соединение.

8.6.5. Получить все пары номеров поставщиков, таких что оба поставщика в каждой паре находятся в одном городе (см. пример 8.3.2) SELECT A.S# AS SA, B.S# AS

SB FROM S AS A, S AS В

WHERE A.CITY = B.CITY AND В этом примере требуется явно указывать переменные области значений. Также следует отметить, что вводимые имена столбцов SA и SB относятся к столбцам результирующей таблицы, и потому не могут использоваться в конструкции WНЕRЕ.

8.6.6. Определить общее количество поставщиков SELECT COUNT(*) AS Результатом будет таблица с одним столбцом, которому присвоено имя N, и одной строкой, содержащей значение 5. Язык SQL поддерживает типичный набор агрегирующих функций7: COUNT, SUM, AVG, MAX, MIN, EVERY и ANY. Однако есть еще несколько специфических особенностей языка SQL, о которых необходимо знать пользователю.

. В общем случае фактическому параметру агрегирующей функции может предшествовать необязательное ключевое слово DISTINCT (например, SUM (DISTINCT QTY) ), которое указывает, что перед применением этой функции дублирующиеся строки должны быть удалены. Для функций MAX, MIN, EVERY и ANY ключевое слово DISTINCT является излишним и не вызывает никакого действия.

Специальная агрегирующая функция COUNT(*) не допускает использования ключевого слова DISTINCT И предназначена для подсчета всех строк в таблице без предварительного удаления дублирующихся строк.

Любые неопределенные значения в столбце фактического параметра (глава 19) удаляются перед применением агрегирующей функции независимо от того, указа но ли ключевое слово DISTINCT, кроме случая использования агрегирующей функции COUNT (*), когда неопределенные значения обрабатываются так же, как обычные значения.

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

EVERY - это аналог конструкции ALL в языке SQL (в этом языке ключевое слово ALL не поддерживается). Вместо ключевого слова ANY можно применить SOME. Кроме того, было введено несколько дополнительных агрегирующих операторов в связи с созданием версии SQL/OLAP, позволяющей использовать язык SQL в области так называемой "оперативной аналитической обработки" (см. главу 22).

Примечание. Этот результат является логически правильным для COUNT, но не для других операторов. Например, как было показано в разделе 8.2, оператор EVERY с точки зрения логики должен возвращать значение TRUE, если он применяется к пустому множеству.

8.6.7. Определить максимальное и минимальное количество деталей с SELECT МАХ ( SP.QTY ) AS MAXQ, MIN ( SP.QTY ) AS MINQ

FROM SP

WHERE SP.P# = P# ('P2') ;

Здесь обе конструкции, FROM и WHERE, фактически предоставляют часть формальных параметров для двух агрегирующих функций. Следовательно, с точки зрения логики они должны были бы записываться в скобках, заключающих аргументы. Тем не менее, данный запрос действительно должен записываться именно так, как показано выше. Этот неортодоксальный подход к синтаксису оказывает существенное отрицательное влияние на структуру, удобство использования и ортогональность8 языка SQL. Например, одно из следствий состоит в том, что агрегирующие функции не могут быть вложенными, в результате чего такой запрос, как "Вычислить среднее значение итоговых значений количества деталей", нельзя сформулировать без громоздких выражений. Если быть точным, то следующий запрос является неправильным.

SELECT AVG ( SUM ( SP.QTY ) ) /* Предостережение! Это Вместо этого данный запрос следовало бы сформулировать, например, таким образом.

SELECT AVG ( X ) FROM ( SELECT SUM ( SP.QTY ) AS X

FROM SP

Назначение конструкции GROUP BY разъясняется в следующем примере, а использование вложенных подзапросов, подобных приведенным здесь в конструкции FROM, — несколько ниже.

Примечание. Спецификация AS POINTLESS бессмысленна, однако ее наличия требуют синтаксические правила языка SQL (дополнительная информация приведена в [4.20]).

8.6.8. Для каждой поставляемой детали указать номер детали и общий объем поставки в штуках (модифицированная версия примера 8.5.4) SELECT SP.P#, SUM ( SP.QTY ) AS TOTQTY

FROM SP

GROUP BY SP.P# ;

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

316 Часть II. Реляционная модель Приведенное выше выражение на языке SQL является аналогом следующего выражения реляционной алгебры.

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

Оно также является аналогом следующего выражения реляционного исчисления кортежей.

( SPX.P#, SUM ( SPY WHERE SPY.P# = SPX.P#, QTY ) AS TOTQTY ) В частности, следует отметить, что если в запросе указана конструкция GROUP BY, то выражения в конструкции SELECT должны быть однозначными для заданной группы.

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

FROM SP

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

Этого нельзя было обеспечить с помощью предыдущей формулировки, в которой использовалась конструкция GROUP BY. (Но, к сожалению, значение TOTQTY для таких деталей будет представлено в виде пустого значения, а не нуля.) 8.6.9. Определить номера всех деталей, поставляемых больше чем одним SELECT SP.P#

FROM SP

GROUP BY SP.P# HAVING COUNT ( SP.S# ) > 1 ;

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

8.6.10. Определить имена поставщиков детали с номером Р2 (см. пример 7.5.1)

SELECT DISTINCT S.SNAME

WHERE S.S# IN Пояснения. В этом примере в конструкции WHERE используется так называемый подзапрос. Неформально говоря, подзапрос — это выражение из конструкций SELECT-FROMWHERE-GROUP BY-HAVING, которое вложено в другое такое же выражение. Подзапрос чаще всего используется для представления множества значений, поиск которых осуществляется с помощью конструкция IN С условием, что и представлено в данном в примере. Система вычисляет запрос в целом, предварительно вычислив указанный подзапрос (по крайней мере, концептуально). Подзапрос в данном примере возвращает множество номеров поставщиков детали с номером Р2, а именно, {S1,S2,S3,S4}.

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

SELECT DISTINCT S.SNAME

Следует отметить, что первоначальную задачу — "Получить имена поставщиков детали с номером Р2" — можно столь же успешно выразить с помощью операции соединения, например, таким образом.

SELECT DISTINCT S.SNAME

8.6.11. Определить имена поставщиков по крайней мере одной детали красного цвета (см. пример 8.3.4)

SELECT DISTINCT

S.SNAME FROM S WHERE

FROM SP

Подзапросы могут иметь произвольную глубину вложения. Упражнение. Приведите эквивалентную формулировку этого запроса с использованием операции соединения.

8.6.12. Определить номера поставщиков, имеющих статус меньше того, который в данное время является максимальным в таблице S SELECT S.S# WHERE S.STATUS < В этом примере используются две отдельные неявные переменные области значений, обозначенные тем же именем S и принимающие значения из той же таблицы S.

8.6.13. Определить имена поставщиков детали с номером Р Примечание. Этот пример повторяет пример 8.6.10. Ниже приведено другое решение, позволяющее представить еще одно средство языка SQL.

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

SELECT DISTINCT

S.SNAME FROM S

WHERE EXISTS

FROM SP

Пояснение. Выражение EXISTS (SELECT... FROM...) на языке SQL принимает значение TRUE тогда и только тогда, когда результат вычисления выражения SELECT...

FROM... будет непустым. Другими словами, в языке SQL функция EXISTS соответствует квантору существования реляционного исчисления (в большей или меньшей степени;

см. [19.6]).

Примечание. В спецификации SQL ссылки на подзапрос, аналогичные показанным в данном примере, называются ссылками на коррелированный подзапрос (correlated subquery), поскольку в данном подзапросе содержится ссылка на переменную области значений (а именно — на неявную переменную области значений S), которая определена во внешнем запросе. Еще одним примером коррелированного подзапроса может служить пример 8.6.8.

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

SELECT DISTINCT S.SNAME

WHERE NOT EXISTS

FROM SP

Этот же запрос можно также представить в альтернативной формулировке.

SELECT DISTINCT

S.SNAME FROM S

WHERE S.S# NOT IN 8.6.15. Определить имена поставщиков, которые поставляют детали всех типов (см. пример 8.3.6)

SELECT DISTINCT

S.SNAME FROM S

WHERE NOT EXISTS (

SELECT * FROM P

WHERE NOT EXISTS

Язык SQL не включает какой-либо непосредственной поддержки квантора всеобщности FORALL; следовательно, запросы "с кванторами FORALL" обычно выражаются с помощью квантора существования и двойного отрицания, как и в этом примере.

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

SELECT DISTINCT S.SNAME

WHERE ( SELECT COUNT ( SP.P# )

FROM SP

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

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

SELECT DISTINCT S.SNAME /* Предостережение! Недопустимый запрос! */ WHERE { SELECT SP.P#

FROM SP

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

8.6.16. Определить номера деталей, которые либо весят более 16 фунтов, либо поставляются поставщиком с номером S2, либо соответствуют и тому, и другому условию (см. пример 8.3.9) SELECT P.P# WHERE P.WEIGHT > WEIGHT ( 16.0 ) UNION 320 Часть II. Реляционная модель SELECT SP.P#

FROM SP

WHERE SP.S# = S# ('S2') ;

Лишние повторяющиеся строки всегда исключаются из результата выполнения неуточненных операторов UNION, INTERSECT И EXCEPT (В языке SQL оператор EXCEPT служит аналогом операции MINUS реляционной алгебры). Однако язык SQL также поддерживает уточненные варианты этих операторов (UNION ALL, INTERSECT ALL И EXCEPT ALL), при которых повторяющиеся строки (если они есть) сохраняются. Примеры с этими вариантами операторов умышленно не показаны.

8.6.17. Определить номер детали и вес в граммах для каждой детали с весом SELECT P.P#, P.WEIGHT * 454 AS GMWT WHERE P.WEIGHT * 454 > WEIGHT ( 10000.0 ) ;

Теперь необходимо вспомнить определение конструкция WITH, которая была впервые представлена в главе 5 и использовалась при описании реляционной алгебры9 в главе 7.

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

WITH Tl AS ( SELECT P.P#, P.WEIGHT * 454 AS GMWT SELECT T1.P#, Tl.GMWT FROM Tl WHERE Tl.GMWT > WEIGHT ( 10000. Кстати, следует отметить, что записи в конструкции WITH (которые в предыдущей главе именовались как — определение имени) в языке SQL принимают вид AS (), а в языке Tutorial D имеют форму AS. Необходимо также учитывать, что конструкция WITH приобретает важное значение, когда требуется сформулировать на языке SQL аналог алгебраического оператора TCLOSE.

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

На этом список примеров применения языка SQL для выборки данных завершается.

Хотя этот список был достаточно большим, о многих возможностях языка SQL здесь даже не упоминалось. Язык SQL в действительности является чрезвычайно избыточным [4.19] в том смысле, что почти всегда существует множество способов представления одного и того же запроса, и нам не хватит места, чтобы описать все возможные формулировки и все возможные опции даже для сравнительно небольшого числа примеров, которые рассматривались в этой главе. (Дополнительные сведения на эту тему приведены в приложении Б.) Безусловно, эта конструкция может также использоваться в реляционном исчислении.

8.7. ИСЧИСЛЕНИЕ ДОМЕНОВ Как было указано в разделе 8.1, исчисление доменов отличается от исчисления кортежей тем, что в нем переменные области значений определены на доменах (типах), а не на отношениях. С точки зрения синтаксиса наиболее очевидное различие между исчислением доменов и исчислением кортежей состоит в том, что первое поддерживает дополнительную форму параметра, который мы будем называть условием принадлежности (membership condition). В общем виде условие принадлежности можно записать следующим образом.

Здесь R — имя переменной отношения, а каждый параметр имеет вид А х, где А — имя атрибута переменной отношения R, а х — имя переменной области значений или вызов селектора (чаще всего литерал). В целом, это условие принимает значение TRUE тогда и только тогда, когда в текущем значении переменной отношения R существует такой кортеж, что для каждого заданного выражения А х сравнение А = х имеет значение TRUE ДЛЯ данного кортежа. Например, рассмотрим результат вычисления следующего выражения.

Это выражение является условием принадлежности, которое принимает значение TRUE тогдаи только тогда, когда обнаруживается, что в настоящее время существует кортеж с данными о поставке, в котором значение s# равно si, а значение Р# равно Р1.

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

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

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

раздела 322 Часть II. Реляционная модель SX WHERE S { S# SX, CITY 'London' } { SX, CITYX } WHERE S { S# SX, CITY CITYX } { SX, PX } WHERE S { S# SX, CITY

CITY CITYY } AND CITYX

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

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

8.7.1. Определить номера поставщиков из Парижа со статусом больше (упрощенная версия примера 8.3.1)

SX WHERE EXISTS STATUSX

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

8.7.2. Найти все такие пары номеров поставщиков, в которых два поставщика находятся в одном городе (см. пример 8.3.2)

{ SX AS SA, SY AS SB } WHERE EXISTS CITYZ

8.7.3. Определить имена поставщиков по крайней мере одной детали красного цвета (см.

NAMEX WHERE EXISTS SX EXISTS PX

8.7.4. Определить имена поставщиков, которые поставляют хотя бы один тип деталей, поставляемых поставщиком с номером S2 (см. пример 8.3.5)

NAMEX WHERE EXISTS SX EXISTS PX

8.7.5. Определить имена поставщиков, которые поставляют детали всех типов (см. пример 8.3.6)

NAMEX WHERE EXISTS SX ( S { S# SX, SNAME

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

NAMEX WHERE EXISTS SX ( S { S# SX, SNAME

8.7.7. Определить номера поставщиков, которые поставляют, по меньшей мере, детали всех типов, поставляемых поставщиком с номером S (см. пример 8.3.8) SX WHERE FORALL PX ( IF SP { S# S#('S2'), P# 8.7.8. Получить номера деталей, которые либо весят более 16 фунтов, либо поставляются поставщиком с номером S2, либо соответствуют и тому, и другому условию (см. пример 8.3.9)

PX WHERE EXISTS WEIGHTX

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

8.8. ЯЗЫК ЗАПРОСОВ ПО ОБРАЗЦУ Одним из наиболее широко известных примеров языка, основанного на исчислении доменов, является язык запросов по образцу (Query-By-Example — QBE) [8.14]. (Фактически QBE одновременно воплощает в себе средства исчисления доменов и исчисления кортежей, но первое в нем доминирует.) Его синтаксис является очень привлекательным и простым для интуитивного восприятия; он основан на идее внесения записей в пустые таблицы. Например, формулировка на языке QBE запроса: "Определить имена поставщиков, 324 Часть II. Реляционная модель которые поставляют по меньшей мере одну деталь, поставляемую поставщиком S2" может выглядеть примерно следующим образом.

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

Записи, начинающиеся с символа подчеркивания, представляют собой примеры элементов (т.е. переменные области определения в исчислении доменов); другие записи представляют собой литеральные значения. Пользователь запрашивает систему предоставить ему ("Р." — сокращение от present) имена поставщиков (_NX), такие, что если поставщик имеет номер _sx, то поставщик _sx поставляет некоторую деталь _РХ, а эта деталь _РХ, в свою очередь, поставляется поставщиком S2. Сравнение этой формулировки QBE с эквивалентной ей формулировкой в исчислении кортежей или доменов (см. примеры 8.3.5 и 8.7.4) показывает, что ее отличие от таких формулировок состоит в отсутствии явно заданных кванторов10; это служит еще одной причиной того, что язык QBE является простым для интуитивного восприятия. Имеет также смысл сравнить эту версию запроса QBE с формулировкой на языке SQL (оставляем это в качестве упражнения для читателя).

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

8.8.1. Определить номера поставщиков, находящихся в Париже, которые имеют статус > 20 (пример 8.7.1) Обратите внимание, насколько просто можно представить операции сравнения ">" и "=". Следует также отметить, что нет необходимости явно задавать элемент примера, если он больше нигде не упоминается (но и не будет ошибкой явное задание элемента примера, такого как P._sx). Кроме того, заслуживает внимания то, что символьные строковые значения, такие как Paris, можно задавать, не заключая их в кавычки (но не будет также ошибкой применение таких кавычек, а иногда они даже требуются, например, если строка включает пробелы).

Возможно также ввести запись "Р." применительно ко всей строке, например, как показано ниже.

Кстати, аналогичное замечание относится и к языку QUEL (см., например, [8.5]).

Этот пример эквивалентен следующему, в котором запись "Р." присутствует в каждой позиции столбца в строке.

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

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

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

8.8.2. Определить номера всех поставляемых деталей, удалив ненужные дубликаты В данной таблице UNQ. является сокращением от unique — уникальный (эта запись соответствует ключевому слову DISTINCT в языке SQL).

8.8.3. Получить номера и данные о статусе поставщиков, находящихся в Париже, вначале выполнив сортировку в порядке убывания статуса, а затем — в порядке возрастания номеров Здесь запись "АО." обозначает сортировку в порядке возрастания, a "DO." — в порядке убывания. Числа в круглых скобках указывают последовательность сортировки столбцов от старшего к младшему; в данном примере STATUS является старшим столбцом, a s# — младшим.

326 Часть II. Реляционная модель 8.8.4. Получить номера и данные о статусе поставщиков, которые либо находятся в Париже, либо имеют статус > 20, либо соответствуют обоим условиям (модифицированная версия примера 8.8.1) Условия, заданные в одной строке, рассматриваются как соединенные друг с другом логическим оператором "И" (см., допустим, пример 8.8.1). Для того чтобы соединить два условия логическим оператором "ИЛИ", их необходимо задать в разных строках, как показано ниже.

Еще один подход к формированию этого запроса состоит в использовании так называемого поля условия (condition box), как показано ниже.

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

8.8.5. Определить детали, вес которых находится в пределах от 16 до 8.8.6. Для всех деталей определить номер детали и вес детали в граммах (пример 8.8.7. Определить номера поставщиков, которые поставляют деталь Р В данном случае к строке таблицы SP неявно применен квантор существования. Этот запрос можно выразить иначе, как показано ниже.

Определить имена поставщиков SX, таких что существует поставка, характеризующаяся тем, что поставщик SX поставляет деталь Р2.

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

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

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

8.8.9. Определить все пары номеров поставщиков, таких что оба поставщика в каждой паре находятся в одном городе (пример 8.6.5) В случае необходимости для определения дополнительного условия _SX < _SY может использоваться поле условия.

8.8.10. Определить общее количество поставляемых деталей Р В языке QBE поддерживаются все обычные операции агрегирования.

По меньшей мере, не поддерживает должным образом. Данное определение поддерживается в нем лишь частично. На первых порах фактически в языке QBE была предусмотрена "полная" поддержка определения NOT EXISTS, но эта поддержка всегда была под сомнением. Основная проблема состояла в том, что не было способа указать порядок, в котором должны были применяться различные неявные кванторы, но, к сожалению, этот порядок имеет значение, если присутствуют какие-либо операторы отрицания NOT. В результате некоторые выражения QBE были двусмысленными. Подробное обсуждение данного вопроса можно найти в [8.3]. См. также упр. 8.2.

328 Часть II. Реляционная модель 8.8.11. Для каждой поставляемой детали определить номер детали и общий объем поставки (пример 8.6.8) Запись "G. " обеспечивает группирование (она соответствует конструкции GROUP BY в языке SQL).

8.8.12. Определить номера всех деталей, поставляемых больше чем одним 8.8.13. Определить номера деталей, которые либо весят больше 16 фунтов, либо поставляются поставщиком S2, либо соответствуют и тому, и другому условию (пример 8.7.8).

8.8.14. Вставить в таблицу Р данные о детали с номером Р7 (город Афины, вес 24, название и цвет в настоящее время не известны) Обратите внимание на то, что запись "I. " применяется ко всей строке, поэтому находится под именем таблицы.

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

8.8.15. Удалить данные обо всех поставках, в которых количество поставляемых деталей было больше Запись "D. " находится под именем таблицы.

8.8.16. Изменить цвет детали Р2 на желтый, увеличить ее вес на пять и указать в соответствующей колонке город Осло 8.8.17. Для всех поставщиков, находящихся в Лондоне, изменить объем поставки на пять 8.9. РЕЗЮМЕ В этой главе кратко рассматривалось реляционное исчисление, альтернативное реляционной алгебре. Внешне два подхода очень отличаются: исчисление имеет характер описания, а алгебра — характер предписания, но на более низком уровне они представляют собой одно и то же, поскольку любые выражения исчисления могут быть преобразованы в семантически эквивалентные выражения алгебры и наоборот.

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

Выражение исчисления кортежей состоит из кортежа-прототипа и необязательной конструкции WHERE, содержащей логическое выражение или правильно построенную формулу (Well-Formed Formula — WFF). Подобная правильно построенная формула может включать кванторы (EXISTS И FORALL), свободные и связанные ссылки на переменные, логические (булевы) операторы (AND, OR, NOT и др.) и т.д. Каждая свободная переменная, которая встречается в правильно построенной формуле, должна быть также упомянута в кортеже-прототипе.

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

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

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

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

330 Часть II. Реляционная модель Запрос SQL представляет собой табличное выражение. Обычно такая конструкция содержит единственное выражение выборки, однако поддерживаются и различные типы явных выражений операций соединения, причем выражения соединения и выборки могут комбинироваться произвольным образом с помощью операторов UNION, INTERSECT и EXCEPT. Также упоминалось о возможности использования конструкция ORDER BY ДЛЯ определения упорядоченности строк в таблице, являющейся результатом вычисления данного табличного выражения (любого вида).

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

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

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

Конструкция WHERE, включая использование оператора EXISTS.

Конструкция GROUP BY и HAVING, включая использование агрегирующих функций Использование подзапросов (например) в конструкциях12 SELECT, FROM И WHERE.

Кроме того, здесь был описан концептуальный алгоритм вычисления выражений выборки языка SQL (основа для формального определения этих выражений). Кратко можно отметить, что этот алгоритм предусматривает формирование декартова произведения таблиц, указанных в конструкции FROM, применение операции сокращения к этому произведению в соответствии с логическим выражением, указанным в конструкции WHERE, и наконец, применение операции проекции к результатам операции сокращения по столбцам, указанным в конструкции SELECT. НО следует сразу же сделать оговорку, что это краткое описание является далеко не полным; более подробные сведения приведены в [4.20].

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

УПРАЖНЕНИЯ

8.1. Пусть р (х) и q — произвольные правильно построенные формулы, в которых переменная х, соответственно, используется и не используется в качестве свободной переменной. Какие из следующих формулировок верны? (Здесь символ "=>" означает "следует", а символ "" означает "эквивалентно". Обратите внимание, что Но следует отметить, что довольно неформально подзапросы в конструкции FROM часто рассматриваются как табличные выражения, подзапросы в конструкции SELECT — как скалярные выражения, а подзапросы в конструкции WHERE — как табличные выражения или скалярные выражения, в зависимости от контекста (!).

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

а) EXISTS х EXISTS у ( р(х,у) ) EXISTS у EXISTS х ( р(х,у) ) б) FORALL х FORALL у ( р(х,у) ) FORALL у FORALL x ( р(х,у) ) В) FORALL х ( р(х,у) ) NOT EXISTS x ( NOT p(x,y) ) Г) EXISTS x ( р(х,у) ) NOT FORALL x ( NOT р(х,у) ) Д) EXISTS x FORALL у ( р(х,у) ) FORALL у EXISTS x ( р(х,у) ) е) EXISTS у FORALL х ( р(х,у) ) => FORALL x EXISTS у ( р(х,у) ) 8.3. Пусть р(х) и q(y) — произвольные правильно построенные формулы, соответст венно, со свободными переменными х и у. Какие из следующих формулировок 8.4. Еще раз обратимся к запросу "Определить номера поставщиков, по крайней мере, всех типов деталей, поставляемых поставщиком с номером S2". Для этого запроса возможна следующая формулировка в терминах исчисления кортежей.

SX.S# WHERE FORALL SPY ( IF SPY.S# = S# ( ' S2') THEN (Здесь SPZ — это еще одна переменная области значений, которая определена на отношении поставок.) Что будет возвращено при выполнении этого запроса, если поставщик с номером S2 в данный момент не поставляет никаких деталей? Что будет, если в приведенном выражении переменную SX всюду заменить переменной SPX?

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

{ PX.PNAME, PX.CITY } WHERE FORALL SX FORALL JX EXISTS SPJX

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

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

8.6. Выразите в терминах исчисления кортежей запрос "Определить три самые тяже 8.7. Рассмотрим отношение спецификации материалов переменной отношения PART_STRUCTURE, представленной в упр. 4.6 главы 4. Обратимся к широко из вестному запросу разузлования деталей "Получить номера деталей, которые на лю бых уровнях вхождения являются компонентами некоторой заданной детали (скажем, детали с номером Р1)". Результат этого запроса, например отношение PART_BILL (которое, безусловно, является отношением, производным от исход ного отношения PART_STRUCTURE), нельзя сформулировать в виде единственного выражения начального реляционного исчисления (или реляционной алгебры).

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

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

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

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

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

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

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

8.14. Дайте ответы к упр. 7.13-7.50, используя средства языка SQL.

8.15. Дайте ответы к упр. 7.13—7.50 в терминах исчисления доменов.

8.16. Дайте ответы к упр. 7.13-7.50, используя средства языка QBE.

СПИСОК ЛИТЕРАТУРЫ

8.1. Codd E.F. A Data Base Sublanguage Founded on the Relational Calculus // Proc. ACM SIGFIDET Workshop on Data Description, Access and Control. — San Diego, Calif. —November 1971.

8.2. Date C.J. A Note on the Relation Calculus // ACM SIGMOD Record 18. — 1989. — № 4. Переиздано: An Anomaly in Codd's Reduction Algorithm // C.J. Date and Hugh Darwen. Relational Database Writings 1989—1991. Reading, Mass.: Addison-Wesley, 8.3. Date C.J. Why Quantifier Order Is Important // C.J. Date and Hugh Darwen. Relational Database Writings 1989-1991. — Reading, Mass.: Addison-Wesley, 1992.

8.4. Date C.J. Relational Calculus as an Aid to Effective Query Formulation // C.J. Date and Hugh Darwen. Relational Database Writings 1989—1991.— Reading, Mass.: AddisonWesley, 1992.

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

8.5. Held G.D., Stonebraker M.R., and Wong E. INGRES — A Relational Data Base System // Proc. NCC 44. — Anaheim, Calif. Montvale, N.J.: AFIPS Press, May 1975.

С середины и до конца 1970-х годов разрабатывались два главных реляционных прототипа: система System R в фирме IBM и система Ingres (первоначально ее название записывалось прописными буквами, INGRES) в Калифорнийском университете (город Беркли). Оба этих проекта оказали очень большое влияние на дальнейшие исследования и впоследствии привели к созданию таких коммерческих систем, как СУБД DB2 (в случае системы System R) и коммерческий продукт Ingres (в случае системы Ingres).

Примечание. Прототип Ingres иногда называют "University Ingres" [8.11], чтобы отличать его от коммерческой версии этой системы. Учебный обзор коммерческой версии можно найти в [1.5].

334 Часть II. Реляционная модель Система Ingres вначале не являлась системой SQL, поскольку исходно поддерживала язык QUEL (Query Language), который во многих отношениях технически превосходил SQL. В самом деле, язык QUEL по-прежнему составляет основу достаточного числа современных исследований баз данных, а примеры на языке QUEL до сих пор появляются в исследовательской литературе. Данная статья, в которой впервые был описан прототип Ingres, включает предварительное определение языка QUEL. См. также [8.10]—[8.12].

8.6. Kuhns J.L. Answering Questions by Computer: A Logical Study // Report RM-5428-PR, Rand Corp. — Santa Monica, Calif., 1967.

8.7. Lacrorix M., Pirotte A. Domain-Oriented Relational Languages // Proc. 3rd Int. Conf.

on Very Large Data Bases. — Tokyo, Japan., October 1977.

8.8. Merrett Т.Н. The Extended Relational Algebra, A Basis for Query Languages // Shneiderman B. (ed.). Databases: Improving Usability and Responsiveness. New York, N.Y.: Academic Press., 1978.

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

8.9. Negri М, Pelagatti G., Sbattella L. Formal Semantics of SQL Queries // ACM TODS. - September 1991. - 16, № 3.

Цитата из резюме: "Семантика запросов SQL формально определена с помощью множества правил, определяющих преобразование на основе синтаксиса запроса SQL в формальную модель, называемую расширенным исчислением трехзначных предикатов (Extended Three Valued Predicate Calculus — E3VPC), которая главным образом основана на хорошо известных математических понятиях. Приведены также правила преобразования общего выражения E3VPC в каноническую форму;

[дополнительно] полностью решены проблемы, подобные анализу эквивалентности запросов SQL". Однако отметим, что в статье рассматривается только тот диалект языка SQL, который определен в самой первой версии стандарта (в 1986 году).

Примечание. Определения терминов трехзначный предикат и каноническая форма, соответственно, приведены в главах 19 и 18.

8.10. Stonebraker M. (ed.) The INGRES Papers: The Anatomy of a Relational Database Management System // Reading, Mass.: Addison-Wesley, 1986.