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

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

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

Традиционные операции над множеством — это объединение, пересечение, вычитание и произведение (точнее, расширенное декартово произведение). Давайте сначала рассмотрим объединение.

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

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

Более точный термин понятия "одна и та же форма" — совместимо по типу. [12][2] Будем говорить, что два отношения совместимы по типу, если у них идентичные заголовки, а точнее,

1) 1) если каждое из них имеет одно и то же множество имен атрибутов (следовательно, заметьте, они заведомо должны иметь одну и ту же степень);

2) 2) если соответствующие атрибуты (т.е. атрибуты с теми же самыми именами в двух отношениях) определены на одном и том же домене.

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

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

Объединение

Объединением двух совместимых по типу отношений А и В (A UNION B) называется отношение с тем же заголовком, как и в отношениях А и В, и с телом, состоящим из множества всех кортежей 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, результат не говорит нам ничего нового — он просто подтверждает, что существуют номера поставщиков и номера деталей.