Реляционная алгебра: соединения, деление — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Соединения)
м (rollbackEdits.php mass rollback)
 
(не показано 7 промежуточных версий 2 участников)
Строка 3: Строка 3:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Соединение''' (англ. ''Join'') — общее наименование для бинарных операторов на отношениях, позволяющих некоторым образом соединить данные из нескольких отношений в одно.
+
'''Соединение''' (англ. ''Join'') — общее наименование для бинарных операторов на отношениях, позволяющих некоторым образом соединить данные из двух отношений в одно.
 
}}
 
}}
 
==Полное соединение==
 
==Полное соединение==
Строка 279: Строка 279:
  
 
* <tex>R_1 \, ⟕ \, R_2 = (R_1 \Join R_2) \cup (R_1 \setminus \pi_{R_1}(R_1 \Join R_2))</tex>
 
* <tex>R_1 \, ⟕ \, R_2 = (R_1 \Join R_2) \cup (R_1 \setminus \pi_{R_1}(R_1 \Join R_2))</tex>
 +
** ''Замечание 1.'' <tex>R_1 \setminus \pi_{R_1}(R_1 \Join R_2)</tex> — это и есть кортежи из <tex>R_1</tex>, которым не соответствует ни один кортеж из <tex>R_2</tex>
 +
** ''Замечание 2.'' Множество атрибутов у <tex>R_1 \Join R_2</tex> есть надмножество атрибутов у <tex>R_1 \setminus \pi_{R_1}(R_1 \Join R_2)</tex>. Подразумевается, что у <tex>R_1 \setminus \pi_{R_1}(R_1 \Join R_2)</tex> недостающие атрибуты дополняются значениями <tex>null</tex>, чтобы операция объединения была определена
 
* <tex>R_1 \, ⟖ \, R_2 = (R_1 \Join R_2) \cup (R_2 \setminus \pi_{R_2}(R_1 \Join R_2))</tex>
 
* <tex>R_1 \, ⟖ \, R_2 = (R_1 \Join R_2) \cup (R_2 \setminus \pi_{R_2}(R_1 \Join R_2))</tex>
 
* <tex>R_1 \, ⟗ \, R_2 = (R_1 \Join R_2) \cup (R_1 \setminus \pi_{R_1}(R_1 \Join R_2)) \cup (R_2 \setminus \pi_{R_2}(R_1 \Join R_2))</tex>
 
* <tex>R_1 \, ⟗ \, R_2 = (R_1 \Join R_2) \cup (R_1 \setminus \pi_{R_1}(R_1 \Join R_2)) \cup (R_2 \setminus \pi_{R_2}(R_1 \Join R_2))</tex>
Строка 363: Строка 365:
 
* <tex>R_1 \ltimes R_2 = R_2 \rtimes R_1</tex>
 
* <tex>R_1 \ltimes R_2 = R_2 \rtimes R_1</tex>
  
Из соответствующих свойств внешних соединений следует:
+
Подставив <tex>R_1 \ltimes R_2</tex> и <tex>R_1 \rtimes R_2</tex> в соответствующие свойства <tex>R_1 \, ⟕ \, R_2</tex> и <tex>R_1 \, ⟖ \, R_2</tex>, получим:
  
 
* <tex>R_1 \, ⟕ \, R_2 = (R_1 \Join R_2) \cup (R_1 \setminus (R_1 \ltimes R_2))</tex>
 
* <tex>R_1 \, ⟕ \, R_2 = (R_1 \Join R_2) \cup (R_1 \setminus (R_1 \ltimes R_2))</tex>
Строка 377: Строка 379:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Левым условным соединением''' (англ. ''Left conditional join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex>, у которых нет общих атрибутов, по условию <tex>\theta</tex> называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а кортежами тела являются всевозможные конкатенации кортежей тел <tex>R_1</tex> и <tex>R_2</tex>, удовлетворяющих условию <tex>\theta</tex>. Если в результате кортежу из <tex>R_1</tex> не соответствует ни одного кортежа из <tex>R_2</tex>, то в результат добавляется этот кортеж из <tex>R_1</tex>, дополненный пустыми значениями. Обозначение: <tex>R_1 ⟕_{\theta} R_2</tex>
+
'''Левым условным соединением''' (англ. ''Left conditional join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex>, у которых нет общих атрибутов, по условию <tex>\theta</tex> называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а кортежами тела являются всевозможные конкатенации кортежей тел <tex>R_1</tex> и <tex>R_2</tex>, удовлетворяющих условию <tex>\theta</tex>. Если в результате кортежу из <tex>R_1</tex> не соответствует ни одного кортежа из <tex>R_2</tex>, то в результат добавляется этот кортеж из <tex>R_1</tex>, дополненный пустыми значениями. Обозначение: <tex>R_1 \, ⟕_{\theta} \, R_2</tex>
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Правым условным соединением''' (англ. ''Right conditional join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex>, у которых нет общих атрибутов, по условию <tex>\theta</tex> называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а кортежами тела являются всевозможные конкатенации кортежей тел <tex>R_1</tex> и <tex>R_2</tex>, удовлетворяющих условию <tex>\theta</tex>. Если в результате кортежу из <tex>R_2</tex> не соответствует ни одного кортежа из <tex>R_1</tex>, то в результат добавляется этот кортеж из <tex>R_2</tex>, дополненный пустыми значениями. Обозначение: <tex>R_1 ⟖_{\theta} R_2</tex>
+
'''Правым условным соединением''' (англ. ''Right conditional join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex>, у которых нет общих атрибутов, по условию <tex>\theta</tex> называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а кортежами тела являются всевозможные конкатенации кортежей тел <tex>R_1</tex> и <tex>R_2</tex>, удовлетворяющих условию <tex>\theta</tex>. Если в результате кортежу из <tex>R_2</tex> не соответствует ни одного кортежа из <tex>R_1</tex>, то в результат добавляется этот кортеж из <tex>R_2</tex>, дополненный пустыми значениями. Обозначение: <tex>R_1 \, ⟖_{\theta} \, R_2</tex>
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Внешним условным соединением''' (англ. ''Outer conditional join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex>, у которых нет общих атрибутов, по условию <tex>\theta</tex> называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а кортежами тела являются всевозможные конкатенации кортежей тел <tex>R_1</tex> и <tex>R_2</tex>, удовлетворяющих условию <tex>\theta</tex>. Если в результате кортежу из одного отношения не соответствует ни одного кортежа из другого, то в результат добавляется этот кортеж, дополненный пустыми значениями. Обозначение: <tex>R_1 ⟗_{\theta} R_2</tex>
+
'''Внешним условным соединением''' (англ. ''Outer conditional join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex>, у которых нет общих атрибутов, по условию <tex>\theta</tex> называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а кортежами тела являются всевозможные конкатенации кортежей тел <tex>R_1</tex> и <tex>R_2</tex>, удовлетворяющих условию <tex>\theta</tex>. Если в результате кортежу из одного отношения не соответствует ни одного кортежа из другого, то в результат добавляется этот кортеж, дополненный пустыми значениями. Обозначение: <tex>R_1 \, ⟗_{\theta} \, R_2</tex>
 
}}
 
}}
 
