Главная Обратная связь

Дисциплины:






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



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

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

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

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

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

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

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

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

 

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



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

 

Объединение

 

Объединением двух совместимых по типу отношений А и B (A union B) называется отношение с тем же заголовком, как и в отношениях А и В, и с телом, состоящим из множества всех кортежей t, принадлежащих А или В или обоим отношениям.

Пример. Пусть отношения А или В будут такими, как показано на рис. 6.3 (отношение А представляет поставщиков из Лондона, а отношение В – поставщиков, которые, например, поставляют деталь Р1). Тогда выражение A union B (см. рис. 6. 3,а) представляет поставщиков, которые или размещаются в Лондоне, или поставляют деталь Р1 (либо и то и другое). Обратите внимание, что результат имеет три кортежа, а не четыре – повторяющиеся кортежи удаляются по определению


 

  A         B        
  S# SNAME STATUS CITY   S# SNAME STATUS CITY  
  S1 S4 Smith Clark London London   S1 S2 Smith Jones London Paris  
                     
           
a) Объединение S# SNAME STATUS CITY  
(A UNION B) S1 S4 S2 Smith Clark Jones London London Paris  
           
б) Пересечение (A INSERT B )          
S# SNAME STATUS CITY  
S1 Smith London  
           
в) Вычитание (A MINUS B)     г) Вычитание (В MINUS А)      
  S# SNAME STATUS CITY   S# SNAME STATUS CITY  
  S4 Clark London   S2 Jones Paris  
                     
                                                 

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

 

Замечание. Вопрос удаления дубликатов не возникает в других традиционных операциях над множествами (пересечение, вычитание и произведение). Фактически существует еще только одна операция (помимо объединения), где этот вопрос возникает, - проекция.

 

Пересечение

 

Пересечением двух совместимых по типу отношений А и В (A INTERSECT B) называется отношение с тем же заголовком , как и в отношениях А и В, и с телом, состоящим из множества всех кортежей t, принадлежащих одновременно обоим отношениям А и В.

Пример. Пусть снова отношения А и В будут такими, как показано на рис. 6. 3. Тогда выражение (A INTERSECT B) (см. рис. 6.3,б) представляет поставщиков, которые размещаются в Лондоне и поставляют деталь Р1.


Вычитание

Вычитанием двух совместимых по типу отношений А и В (А minus В) называется от­ношение с тем же заголовком, как и в отношениях А и В, и с телом, состоящим из множества всех кортежей t, принадлежащих отношению А и не принадлежащих от­ношению В.

Пример. Пусть снова отношения А и В будут такими, как показано на рис. 6.3. То­гда выражение А minus В (см. рис. 6.3,в) представляет поставщиков, которые разме­щаются в Лондоне и не поставляют деталь Р1, а в minus а (см. рис. 6.3,г) представляет поставщиков, которые поставляют деталь Р1 и не размещаются в Лондоне. Заметьте, что вычитание учитывает порядок следования точно так же, как и в обычной арифме­тике (например, "5-2" и "2-5" — это не одно и то же).

 

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

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

{ <А1:а1>, <А2:а2>, ..., <Аm:am> }

и

{ <В1:b1>, <В2:Ь2>, ..., <Вn:Ьn> }

(имена атрибутов показаны для определенности) сцепляются в один кортеж

{ <A1 :al>, <A2:a2>, ..., <Am:am>, <В1:b1>, <В2:Ь2>,..., <Вn:Ьn> }

 

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

Итак, декартово произведение двух отношений А и В ( A times в), где А и В не имеют общих имен атрибутов, определяется как отношение с заголовком, ко­торый представляет собой сцепление двух заголовков исходных отношений А и В, и телом, состоящим из множества всех кортежей t, таких, что t представляет собой сцепление кортежа а, принадлежащего отношению А, и кортежа b, принадлежащего отношению В. Обратите внимание, что кардинальное число результата равняется произведению кардинальных чисел исходных отношений А и В, а сте­пень равняется сумме их степеней.

Пример. Пусть отношения А и В будут такими, как показано на рис. 6.4 (отношение А представляет, например, номера всех текущих поставщиков, а отноше­ние В — номера всех текущих деталей). Тогда a times в— это все текущие пары по­ставщик-деталь и деталь-поставщик.

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

 

 

S #   P#   .. ..   .. ..   .. ..   .. ..
S1 S1 S1 S1 S1 S1   P1 P2 P3 P4 P5 P6   S2 S2 S2 S2 S2 S2 P1 P2 P3 P4 P5 P6   S3 S3 S3 S3 S3 S3 P1 P2 P3 P4 P5 P6   S4 S4 S4 S4 S4 S4 P1 P2 P3 P4 P5 P6   S5 S5 S5 S5 S5 S5 P1 P2 P3 P4 P5 P6
..   ..   .. ..   .. ..   .. ..      

 

         
A S# B P#  
  S1 S2 S3 S4 S5   P1 P2 P3 P4 P5 P6  
         
Декартово произведение (A TIMES B)
  S#   P#   ...        
  S1 S1 S1 S1 S1 S1   P1 P2 P3 P4 P5 P6   S2 S2 S2 S2 S2 S2 P1 P2 P3 P4 P5 P6   S3 S3 S3 S3 S3 S3 P1 P2 P3 P4 P5 P6   S4 S4 S4 S4 S4 S4 P1 P2 P3 P4 P5 P6   S5 S5 S5 S5 S5 S5 P1 P2 P3 P4 P5 P6  
                 
                                 
                                         

 

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

 

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

 





sdamzavas.net - 2017 год. Все права принадлежат их авторам! В случае нарушение авторского права, обращайтесь по форме обратной связи...