Дейт К. Введение в системы баз данных
Подождите немного. Документ загружается.
9. Глава 6
10. Реляционные
11. операторы:
12. I. Реляционная алгебра
6.1. Введение
Третья и последняя часть реляционной модели — операторы — существенно
эволюционировала со времени первой публикации статьи Кодда [6.1]. Однако как и
раньше основным компонентом этой части модели является так называемая
реляционная алгебра, которая в основном состоит из набора операторов,
использующих отношения в качестве операндов и возвращающих отношения в
качестве результата. В главе 3 кратко обсуждались операторы выборки, проекции и
соединения; эти и некоторые другие операторы рассматриваются в этой главе более
подробно.
В [6.2] Кодд определяет так называемую "начальную" алгебру, т.е. набор из
восьми операторов, показанный символически на рис. 6.1. Определяя именно эти
восемь операторов, Кодд преследовал особую цель, о которой пойдет речь в
следующей главе. Однако важно понимать, что на этих операторах не заканчивается
история; на самом деле можно было бы определить любое число операторов,
которые бы удовлетворяли простому необходимому условию: "отношение на входе,
отношение на выходе" (множество таких операторов действительно предлагалось
разными авторами; см., например, [6.9-6.11]). В этой главе сначала рассматриваются
операторы Кодда (или, по крайней мере, его версия операторов), а затем они
используются в качестве основы для обсуждения различных алгебраических идей; в
продолжение этой темы обсуждаются способы, с помощью которых данный
первоначальный набор операторов можно расширить.
Обзор начальной алгебры
Как утверждалось выше, реляционная алгебра, определенная Коддом в [6.2],
состоит из восьми операторов, составляющих две группы, по четыре оператора в
каждой.
1. 1.BBBBBBBBBBB Традиционные операции над множествами: объединение, пересечение,
вычитание и декартово произведение (все они модифицированы с учетом того,
что их операндами являются отношения, а не произвольные множества).
2. 2.BBBBBBBBBBB Специальные реляционные операции: выборка, проекция, соединение и
деление. Ниже приведены упрощенные определения этих восьми операторов
(см. рис. 6.1).
Выборка: возвращает отношение, содержащее все кортежи из определенного
отношения, которые удовлетворяют определенным условиям. Операция выборки
также называется операцией ограничения
11[1]
, поэтому далее в этой книге будет
также употребляться термин ограничение, если подразумевается алгебраическая
операция.
11
Проекция: возвращает отношение, содержащее все кортежи (называемые как
подкортежи) определенного отношения после исключения из него некоторых
атрибутов.
Произведение: возвращает отношение, содержащее всевозможные кортежи,
которые являются сочетанием двух кортежей, принадлежащих соответственно двум
определенным отношениям.
Объединение: возвращает отношение, содержащее все кортежи, которые
принадлежат или одному из двух определенных отношений, или обоим.
Пересечение: возвращает отношение, содержащее все кортежи, которые
принадлежат одновременно двум определенным отношениям.
Вычитание: возвращает отношение, содержащее все кортежи, которые
принадлежат первому из двух определенных отношений и не принадлежат второму.
Соединение: возвращает отношение, кортежи которого — это сочетания двух
кортежей (принадлежащих соответственно двум определенным отношениям),
имеющих общее значение для одного или нескольких общих атрибутов этих двух
отношений (и такие общие значения в результирующем кортеже появляются только
один раз, а не дважды).
Замечание. Строго говоря, это естественное соединение. (О различных видах
соединений речь идет ниже в этой главе.)
Деление: для двух отношений, бинарного и унарного, возвращает отношение,
содержащее все значения одного атрибута бинарного отношения, которые
соответствуют (в другом атрибуте) всем значениям в унарном отношении.
На этом закончим краткий обзор первоначальных операторов. План остальной
части главы такой: в следующем вводном разделе повторно и более подробно
рассматривается вопрос замкнутости. Затем в деталях обсуждается восемь
первоначальных операторов, предложенных Коддом и даются некоторые примеры
использования этих операторов для формулирования запросов. Далее обсуждается
вопрос "зачем нужна алгебра" и описываются два немаловажных оператора,
называемых EXTEND и SUMMARIZE. Затем рассматриваются операции
присвоения, обновления и реляционное сравнение. И наконец, дается краткое
заключение.
6.2. Замкнутость
Уже не раз отмечалось, что результат каждой операции над отношением (или
реляционной операции) также является отношением. Это реляционное свойство
называется свойством замкнутости и впервые упоминается в главе 3. Там же
делается вывод: поскольку результат любой операции имеет тот же тип, что и
исходные объекты (отношения), то результат одной операции может
использоваться в качестве исходных данных для другой. Таким образом, имеется
возможность, например, взять или проекцию от объединения, или соединение от
двух выборок, или объединение соединения и пересечения и т.д.
Другими словами, можно записывать вложенные выражения, т.е. выражения,
в которых операнды сами представлены выражениями вместо простых имен
отношений. В этой главе приводится много примеров таких вложенных выражений
(фактически они будут встречаться на протяжении всей книги).
Замечание, Есть явная аналогия между возможностями использования
вложенных реляционных выражений в реляционной алгебре и вложенных
арифметических выражений в обычной арифметике. Действительно, тот факт, что
отношения замкнуты, важен в алгебре по тем же причинам, по которым в обычной
арифметике важно, что числа замкнуты.
При обсуждений свойства замкнутости в главе 3 сознательно умалчивался один
существенный момент. Как уже разъяснялось в главе 4, отношение имеет две части
— заголовок и тело; нестрого говоря, заголовок — это множество атрибутов, а тело
— это данные. Заголовок для базового отношения, очевидно, вполне конкретен и
известен системе, поскольку он определяется как часть соответствующего оператора
create base relation (см. главу 4). Ну а как же для производных отношений?
Рассмотрим, например, выражение
S JOIN P,
которое представляет соединение отношения поставщиков и отношения
деталей по соответствующим городам (значение атрибута CITY общее для двух
отношений). Что будет заголовком для результата этого соединения? Обязательное
наличие заголовка диктуется замкнутостью, а системе должно быть известно, что
это такое (это в равной степени необходимо и пользователю, как мы скоро увидим).
Поэтому, если рассматривать замкнутость более строго, каждая реляционная
операция должна быть определена таким образом, чтобы выдавать результат с
надлежащим заголовком (т.е. с соответствующим набором необходимых имен
атрибутов). Причина такого требования к результирующим отношениям
заключается в необходимости иметь возможность обращаться к именам атрибутов
в последующих операциях, например в дальнейших операциях, расположенных на
более глубоких уровнях вложенного выражения. Мы не могли бы, например, даже
записать такое выражение, как
(S JOIN P) WHERE WEIGHT > 18,
если бы не знали, что результат вычисления выражения s join p имеет атрибут
WEIGHT. Другими словами, необходим такой набор правил наследования имен
атрибутов, встроенный в алгебру, чтобы можно было предсказывать имена
атрибутов на выходе произвольной реляционной операции, зная имена атрибутов на
входе этой операции. Задав такие правила для всех операций, можно гарантировать,
что для выражения любой сложности будет вычисляться результат, имеющий
вполне определенный набор атрибутов.
Прежде чем двигаться дальше, отметим, что этот аспект алгебры, как правило,
недооценивается в литературе, кроме двух заметных работ — Холла (Hall) и др.
[6.9] и Дарвена (Darwen) [4.7]. Версия алгебры, представленная в этой главе, была
выбрана в значительной мере под влиянием работы Дарвена. (В более ранних
изданиях этой книги, обращаясь к проблеме наследования имен атрибутов, мы
использовали подход, который был значительно хуже предложенного Дарвеном.)
Наша версия реляционной алгебры определена таким образом, чтобы
гарантировать, что все отношения будут иметь правильные заголовки, т.е.
заголовки, в которых все атрибуты имеют правильные имена, уникальные в
содержащем их отношении. Для достижения этой цели необходим новый оператор
rename, предназначенный для переименования атрибутов в определенном
отношении. Точнее, для определенного отношения оператор rename возвращает (по
крайней мере концептуально) новую копию отношения, в котором некоторый
атрибут имеет другое заданное имя. (Определенное отношение, конечно, может
быть результатом вычисления выражения, включающего другие алгебраические
операции.) Например, можно написать:
S RENAME CITY AS SCITY
С помощью этого выражения (обратите внимание, что рассматриваемая запись
является выражением, а не командой или оператором, а значит, может быть
вложена в другие выражения) вычисляется отношение, имеющее то же самое тело,
что и отношение S, но с именем атрибута SCITY вместо CITY:
Другие атрибуты этого отношения наследуют имена своих эквивалентов в
отношении S без изменения. Само отношение безымянное. (Напоминаем читателю,
что мы начали использовать переменную RENAME в синтаксисе для определения
внешних ключей. Если нужно освежить этот материал в памяти, обратитесь к главе
5.)
В заключение стоит обратить ваше внимание на то, что можно расширять
понятие замкнутости и дальше. Как отмечалось в главе 5, каждое отношение Имеет
не только заголовок и тело, а и множество потенциальных ключей. Поэтому в
определенных случаях может понадобиться, чтобы системе были известны
потенциальные ключи (так же, как и имена атрибутов) для каждого
результирующего отношения. Другими словами, было бы весьма полезно иметь
набор правил наследования потенциальных ключей, с помощью которых в
системе можно было бы определить потенциальные ключи для результата
произвольного выражения.
6.3. Синтаксис реляционной алгебры
Сейчас самое время ввести конкретный синтаксис для операций реляционной
алгебры (см. BNF-грамматику на рис. 6.2). Обратите внимание, что синтаксис не
рассматривается в качестве серьезного кандидата для языка конечного пользователя,
он не особенно дружественный, а используется как надежная основа для
обсуждения операторов в оставшейся части главы и, конечно, его можно было бы
сделать более дружественным с помощью соответствующего "синтаксического
сахара". И действительно, несколько позже в этой главе будут предложены наши
собственные простые усовершенствования.
Несколько замечаний по грамматике
1. 1.BBBBBBBBBBB В главе 4 приводилось объяснение условным обозначениям типа
"commalist" (что означает список, разделенный запятыми).
2. 2.BBBBBBBBBBB Обозначения relation (отношение) и attribute (атрибут)
определяются как идентификаторы, которые представляют собой
соответственно имя отношения и имя атрибута.
3. 3.BBBBBBBBBBB Объяснение обозначения condition (условие) приводится ниже в этой
главе.
В определенной выше грамматике для обеспечения правильного порядка в
вычислениях сложных выражений необходимо часто использовать скобки. Ниже в
этой главе описаны некоторые упрощения, во многих случаях позволяющих
уменьшить общее количество скобок. Об одном из таких упрощений, а именно о
множественном переименовании, мы поговорим прямо сейчас. Рассмотрим
следующий пример:
(S RENAME CITY AS SCITY) RENAME S# AS SNUM
Как указывалось ранее, внутреннее выражение служит для вычисления
отношения с телом, таким же как и у отношения S, но имеющим атрибут города с
именем SCITY, а не CITY; а общее выражение — соответственно для вычисления
отношения с таким же телом, но дополнительно с измененным именем атрибута
номера поставщика S# на SNUM. Чтобы можно было переименовать несколько
атрибутов за один раз, не используя многоуровневые вложенные выражения,
вводится расширенная версия оператора rename:, в которой предыдущий пример
будет выглядеть следующим образом:
(S RENAME CITY AS SCITY, S# AS SNUM)
Иными словами, другой допустимый синтаксис для этой синтаксической
категории переименования таков:
(term RENAME rename-commalist)
Здесь обозначение comma list (как указывалось выше) означает список через
запятую, а rename означает, что каждый из элементов этого списка представляет
собой выражение
attribute AS attribute
6.4. Традиционные операции над множествами
Теперь рассмотрим отдельные операции начальной алгебры подробнее,
используя конкретный синтаксис, представленный в предыдущем разделе.
Настоящий раздел касается традиционных операций над множествами, а
следующий — специальных реляционных операций.
Традиционные операции над множеством — это объединение, пересечение,
вычитание и произведение (точнее, расширенное декартово произведение). Давайте
сначала рассмотрим объединение.
В математике объединение двух множеств является множеством всех
элементов, принадлежащих или обоим, или одному из исходных множеств.
Поскольку отношение является, нестрого говоря, множеством кортежей, то,
очевидно, можно построить объединение двух отношений; результат будет
множеством, содержащим все кортежи, принадлежащие или обоим, или одному из
исходных отношений. Например, объединение множества кортежей поставщиков в
отношении S и множества кортежей деталей в отношении Р является, несомненно,
множеством.
Однако, хотя такой результат и является множеством, он не является
отношением; отношения не могут содержать смесь кортежей разных типов, они
должны содержать однородные кортежи. И конечно, результат тоже должен быть
отношением, поскольку необходимо, чтобы сохранилось свойство замкнутости.
Следовательно, объединение в реляционной алгебре не полностью совпадает с
математическим объединением, вернее, это особая форма объединения, в которой
требуется, чтобы два исходных отношения, нестрого говоря, имели "одну и ту же
форму". Это означает, например, что они оба содержат кортежи поставщиков или
кортежи деталей, а не смесь обоих видов. Если два отношения имеют "одну и ту же
форму", то их можно объединить и результат объединения будет отношением той
же формы; иначе говоря, свойство замкнутости будет сохранено.
Более точный термин понятия "одна и та же форма" — совместимо по типу.
12[2]
Будем говорить, что два отношения совместимы по типу, если у них идентичные
заголовки, а точнее,
1) 1)BBBBBBBBBBB если каждое из них имеет одно и то же множество имен атрибутов
(следовательно, заметьте, они заведомо должны иметь одну и ту же
степень);
2) 2)BBBBBBBBBBB если соответствующие атрибуты (т.е. атрибуты с теми же самыми
именами в двух отношениях) определены на одном и том же домене.
Операции объединения, пересечения и вычитания требуют от операндов
совместимости по типу. Аргументы, аналогичные приведенным выше для
объединения, применимы также для пересечения н вычитания. (Операция декартова
произведения, напротив, такого требования к операндам не выдвигает, хотя и имеет
собственные требования, как вы скоро убедитесь.) Если необходимо выполнить
операцию объединения, пересечения или вычитания двух отношений, которые
почти совместимы по типу, за исключением некоторых различий в именах
атрибутов, можно использовать оператор rename (обсуждаемый выше в этой главе),
чтобы сделать эти отношения полностью совместимыми по типу, прежде чем
выполнить необходимую операцию.
Теперь можно приступить к определениям традиционных операций над
множествами, точнее, к тем их разновидностям, которые поддерживаются в
реляционной алгебре.
Объединение
Объединением двух совместимых по типу отношений А и В (A UNION B)
называется отношение с тем же заголовком, как и в отношениях А и В, и с телом,
12
состоящим из множества всех кортежей t, принадлежащих А или В или обоим
отношениям.
Пример. Пусть отношения А и В будут такими, как показано на рис. 6.3
(отношение А представляет поставщиков из Лондона, а отношение В —
поставщиков, которые, например, поставляют деталь Р1). Тогда выражение a union в
(см. рис. 6.3,а) представляет поставщиков, которые или размещаются в Лондоне, или
поставляют деталь Р1 (либо и то и другое). Обратите внимание, что результат имеет
три кортежа, а не четыре — повторяющиеся кортежи удаляются по определению.
Замечание. Вопрос удаления дубликатов не возникает в других традиционных
операциях над множествами (пересечение, вычитание и произведение). Фактически
существует еще только одна операция (помимо объединения), где этот вопрос
возникает, — проекция.
Пересечение.
Пересечением двух совместимых по типу отношений А и В (A INTERSECT B)
называется отношение с тем же заголовком, как и в отношениях А и В, и с телом,
состоящим из множества всех кортежей t, принадлежащих одновременно обоим
отношениям А и В.
Пример. Пусть снова отношения А и В будут такими, как показано, на рис. 6.3.
Тогда выражение A INTERSECT В (см. рис. 6.3,6) представляет поставщиков,
которые размещаются в Лондоне и поставляют деталь Р1.
Вычитание
Вычитанием двух совместимых по типу отношений А и В (A MINUS B)
называется отношение с тем же заголовком, как и в отношениях А и В, и с телом,
состоящим из множества всех кортежей t, принадлежащих отношению А и не
принадлежащих отношению В.
Пример. Пусть снова отношения А и В будут такими, как показано на рис. 6.3.
Тогда выражение A MINUS В (см. рис. 6.3,в) представляет поставщиков,
которые .размещаются в Лондоне и не поставляют деталь Р1, а B MINUS A (см.
рис. 6.3,г) представляет поставщиков, которые поставляют деталь Р1 и не
размещаются в Лондоне. Заметьте, что вычитание учитывает порядок следования
точно так же, как и в обычной арифметике (например, "5-2" и "2-5" — это не одно и
то же).
Произведение
В математике декартово произведение (или для краткости произведение) двух
множеств является множеством всех таких упорядоченных пар элементов, что
первый элемент в каждой паре берется из первого множества, а второй элемент в
каждой паре берется из второго множества. Следовательно, декартово произведение
двух отношений должно быть множеством упорядоченных пар кортежей. Но опять-
таки необходимо сохранить свойство замкнутости; иначе говоря, результат должен
содержать кортежи, а не упорядоченные пары кортежей. Поэтому версия декартова
произведения в реляционной алгебре представляет собой расширенную форму
операции, в которой каждая упорядоченная пара кортежей заменяется одним
кортежем, образованным из двух сцепленных кортежей этой пары. "Сцепление"
здесь означает объединение (в смысле теории множеств, а не реляционной алгебры);
т.е. кортежи
Другая проблема, возникающая в связи с декартовым произведением,
заключается в том, что результирующее отношение должно иметь правильно
сформированный заголовок. Очевидно, что заголовок в своей основе представляет
просто сцепление двух заголовков исходных отношений. Следовательно, если эти
два заголовка имеют какие-то общие имена атрибутов, возникает проблема. Если
допустить такую операцию, то результирующий заголовок будет иметь два
одинаковых атрибута, а значит, будет "неверно сформированным". Поэтому, если
нужно построить декартово произведение двух отношений, которые имеют какие-то
общие имена атрибутов, необходимо прежде для переименования соответствующих
атрибутов применить оператор rename.
Итак, декартово произведение двух отношений А и В (A TIMES В), где А и В
не имеют общих имен атрибутов, определяется как отношение с заголовком,
который представляет собой сцепление двух заголовков исходных отношений A и В,
и телом, состоящим из множества всех кортежей t, таких, что t представляет собой
сцепление кортежа а, принадлежащего отношению А, и кортежа b, принадлежащего
отношению В. Обратите внимание, что кардинальное число результата равняется
произведению кардинальных чисел исходных отношений A и B,a степень равняется
сумме их степеней.
Пример. Пусть отношения А и В будут такими, как показано на рис. 6.4
(отношение А представляет, например, номера всех текущих поставщиков, а
отношение В — номера всех текущих деталей). Тогда A times B — это все текущие
пары поставщик-деталь и деталь-поставщик.
Прежде чем завершить обсуждение этой операции, необходимо указать, что на
практике явное использование операции декартова произведения требуется только
для чересчур сложных запросов (см. упражнения и Ответы на них в конце главы).
Другими словами, для реального запроса относительно редко требуется (хотя нельзя
сказать, что вовсе не требуется) использование операции декартова произведения.
Эта операция включена в реляционную алгебру главным образом по
концептуальным соображениям. В частности, как отмечается ниже в этой главе,
декартово произведение требуется как промежуточный шаг при определении
операций θ-соединения (а операция θ-соединения используете довольно часто).
Отметим, Что операция декартова Произведения не очень важна на практике,
потому что после ее выполнения в результате нет никакой дополнительной
информации по сравнению с исходной. В случае, показанном в примере на рис. 6.4,
результат не говорит нам ничего нового — он просто подтверждает, что существуют
номера поставщиков и номера деталей.
B
Несколько синтаксических упрощений
Легко проверить, что операция объединения ассоциативна, т.е. если А, В и С—
произвольные выражения (дающие совместимые по типу отношения), то выражения
(A UNION В) UNION С
и
A UNION (В UNION С)
эквивалентны. Следовательно, для удобства можно разрешить запись
последовательных операторов объединения без использования круглых скобок;
таким образом, предыдущее выражение можно однозначно упростить:
A UNION В UNION С