===Пример===
 
===Пример===
Строка 419: Строка 421:
 
|Плюшкин
 
|Плюшкин
 
|}
 
|}
Тогда <tex>R_1 ⟕_{\text{length(FirstName)}+2<\text{length(LastName)}} R_2</tex> равно:
+
Тогда <tex>R_1 \, ⟕_{\text{length(FirstName)}+2<\text{length(LastName)}} \, R_2</tex> равно:
 
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
 
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
 
!'''Id1'''
 
!'''Id1'''
Строка 457: Строка 459:
  
 
* <tex>R_1 \times_{\theta} R_2 = \sigma_{\theta}(R_1 \times R_2)</tex>
 
* <tex>R_1 \times_{\theta} R_2 = \sigma_{\theta}(R_1 \times R_2)</tex>
* <tex>R_1 ⟕_{\theta} R_2 = J \cup (R_1 \setminus \pi_{R_1}(J))</tex>, где <tex>J = \sigma_{\theta}(R_1 \times R_2)</tex>
+
* <tex>R_1 \, ⟕_{\theta} \, R_2 = J \cup (R_1 \setminus \pi_{R_1}(J))</tex>, где <tex>J = \sigma_{\theta}(R_1 \times R_2)</tex>
* <tex>R_1 ⟖_{\theta} R_2 = J \cup (R_2 \setminus \pi_{R_2}(J))</tex>, где <tex>J = \sigma_{\theta}(R_1 \times R_2)</tex>
+
* <tex>R_1 \, ⟖_{\theta} \, R_2 = J \cup (R_2 \setminus \pi_{R_2}(J))</tex>, где <tex>J = \sigma_{\theta}(R_1 \times R_2)</tex>
* <tex>R_1 ⟗_{\theta} R_2 = J \cup (R_1 \setminus \pi_{R_1}(J)) \cup (R_2 \setminus \pi_{R_2}(J))</tex>, где <tex>J = \sigma_{\theta}(R_1 \times R_2)</tex>
+
* <tex>R_1 \, ⟗_{\theta} \, R_2 = J \cup (R_1 \setminus \pi_{R_1}(J)) \cup (R_2 \setminus \pi_{R_2}(J))</tex>, где <tex>J = \sigma_{\theta}(R_1 \times R_2)</tex>
  
 
Из свойств выше нетрудно вывести:
 
Из свойств выше нетрудно вывести:
  
* <tex>R_1 ⟕_{\theta} R_2 = R_2 ⟖_{\theta} R_1</tex>
+
* <tex>R_1 \, ⟕_{\theta} \, R_2 = R_2 \, ⟖_{\theta} \, R_1</tex>
* <tex>R_1 ⟗_{\theta} R_2 = (R_1 ⟕_{\theta} R_2) \cup (R_1 ⟖_{\theta} R_2)</tex>
+
* <tex>R_1 \, ⟗_{\theta} \, R_2 = (R_1 \, ⟕_{\theta} \, R_2) \cup (R_1 \, ⟖_{\theta} \, R_2)</tex>
  
 
=Деление=
 
=Деление=
Строка 470: Строка 472:
 
==Деление==
 
==Деление==
  
'''TODO'''
+
{{Определение
 +
|definition=
 +
Пусть даны отношения <tex>A</tex> с заголовком <tex>X \cup Y</tex> и отношение <tex>B</tex> с заголовком <tex>Y</tex>. Тогда '''делением''' (англ. ''Division'') <tex>A</tex> на <tex>B</tex> называется максимальное по включению отношение <tex>C</tex> с заголовком <tex>X</tex>, такое что <tex>B \times C \subseteq A</tex>. Обозначение: <tex>A \div B</tex>
 +
}}
 +
Определение деления в реляционной алгебре хорошо перекликается с определением деления с остатком в арифметике: ''«Частным от деления целого числа <tex>a</tex> на натуральное число <tex>b</tex> называется максимальное целое <tex>c</tex>, такое что <tex>bc \leq a</tex>.»''
 +
 
 +
===Пример===
 +
 
 +
Рассмотрим следующие отношения, <tex>A</tex> и <tex>B</tex> соответственно:
 +
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
 +
!'''Id'''
 +
!'''FirstName'''
 +
|-
 +
|1
 +
|Иван
 +
|-
 +
|2
 +
|Иван
 +
|-
 +
|1
 +
|Пётр
 +
|-
 +
|2
 +
|Пётр
 +
|-
 +
|3
 +
|Пётр
 +
|-
 +
|1
 +
|Сидор
 +
|-
 +
|3
 +
|Сидор
 +
|}
 +
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
 +
!'''Id'''
 +
|-
 +
|1
 +
|-
 +
|2
 +
|}
 +
Тогда результатом деления <tex>A</tex> на <tex>B</tex> будут такие имена (FirstName), которые в отношении <tex>A</tex> ассоциированы и с <tex>Id = 1</tex>, и с <tex>Id = 2</tex>. Итого получим:
 +
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
 +
!'''FirstName'''
 +
|-
 +
|Иван
 +
|-
 +
|Пётр
 +
|}
 +
 
 +
===Свойства===
 +
 
 +
* <tex>A \div B = \{x \in \pi_X(A) \, | \, \forall y \in B: \,\, (x, y) \in A\}</tex> — интерпретация определения на языке кванторов
 +
* <tex>A \div B = \pi_X(A) \setminus \pi_X(\pi_X(A) \times B \setminus A)</tex> — выражение деления через простейшие операции реляционной алгебры
 +
** ''Объяснение.'' <tex>\pi_X(A) \times B \setminus A</tex>  это все такие пары <tex>(x, y) \in X \times Y</tex>, что <tex>x \in \pi_X(A)</tex>, но <tex>(x, y) \notin A</tex>.
 +
** Тогда <tex>\pi_X(\pi_X(A) \times B \setminus A)</tex> — это все <tex>x \in \pi_X(A)</tex>, такие что <tex>\{x\} \times B \not\subseteq A</tex>.
 +
** Тогда <tex>\pi_X(A) \setminus \pi_X(\pi_X(A) \times B \setminus A)</tex> — это максимальное по включению <tex>C \subseteq \pi_X(A)</tex>, что <tex>C \times B \subseteq A</tex> — то есть, в точности результат деления <tex>A</tex> на <tex>B</tex> по определению
  
 
==Большое деление==
 
==Большое деление==
  
'''TODO'''
+
{{Определение
 +
|definition=
 +
Пусть даны отношения <tex>A</tex> с заголовком <tex>X \cup Y</tex> и отношение <tex>B</tex> с заголовком <tex>Y \cup Z \,\,\,\, (X \cap Z = \varnothing)</tex>. Тогда '''большим делением''' (англ. ''Great division'') <tex>A</tex> на <tex>B</tex> называется максимальное по включению отношение с заголовком <tex>X \cup Z</tex>, такое что для каждого <tex>(x, z) \in X \times Z</tex> верно <tex>\{x\} \times \pi_Y(\sigma_{Z=z}(B)) \subseteq A</tex>. Обозначение: <tex>A ⋇ B</tex>
 +
}}
 +
===Пример===
 +
 
 +
Рассмотрим следующие отношения, <tex>A</tex> и <tex>B</tex> соответственно:
 +
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
 +
!'''Id'''
 +
!'''FirstName'''
 +
|-
 +
|1
 +
|Иван
 +
|-
 +
|2
 +
|Иван
 +
|-
 +
|1
 +
|Пётр
 +
|-
 +
|2
 +
|Пётр
 +
|-
 +
|3
 +
|Пётр
 +
|-
 +
|1
 +
|Сидор
 +
|-
 +
|3
 +
|Сидор
 +
|}
 +
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
 +
!'''Id'''
 +
!'''LastName'''
 +
|-
 +
|1
 +
|Иванов
 +
|-
 +
|2
 +
|Иванов
 +
|-
 +
|1
 +
|Петров
 +
|-
 +
|3
 +
|Сидоров
 +
|}
 +
Тогда результатом большого деления <tex>A</tex> на <tex>B</tex> будет:
 +
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
 +
!'''FirstName'''
 +
!'''LastName'''
 +
|-
 +
|Иван
 +
|Иванов
 +
|-
 +
|Иван
 +
|Петров
 +
|-
 +
|Пётр
 +
|Иванов
 +
|-
 +
|Пётр
 +
|Петров
 +
|-
 +
|Пётр
 +
|Сидоров
 +
|-
 +
|Сидор
 +
|Петров
 +
|-
 +
|Сидор
 +
|Сидоров
 +
|}
 +
''Объяснение.'' Чтобы найти результат большого деления, переберём всевозможные <tex>(x, z) \in X \times Z</tex>. В нашем случае <tex>X = \{(Иван), (Пётр), (Сидор)\}, Z = \{(Иванов), (Петров), (Сидоров)\}</tex>.
 +
 
 +
Возьмём <tex>(x, z) = (Иван, Иванов)</tex>. Тогда <tex>\pi_Y(\sigma_{Z=Иванов}(B)) = \{(1), (2)\}</tex>. Тогда <tex>\{Иван\} \times \pi_Y(\sigma_{Z=Иванов}(B)) = \{(1, Иван), (2, Иван)\}</tex>, что является подмножеством <tex>A</tex>. Значит, <tex>(Иван, Иванов)</tex> есть в результате большого деления.
 +
 
 +
Возьмём <tex>(x, z) = (Иван, Петров)</tex>. Тогда <tex>\pi_Y(\sigma_{Z=Петров}(B)) = \{(1)\}</tex>. Тогда <tex>\{Иван\} \times \pi_Y(\sigma_{Z=Петров}(B)) = \{(1, Иван)\}</tex>, что является подмножеством <tex>A</tex>. Значит, <tex>(Иван, Петров)</tex> есть в результате большого деления.
 +
 
 +
Возьмём <tex>(x, z) = (Иван, Сидоров)</tex>. Тогда <tex>\pi_Y(\sigma_{Z=Сидоров}(B)) = \{(3)\}</tex>. Тогда <tex>\{Иван\} \times \pi_Y(\sigma_{Z=Сидоров}(B)) = \{(3, Иван)\}</tex>, что '''не''' является подмножеством <tex>A</tex>. Значит, элемента <tex>(Иван, Сидоров)</tex> нет в результате большого деления.
 +
 
 +
Аналогично перебираются 6 оставшихся элементов <tex>X \times Z</tex>.
 +
 
 +
===Свойства===
 +
 
 +
* <tex>A ⋇ B = \{(x, z) \in \pi_X(A) \times \pi_Z(B) \, | \, \forall y \in \pi_Y(\sigma_{Z=z}(B)): \,\, (x, y) \in A\}</tex> — интерпретация определения на языке кванторов
 +
* Если <tex>C = A ⋇ B</tex>, то для каждого <tex>z \in Z</tex> верно <tex>\pi_X(\sigma_{Z=z}(C)) = A \div \pi_Y(\sigma_{Z=z}(B))</tex> — интерпретация большого деления как "деление для каждого <tex>z</tex>"
 +
* <tex>A ⋇ B = \pi_X(A) \times \pi_Z(B) \setminus \pi_{XZ}(\pi_X(A) \times B \setminus A \Join B)</tex> — выражение большого деления через простейшие операции реляционной алгебры
  
 
=Литература=
 
=Литература=

Текущая версия на 19:41, 4 сентября 2022

Соединения

Определение:
Соединение (англ. Join) — общее наименование для бинарных операторов на отношениях, позволяющих некоторым образом соединить данные из двух отношений в одно.

Полное соединение

Определение:
Полным, или декартовым соединением (англ. Cross join, Cartesian join) двух отношений [math]R_1[/math] и [math]R_2[/math], у которых нет общих атрибутов, называется отношение, в котором заголовок является объединением заголовков [math]R_1[/math] и [math]R_2[/math], а тело — декартовым произведением тел [math]R_1[/math] и [math]R_2[/math]. Обозначение: [math]R_1 \times R_2[/math]

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

Пример

Рассмотрим два отношения:

Id1 FirstName
1 Иван
2 Пётр
3 Сидор
Id2 LastName
1 Иванов
3 Петров
4 Сидоров

Их полным соединением будет следующее отношение:

Id1 FirstName Id2 LastName
1 Иван 1 Иванов
1 Иван 3 Петров
1 Иван 4 Сидоров
2 Пётр 1 Иванов
2 Пётр 3 Петров
2 Пётр 4 Сидоров
3 Сидор 1 Иванов
3 Сидор 3 Петров
3 Сидор 4 Сидоров

Естественное соединение

Определение:
Естественным соединением (англ. Natural join) двух отношений [math]R_1[/math] и [math]R_2[/math] называется отношение, в котором заголовок является объединением заголовков [math]R_1[/math] и [math]R_2[/math], а тело состоит из кортежей, полученных всевозможными соединениями кортежей [math]R_1[/math] и [math]R_2[/math], имеющих равные значения одноимённых атрибутов. Обозначение: [math]R_1 \Join R_2[/math]

Пример

Рассмотрим два отношения:

Id FirstName
1 Иван
2 Пётр
3 Сидор
Id LastName
1 Иванов
1 Петров
2 Сидоров

Их естественным соединением будет следующее отношение:

Id FirstName LastName
1 Иван Иванов
1 Иван Петров
2 Пётр Сидоров

Свойства

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

  • Если [math]|R_1| = m[/math] и [math]|R_2| = n[/math], то [math]0 \leq |R_1 \Join R_2| \leq mn[/math].
    • [math]|R_1 \Join R_2| = 0[/math] достигается, если у общих атрибутов в [math]R_1[/math] и [math]R_2[/math] нет равных значений
    • [math]|R_1 \Join R_2| = mn[/math] достигается, в частности, при отсутствии общих атрибутов у [math]R_1[/math] и [math]R_2[/math] (в такой ситуации естественное соединение совпадает с полным: [math]R_1 \Join R_2 = R_1 \times R_2[/math])

Внешние соединения

Определение:
Левым соединением (англ. Left join или Left outer join) двух отношений [math]R_1[/math] и [math]R_2[/math] называется отношение, в котором заголовок является объединением заголовков [math]R_1[/math] и [math]R_2[/math], а тело состоит из кортежей, полученных всевозможными соединениями кортежей [math]R_1[/math] и [math]R_2[/math], имеющих равные значения одноимённых атрибутов. Если по одноимённым атрибутам кортежу из [math]R_1[/math] не соответствует ни одного кортежа из [math]R_2[/math], то в результат добавляется этот кортеж из [math]R_1[/math], дополненный пустыми значениями. Обозначение: [math]R_1 \, ⟕ \, R_2[/math]


Определение:
Правым соединением (англ. Right join или Right outer join) двух отношений [math]R_1[/math] и [math]R_2[/math] называется отношение, в котором заголовок является объединением заголовков [math]R_1[/math] и [math]R_2[/math], а тело состоит из кортежей, полученных всевозможными соединениями кортежей [math]R_1[/math] и [math]R_2[/math], имеющих равные значения одноимённых атрибутов. Если по одноимённым атрибутам кортежу из [math]R_2[/math] не соответствует ни одного кортежа из [math]R_1[/math], то в результат добавляется этот кортеж из [math]R_2[/math], дополненный пустыми значениями. Обозначение: [math]R_1 \, ⟖ \, R_2[/math]


Определение:
Внешним соединением (англ. Outer join или Full outer join) двух отношений [math]R_1[/math] и [math]R_2[/math] называется отношение, в котором заголовок является объединением заголовков [math]R_1[/math] и [math]R_2[/math], а тело состоит из кортежей, полученных всевозможными соединениями кортежей [math]R_1[/math] и [math]R_2[/math], имеющих равные значения одноимённых атрибутов. Если по одноимённым атрибутам кортежу из одного отношения не соответствует ни одного кортежа из другого, то в результат добавляется этот кортеж, дополненный пустыми значениями. Обозначение: [math]R_1 \, ⟗ \, R_2[/math]

Пример

Рассмотрим два отношения ([math]R_1[/math] и [math]R_2[/math] соответственно):

Id FirstName
1 Иван
2 Пётр
3 Сидор
Id LastName
1 Иванов
1 Петров
3 Сидоров
4 Плюшкин

Тогда [math]R_1 \, ⟕ \, R_2[/math] (левое соединение) равно:

Id FirstName LastName
1 Иван Иванов
1 Иван Петров
2 Пётр
3 Сидор Сидоров

[math]R_1 \, ⟖ \, R_2[/math] (правое соединение) равно:

Id FirstName LastName
1 Иван Иванов
1 Иван Петров
3 Сидор Сидоров
4 Плюшкин

[math]R_1 \, ⟗ \, R_2[/math] (внешнее соединение) равно:

Id FirstName LastName
1 Иван Иванов
1 Иван Петров
2 Пётр
3 Сидор Сидоров
4 Плюшкин

Свойства

Непосредственно из определений вытекают следующие свойства:

  • [math]R_1 \, ⟕ \, R_2 = (R_1 \Join R_2) \cup (R_1 \setminus \pi_{R_1}(R_1 \Join R_2))[/math]
    • Замечание 1. [math]R_1 \setminus \pi_{R_1}(R_1 \Join R_2)[/math] — это и есть кортежи из [math]R_1[/math], которым не соответствует ни один кортеж из [math]R_2[/math]
    • Замечание 2. Множество атрибутов у [math]R_1 \Join R_2[/math] есть надмножество атрибутов у [math]R_1 \setminus \pi_{R_1}(R_1 \Join R_2)[/math]. Подразумевается, что у [math]R_1 \setminus \pi_{R_1}(R_1 \Join R_2)[/math] недостающие атрибуты дополняются значениями [math]null[/math], чтобы операция объединения была определена
  • [math]R_1 \, ⟖ \, R_2 = (R_1 \Join R_2) \cup (R_2 \setminus \pi_{R_2}(R_1 \Join R_2))[/math]
  • [math]R_1 \, ⟗ \, R_2 = (R_1 \Join R_2) \cup (R_1 \setminus \pi_{R_1}(R_1 \Join R_2)) \cup (R_2 \setminus \pi_{R_2}(R_1 \Join R_2))[/math]

Из этих свойств, в свою очередь, следует:

  • [math]R_1 \, ⟕ \, R_2 = R_2 \, ⟖ \, R_1[/math]
  • [math]R_1 \, ⟗ \, R_2 = (R_1 \, ⟕ \, R_2) \cup (R_1 \, ⟖ \, R_2)[/math]

Полусоединения

Определение:
Левым полусоединением (англ. Left semijoin) двух отношений [math]R_1[/math] и [math]R_2[/math] называется отношение, в котором заголовок равен заголовку [math]R_1[/math], а тело состоит из кортежей в [math]R_1[/math], для которых существует кортеж из [math]R_2[/math] с равными значениями одноимённых атрибутов. Обозначение: [math]R_1 \ltimes R_2[/math]


Определение:
Правым полусоединением (англ. Right semijoin) двух отношений [math]R_1[/math] и [math]R_2[/math] называется отношение, в котором заголовок равен заголовку [math]R_2[/math], а тело состоит из кортежей в [math]R_2[/math], для которых существует кортеж из [math]R_1[/math] с равными значениями одноимённых атрибутов. Обозначение: [math]R_1 \rtimes R_2[/math]

Пример

Рассмотрим два отношения ([math]R_1[/math] и [math]R_2[/math] соответственно):

Id FirstName
1 Иван
2 Пётр
3 Сидор
Id LastName
1 Иванов
1 Петров
3 Сидоров
4 Плюшкин

Тогда [math]R_1 \ltimes R_2[/math] (левое полусоединение) равно:

Id FirstName
1 Иван
3 Сидор

[math]R_1 \rtimes R_2[/math] (правое полусоединение) равно:

Id LastName
1 Иванов
1 Петров
3 Сидоров

Свойства

Из определения следует:

  • [math]R_1 \ltimes R_2 = \pi_{R_1}(R_1 \Join R_2)[/math]
  • [math]R_1 \rtimes R_2 = \pi_{R_2}(R_1 \Join R_2)[/math]
  • [math]R_1 \ltimes R_2 = R_2 \rtimes R_1[/math]

Подставив [math]R_1 \ltimes R_2[/math] и [math]R_1 \rtimes R_2[/math] в соответствующие свойства [math]R_1 \, ⟕ \, R_2[/math] и [math]R_1 \, ⟖ \, R_2[/math], получим:

  • [math]R_1 \, ⟕ \, R_2 = (R_1 \Join R_2) \cup (R_1 \setminus (R_1 \ltimes R_2))[/math]
  • [math]R_1 \, ⟖ \, R_2 = (R_1 \Join R_2) \cup (R_2 \setminus (R_1 \rtimes R_2))[/math]
  • [math]R_1 \, ⟗ \, R_2 = (R_1 \Join R_2) \cup (R_1 \setminus (R_1 \ltimes R_2)) \cup (R_2 \setminus (R_1 \rtimes R_2))[/math]

Условные соединения

Определение:
Условным соединением (англ. Conditional join) двух отношений [math]R_1[/math] и [math]R_2[/math], у которых нет общих атрибутов, по условию [math]\theta[/math] называется отношение, в котором заголовок является объединением заголовков [math]R_1[/math] и [math]R_2[/math], а кортежами тела являются всевозможные конкатенации кортежей тел [math]R_1[/math] и [math]R_2[/math], удовлетворяющих условию [math]\theta[/math]. Обозначение: [math]R_1 \times_{\theta} R_2[/math]


Определение:
Левым условным соединением (англ. Left conditional join) двух отношений [math]R_1[/math] и [math]R_2[/math], у которых нет общих атрибутов, по условию [math]\theta[/math] называется отношение, в котором заголовок является объединением заголовков [math]R_1[/math] и [math]R_2[/math], а кортежами тела являются всевозможные конкатенации кортежей тел [math]R_1[/math] и [math]R_2[/math], удовлетворяющих условию [math]\theta[/math]. Если в результате кортежу из [math]R_1[/math] не соответствует ни одного кортежа из [math]R_2[/math], то в результат добавляется этот кортеж из [math]R_1[/math], дополненный пустыми значениями. Обозначение: [math]R_1 \, ⟕_{\theta} \, R_2[/math]


Определение:
Правым условным соединением (англ. Right conditional join) двух отношений [math]R_1[/math] и [math]R_2[/math], у которых нет общих атрибутов, по условию [math]\theta[/math] называется отношение, в котором заголовок является объединением заголовков [math]R_1[/math] и [math]R_2[/math], а кортежами тела являются всевозможные конкатенации кортежей тел [math]R_1[/math] и [math]R_2[/math], удовлетворяющих условию [math]\theta[/math]. Если в результате кортежу из [math]R_2[/math] не соответствует ни одного кортежа из [math]R_1[/math], то в результат добавляется этот кортеж из [math]R_2[/math], дополненный пустыми значениями. Обозначение: [math]R_1 \, ⟖_{\theta} \, R_2[/math]


Определение:
Внешним условным соединением (англ. Outer conditional join) двух отношений [math]R_1[/math] и [math]R_2[/math], у которых нет общих атрибутов, по условию [math]\theta[/math] называется отношение, в котором заголовок является объединением заголовков [math]R_1[/math] и [math]R_2[/math], а кортежами тела являются всевозможные конкатенации кортежей тел [math]R_1[/math] и [math]R_2[/math], удовлетворяющих условию [math]\theta[/math]. Если в результате кортежу из одного отношения не соответствует ни одного кортежа из другого, то в результат добавляется этот кортеж, дополненный пустыми значениями. Обозначение: [math]R_1 \, ⟗_{\theta} \, R_2[/math]

Пример

Рассмотрим два отношения ([math]R_1[/math] и [math]R_2[/math] соответственно):

Id1 FirstName
1 Иван
2 Пётр
3 Сидор
Id2 LastName
1 Иванов
1 Петров
3 Сидоров
4 Плюшкин

Тогда [math]R_1 \, ⟕_{\text{length(FirstName)}+2\lt \text{length(LastName)}} \, R_2[/math] равно:

Id1 FirstName Id2 LastName
1 Иван 3 Сидоров
1 Иван 4 Плюшкин
2 Пётр 3 Сидоров
2 Пётр 4 Плюшкин
3 Сидор

Свойства

Из определений следует:

  • [math]R_1 \times_{\theta} R_2 = \sigma_{\theta}(R_1 \times R_2)[/math]
  • [math]R_1 \, ⟕_{\theta} \, R_2 = J \cup (R_1 \setminus \pi_{R_1}(J))[/math], где [math]J = \sigma_{\theta}(R_1 \times R_2)[/math]
  • [math]R_1 \, ⟖_{\theta} \, R_2 = J \cup (R_2 \setminus \pi_{R_2}(J))[/math], где [math]J = \sigma_{\theta}(R_1 \times R_2)[/math]
  • [math]R_1 \, ⟗_{\theta} \, R_2 = J \cup (R_1 \setminus \pi_{R_1}(J)) \cup (R_2 \setminus \pi_{R_2}(J))[/math], где [math]J = \sigma_{\theta}(R_1 \times R_2)[/math]

Из свойств выше нетрудно вывести:

  • [math]R_1 \, ⟕_{\theta} \, R_2 = R_2 \, ⟖_{\theta} \, R_1[/math]
  • [math]R_1 \, ⟗_{\theta} \, R_2 = (R_1 \, ⟕_{\theta} \, R_2) \cup (R_1 \, ⟖_{\theta} \, R_2)[/math]

Деление

Деление

Определение:
Пусть даны отношения [math]A[/math] с заголовком [math]X \cup Y[/math] и отношение [math]B[/math] с заголовком [math]Y[/math]. Тогда делением (англ. Division) [math]A[/math] на [math]B[/math] называется максимальное по включению отношение [math]C[/math] с заголовком [math]X[/math], такое что [math]B \times C \subseteq A[/math]. Обозначение: [math]A \div B[/math]

Определение деления в реляционной алгебре хорошо перекликается с определением деления с остатком в арифметике: «Частным от деления целого числа [math]a[/math] на натуральное число [math]b[/math] называется максимальное целое [math]c[/math], такое что [math]bc \leq a[/math]

Пример

Рассмотрим следующие отношения, [math]A[/math] и [math]B[/math] соответственно:

Id FirstName
1 Иван
2 Иван
1 Пётр
2 Пётр
3 Пётр
1 Сидор
3 Сидор
Id
1
2

Тогда результатом деления [math]A[/math] на [math]B[/math] будут такие имена (FirstName), которые в отношении [math]A[/math] ассоциированы и с [math]Id = 1[/math], и с [math]Id = 2[/math]. Итого получим:

FirstName
Иван
Пётр

Свойства

  • [math]A \div B = \{x \in \pi_X(A) \, | \, \forall y \in B: \,\, (x, y) \in A\}[/math] — интерпретация определения на языке кванторов
  • [math]A \div B = \pi_X(A) \setminus \pi_X(\pi_X(A) \times B \setminus A)[/math] — выражение деления через простейшие операции реляционной алгебры
    • Объяснение. [math]\pi_X(A) \times B \setminus A[/math] это все такие пары [math](x, y) \in X \times Y[/math], что [math]x \in \pi_X(A)[/math], но [math](x, y) \notin A[/math].
    • Тогда [math]\pi_X(\pi_X(A) \times B \setminus A)[/math] — это все [math]x \in \pi_X(A)[/math], такие что [math]\{x\} \times B \not\subseteq A[/math].
    • Тогда [math]\pi_X(A) \setminus \pi_X(\pi_X(A) \times B \setminus A)[/math] — это максимальное по включению [math]C \subseteq \pi_X(A)[/math], что [math]C \times B \subseteq A[/math] — то есть, в точности результат деления [math]A[/math] на [math]B[/math] по определению

Большое деление

Определение:
Пусть даны отношения [math]A[/math] с заголовком [math]X \cup Y[/math] и отношение [math]B[/math] с заголовком [math]Y \cup Z \,\,\,\, (X \cap Z = \varnothing)[/math]. Тогда большим делением (англ. Great division) [math]A[/math] на [math]B[/math] называется максимальное по включению отношение с заголовком [math]X \cup Z[/math], такое что для каждого [math](x, z) \in X \times Z[/math] верно [math]\{x\} \times \pi_Y(\sigma_{Z=z}(B)) \subseteq A[/math]. Обозначение: [math]A ⋇ B[/math]

Пример

Рассмотрим следующие отношения, [math]A[/math] и [math]B[/math] соответственно:

Id FirstName
1 Иван
2 Иван
1 Пётр
2 Пётр
3 Пётр
1 Сидор
3 Сидор
Id LastName
1 Иванов
2 Иванов
1 Петров
3 Сидоров

Тогда результатом большого деления [math]A[/math] на [math]B[/math] будет:

FirstName LastName
Иван Иванов
Иван Петров
Пётр Иванов
Пётр Петров
Пётр Сидоров
Сидор Петров
Сидор Сидоров

Объяснение. Чтобы найти результат большого деления, переберём всевозможные [math](x, z) \in X \times Z[/math]. В нашем случае [math]X = \{(Иван), (Пётр), (Сидор)\}, Z = \{(Иванов), (Петров), (Сидоров)\}[/math].

Возьмём [math](x, z) = (Иван, Иванов)[/math]. Тогда [math]\pi_Y(\sigma_{Z=Иванов}(B)) = \{(1), (2)\}[/math]. Тогда [math]\{Иван\} \times \pi_Y(\sigma_{Z=Иванов}(B)) = \{(1, Иван), (2, Иван)\}[/math], что является подмножеством [math]A[/math]. Значит, [math](Иван, Иванов)[/math] есть в результате большого деления.

Возьмём [math](x, z) = (Иван, Петров)[/math]. Тогда [math]\pi_Y(\sigma_{Z=Петров}(B)) = \{(1)\}[/math]. Тогда [math]\{Иван\} \times \pi_Y(\sigma_{Z=Петров}(B)) = \{(1, Иван)\}[/math], что является подмножеством [math]A[/math]. Значит, [math](Иван, Петров)[/math] есть в результате большого деления.

Возьмём [math](x, z) = (Иван, Сидоров)[/math]. Тогда [math]\pi_Y(\sigma_{Z=Сидоров}(B)) = \{(3)\}[/math]. Тогда [math]\{Иван\} \times \pi_Y(\sigma_{Z=Сидоров}(B)) = \{(3, Иван)\}[/math], что не является подмножеством [math]A[/math]. Значит, элемента [math](Иван, Сидоров)[/math] нет в результате большого деления.

Аналогично перебираются 6 оставшихся элементов [math]X \times Z[/math].

Свойства

  • [math]A ⋇ B = \{(x, z) \in \pi_X(A) \times \pi_Z(B) \, | \, \forall y \in \pi_Y(\sigma_{Z=z}(B)): \,\, (x, y) \in A\}[/math] — интерпретация определения на языке кванторов
  • Если [math]C = A ⋇ B[/math], то для каждого [math]z \in Z[/math] верно [math]\pi_X(\sigma_{Z=z}(C)) = A \div \pi_Y(\sigma_{Z=z}(B))[/math] — интерпретация большого деления как "деление для каждого [math]z[/math]"
  • [math]A ⋇ B = \pi_X(A) \times \pi_Z(B) \setminus \pi_{XZ}(\pi_X(A) \times B \setminus A \Join B)[/math] — выражение большого деления через простейшие операции реляционной алгебры

Литература

  • Дейт К. Введение в системы баз данных (глава 7)
  • Уидом Д., Ульман Д. Основы реляционных баз данных (главы 4 и 5)