Викиконспекты - Вклад участника [ru]

Реляционная алгебра: соединения, деление

2021-12-26T10:42:17Z

Masmirnov:

=Соединения=

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

{{Определение
|definition=
'''Полным''', или '''декартовым соединением''' (англ. ''Cross join'', ''Cartesian join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex>, у которых нет общих атрибутов, называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а тело — декартовым произведением тел <tex>R_1</tex> и <tex>R_2</tex>. Обозначение: <tex>R_1 \times R_2</tex>
}}
В случае, если у двух отношений есть хотя бы один общий атрибут в заголовке, их полное соединение не определено.

===Пример===

Рассмотрим два отношения:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id1'''
!'''FirstName'''
|-
|1
|Иван
|-
|2
|Пётр
|-
|3
|Сидор
|}
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id2'''
!'''LastName'''
|-
|1
|Иванов
|-
|3
|Петров
|-
|4
|Сидоров
|}
Их полным соединением будет следующее отношение:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id1'''
!'''FirstName'''
!'''Id2'''
!'''LastName'''
|-
|1
|Иван
|1
|Иванов
|-
|1
|Иван
|3
|Петров
|-
|1
|Иван
|4
|Сидоров
|-
|2
|Пётр
|1
|Иванов
|-
|2
|Пётр
|3
|Петров
|-
|2
|Пётр
|4
|Сидоров
|-
|3
|Сидор
|1
|Иванов
|-
|3
|Сидор
|3
|Петров
|-
|3
|Сидор
|4
|Сидоров
|}

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

{{Определение
|definition=
'''Естественным соединением''' (англ. ''Natural join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а тело состоит из кортежей, полученных всевозможными соединениями кортежей <tex>R_1</tex> и <tex>R_2</tex>, имеющих равные значения одноимённых атрибутов. Обозначение: <tex>R_1 \Join R_2</tex>
}}
===Пример===

Рассмотрим два отношения:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
|-
|1
|Иван
|-
|2
|Пётр
|-
|3
|Сидор
|}
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''LastName'''
|-
|1
|Иванов
|-
|1
|Петров
|-
|2
|Сидоров
|}
Их естественным соединением будет следующее отношение:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
!'''LastName'''
|-
|1
|Иван
|Иванов
|-
|1
|Иван
|Петров
|-
|2
|Пётр
|Сидоров
|}

===Свойства===

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

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

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

{{Определение
|definition=
'''Левым соединением''' (англ. ''Left join'' или ''Left outer join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а тело состоит из кортежей, полученных всевозможными соединениями кортежей <tex>R_1</tex> и <tex>R_2</tex>, имеющих равные значения одноимённых атрибутов. Если по одноимённым атрибутам кортежу из <tex>R_1</tex> не соответствует ни одного кортежа из <tex>R_2</tex>, то в результат добавляется этот кортеж из <tex>R_1</tex>, дополненный пустыми значениями. Обозначение: <tex>R_1 \, ⟕ \, R_2</tex>
}}
{{Определение
|definition=
'''Правым соединением''' (англ. ''Right join'' или ''Right outer join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а тело состоит из кортежей, полученных всевозможными соединениями кортежей <tex>R_1</tex> и <tex>R_2</tex>, имеющих равные значения одноимённых атрибутов. Если по одноимённым атрибутам кортежу из <tex>R_2</tex> не соответствует ни одного кортежа из <tex>R_1</tex>, то в результат добавляется этот кортеж из <tex>R_2</tex>, дополненный пустыми значениями. Обозначение: <tex>R_1 \, ⟖ \, R_2</tex>
}}
{{Определение
|definition=
'''Внешним соединением''' (англ. ''Outer join'' или ''Full outer join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а тело состоит из кортежей, полученных всевозможными соединениями кортежей <tex>R_1</tex> и <tex>R_2</tex>, имеющих равные значения одноимённых атрибутов. Если по одноимённым атрибутам кортежу из одного отношения не соответствует ни одного кортежа из другого, то в результат добавляется этот кортеж, дополненный пустыми значениями. Обозначение: <tex>R_1 \, ⟗ \, R_2</tex>
}}
===Пример===

Рассмотрим два отношения (<tex>R_1</tex> и <tex>R_2</tex> соответственно):
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
|-
|1
|Иван
|-
|2
|Пётр
|-
|3
|Сидор
|}
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''LastName'''
|-
|1
|Иванов
|-
|1
|Петров
|-
|3
|Сидоров
|-
|4
|Плюшкин
|}
Тогда <tex>R_1 \, ⟕ \, R_2</tex> (левое соединение) равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
!'''LastName'''
|-
|1
|Иван
|Иванов
|-
|1
|Иван
|Петров
|-
|2
|Пётр
|
|-
|3
|Сидор
|Сидоров
|}
<tex>R_1 \, ⟖ \, R_2</tex> (правое соединение) равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
!'''LastName'''
|-
|1
|Иван
|Иванов
|-
|1
|Иван
|Петров
|-
|3
|Сидор
|Сидоров
|-
|4
|
|Плюшкин
|}
<tex>R_1 \, ⟗ \, R_2</tex> (внешнее соединение) равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
!'''LastName'''
|-
|1
|Иван
|Иванов
|-
|1
|Иван
|Петров
|-
|2
|Пётр
|
|-
|3
|Сидор
|Сидоров
|-
|4
|
|Плюшкин
|}

===Свойства===

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

* <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_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_2 \, ⟖ \, R_1</tex>
* <tex>R_1 \, ⟗ \, R_2 = (R_1 \, ⟕ \, R_2) \cup (R_1 \, ⟖ \, R_2)</tex>

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

{{Определение
|definition=
'''Левым полусоединением''' (англ. ''Left semijoin'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок равен заголовку <tex>R_1</tex>, а тело состоит из кортежей в <tex>R_1</tex>, для которых существует кортеж из <tex>R_2</tex> с равными значениями одноимённых атрибутов. Обозначение: <tex>R_1 \ltimes R_2</tex>
}}
{{Определение
|definition=
'''Правым полусоединением''' (англ. ''Right semijoin'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок равен заголовку <tex>R_2</tex>, а тело состоит из кортежей в <tex>R_2</tex>, для которых существует кортеж из <tex>R_1</tex> с равными значениями одноимённых атрибутов. Обозначение: <tex>R_1 \rtimes R_2</tex>
}}
===Пример===

Рассмотрим два отношения (<tex>R_1</tex> и <tex>R_2</tex> соответственно):
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
|-
|1
|Иван
|-
|2
|Пётр
|-
|3
|Сидор
|}
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''LastName'''
|-
|1
|Иванов
|-
|1
|Петров
|-
|3
|Сидоров
|-
|4
|Плюшкин
|}
Тогда <tex>R_1 \ltimes R_2</tex> (левое полусоединение) равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
|-
|1
|Иван
|-
|3
|Сидор
|}
<tex>R_1 \rtimes R_2</tex> (правое полусоединение) равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''LastName'''
|-
|1
|Иванов
|-
|1
|Петров
|-
|3
|Сидоров
|}

===Свойства===

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

* <tex>R_1 \ltimes R_2 = \pi_{R_1}(R_1 \Join R_2)</tex>
* <tex>R_1 \rtimes R_2 = \pi_{R_2}(R_1 \Join R_2)</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_2 \setminus (R_1 \rtimes R_2))</tex>
* <tex>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))</tex>

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

{{Определение
|definition=
'''Условным соединением''' (англ. ''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 \times_{\theta} R_2</tex>
}}
{{Определение
|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>
}}
{{Определение
|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>
}}
{{Определение
|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>
}}
===Пример===

Рассмотрим два отношения (<tex>R_1</tex> и <tex>R_2</tex> соответственно):
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id1'''
!'''FirstName'''
|-
|1
|Иван
|-
|2
|Пётр
|-
|3
|Сидор
|}
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id2'''
!'''LastName'''
|-
|1
|Иванов
|-
|1
|Петров
|-
|3
|Сидоров
|-
|4
|Плюшкин
|}
Тогда <tex>R_1 \, ⟕_{\text{length(FirstName)}+2<\text{length(LastName)}} \, R_2</tex> равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id1'''
!'''FirstName'''
!'''Id2'''
!'''LastName'''
|-
|1
|Иван
|3
|Сидоров
|-
|1
|Иван
|4
|Плюшкин
|-
|2
|Пётр
|3
|Сидоров
|-
|2
|Пётр
|4
|Плюшкин
|-
|3
|Сидор
|
|
|}

===Свойства===

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

* <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_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_1 \, ⟕_{\theta} \, R_2) \cup (R_1 \, ⟖_{\theta} \, R_2)</tex>

=Деление=

==Деление==

{{Определение
|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> по определению

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

{{Определение
|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> — выражение большого деления через простейшие операции реляционной алгебры

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

[[Категория: Базы данных]]

Реляционная алгебра: соединения, деление

2021-12-26T10:27:30Z

Masmirnov:

=Соединения=

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

{{Определение
|definition=
'''Полным''', или '''декартовым соединением''' (англ. ''Cross join'', ''Cartesian join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex>, у которых нет общих атрибутов, называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а тело — декартовым произведением тел <tex>R_1</tex> и <tex>R_2</tex>. Обозначение: <tex>R_1 \times R_2</tex>
}}
В случае, если у двух отношений есть хотя бы один общий атрибут в заголовке, их полное соединение не определено.

===Пример===

Рассмотрим два отношения:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id1'''
!'''FirstName'''
|-
|1
|Иван
|-
|2
|Пётр
|-
|3
|Сидор
|}
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id2'''
!'''LastName'''
|-
|1
|Иванов
|-
|3
|Петров
|-
|4
|Сидоров
|}
Их полным соединением будет следующее отношение:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id1'''
!'''FirstName'''
!'''Id2'''
!'''LastName'''
|-
|1
|Иван
|1
|Иванов
|-
|1
|Иван
|3
|Петров
|-
|1
|Иван
|4
|Сидоров
|-
|2
|Пётр
|1
|Иванов
|-
|2
|Пётр
|3
|Петров
|-
|2
|Пётр
|4
|Сидоров
|-
|3
|Сидор
|1
|Иванов
|-
|3
|Сидор
|3
|Петров
|-
|3
|Сидор
|4
|Сидоров
|}

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

{{Определение
|definition=
'''Естественным соединением''' (англ. ''Natural join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а тело состоит из кортежей, полученных всевозможными соединениями кортежей <tex>R_1</tex> и <tex>R_2</tex>, имеющих равные значения одноимённых атрибутов. Обозначение: <tex>R_1 \Join R_2</tex>
}}
===Пример===

Рассмотрим два отношения:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
|-
|1
|Иван
|-
|2
|Пётр
|-
|3
|Сидор
|}
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''LastName'''
|-
|1
|Иванов
|-
|1
|Петров
|-
|2
|Сидоров
|}
Их естественным соединением будет следующее отношение:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
!'''LastName'''
|-
|1
|Иван
|Иванов
|-
|1
|Иван
|Петров
|-
|2
|Пётр
|Сидоров
|}

===Свойства===

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

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

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

{{Определение
|definition=
'''Левым соединением''' (англ. ''Left join'' или ''Left outer join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а тело состоит из кортежей, полученных всевозможными соединениями кортежей <tex>R_1</tex> и <tex>R_2</tex>, имеющих равные значения одноимённых атрибутов. Если по одноимённым атрибутам кортежу из <tex>R_1</tex> не соответствует ни одного кортежа из <tex>R_2</tex>, то в результат добавляется этот кортеж из <tex>R_1</tex>, дополненный пустыми значениями. Обозначение: <tex>R_1 \, ⟕ \, R_2</tex>
}}
{{Определение
|definition=
'''Правым соединением''' (англ. ''Right join'' или ''Right outer join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а тело состоит из кортежей, полученных всевозможными соединениями кортежей <tex>R_1</tex> и <tex>R_2</tex>, имеющих равные значения одноимённых атрибутов. Если по одноимённым атрибутам кортежу из <tex>R_2</tex> не соответствует ни одного кортежа из <tex>R_1</tex>, то в результат добавляется этот кортеж из <tex>R_2</tex>, дополненный пустыми значениями. Обозначение: <tex>R_1 \, ⟖ \, R_2</tex>
}}
{{Определение
|definition=
'''Внешним соединением''' (англ. ''Outer join'' или ''Full outer join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а тело состоит из кортежей, полученных всевозможными соединениями кортежей <tex>R_1</tex> и <tex>R_2</tex>, имеющих равные значения одноимённых атрибутов. Если по одноимённым атрибутам кортежу из одного отношения не соответствует ни одного кортежа из другого, то в результат добавляется этот кортеж, дополненный пустыми значениями. Обозначение: <tex>R_1 \, ⟗ \, R_2</tex>
}}
===Пример===

Рассмотрим два отношения (<tex>R_1</tex> и <tex>R_2</tex> соответственно):
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
|-
|1
|Иван
|-
|2
|Пётр
|-
|3
|Сидор
|}
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''LastName'''
|-
|1
|Иванов
|-
|1
|Петров
|-
|3
|Сидоров
|-
|4
|Плюшкин
|}
Тогда <tex>R_1 \, ⟕ \, R_2</tex> (левое соединение) равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
!'''LastName'''
|-
|1
|Иван
|Иванов
|-
|1
|Иван
|Петров
|-
|2
|Пётр
|
|-
|3
|Сидор
|Сидоров
|}
<tex>R_1 \, ⟖ \, R_2</tex> (правое соединение) равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
!'''LastName'''
|-
|1
|Иван
|Иванов
|-
|1
|Иван
|Петров
|-
|3
|Сидор
|Сидоров
|-
|4
|
|Плюшкин
|}
<tex>R_1 \, ⟗ \, R_2</tex> (внешнее соединение) равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
!'''LastName'''
|-
|1
|Иван
|Иванов
|-
|1
|Иван
|Петров
|-
|2
|Пётр
|
|-
|3
|Сидор
|Сидоров
|-
|4
|
|Плюшкин
|}

===Свойства===

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

* <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_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_2 \, ⟖ \, R_1</tex>
* <tex>R_1 \, ⟗ \, R_2 = (R_1 \, ⟕ \, R_2) \cup (R_1 \, ⟖ \, R_2)</tex>

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

{{Определение
|definition=
'''Левым полусоединением''' (англ. ''Left semijoin'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок равен заголовку <tex>R_1</tex>, а тело состоит из кортежей в <tex>R_1</tex>, для которых существует кортеж из <tex>R_2</tex> с равными значениями одноимённых атрибутов. Обозначение: <tex>R_1 \ltimes R_2</tex>
}}
{{Определение
|definition=
'''Правым полусоединением''' (англ. ''Right semijoin'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок равен заголовку <tex>R_2</tex>, а тело состоит из кортежей в <tex>R_2</tex>, для которых существует кортеж из <tex>R_1</tex> с равными значениями одноимённых атрибутов. Обозначение: <tex>R_1 \rtimes R_2</tex>
}}
===Пример===

Рассмотрим два отношения (<tex>R_1</tex> и <tex>R_2</tex> соответственно):
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
|-
|1
|Иван
|-
|2
|Пётр
|-
|3
|Сидор
|}
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''LastName'''
|-
|1
|Иванов
|-
|1
|Петров
|-
|3
|Сидоров
|-
|4
|Плюшкин
|}
Тогда <tex>R_1 \ltimes R_2</tex> (левое полусоединение) равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
|-
|1
|Иван
|-
|3
|Сидор
|}
<tex>R_1 \rtimes R_2</tex> (правое полусоединение) равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''LastName'''
|-
|1
|Иванов
|-
|1
|Петров
|-
|3
|Сидоров
|}

===Свойства===

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

* <tex>R_1 \ltimes R_2 = \pi_{R_1}(R_1 \Join R_2)</tex>
* <tex>R_1 \rtimes R_2 = \pi_{R_2}(R_1 \Join R_2)</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_2 \setminus (R_1 \rtimes R_2))</tex>
* <tex>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))</tex>

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

{{Определение
|definition=
'''Условным соединением''' (англ. ''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 \times_{\theta} R_2</tex>
}}
{{Определение
|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>
}}
{{Определение
|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>
}}
{{Определение
|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>
}}
===Пример===

Рассмотрим два отношения (<tex>R_1</tex> и <tex>R_2</tex> соответственно):
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id1'''
!'''FirstName'''
|-
|1
|Иван
|-
|2
|Пётр
|-
|3
|Сидор
|}
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id2'''
!'''LastName'''
|-
|1
|Иванов
|-
|1
|Петров
|-
|3
|Сидоров
|-
|4
|Плюшкин
|}
Тогда <tex>R_1 \, ⟕_{\text{length(FirstName)}+2<\text{length(LastName)}} \, R_2</tex> равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id1'''
!'''FirstName'''
!'''Id2'''
!'''LastName'''
|-
|1
|Иван
|3
|Сидоров
|-
|1
|Иван
|4
|Плюшкин
|-
|2
|Пётр
|3
|Сидоров
|-
|2
|Пётр
|4
|Плюшкин
|-
|3
|Сидор
|
|
|}

===Свойства===

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

* <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_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_1 \, ⟕_{\theta} \, R_2) \cup (R_1 \, ⟖_{\theta} \, R_2)</tex>

=Деление=

==Деление==

{{Определение
|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> по определению

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

{{Определение
|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 \cup 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>LastName = Иванов</tex>. Отфильтровав по этому условию отношение <tex>B</tex>, получим <tex>Id = \{1, 2\}</tex>. Поделив отношение <tex>A</tex> на это, получим <tex>FirstName = \{Иван, Пётр\}</tex>. Поэтому в ответе есть ''Иван Иванов'' и ''Пётр Иванов''.

Зафиксируем <tex>LastName = Петров</tex>. Отфильтровав по этому условию отношение <tex>B</tex>, получим <tex>Id = \{1\}</tex>. Поделив отношение <tex>A</tex> на это, получим <tex>FirstName = \{Иван, Пётр, Сидор\}</tex>. Поэтому в ответе есть ''Иван Петров'', ''Пётр Петров'' и ''Сидор Петров''.

Зафиксируем <tex>LastName = Сидоров</tex>. Отфильтровав по этому условию отношение <tex>B</tex>, получим <tex>Id = \{3\}</tex>. Поделив отношение <tex>A</tex> на это, получим <tex>FirstName = \{Пётр, Сидор\}</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> — выражение большого деления через простейшие операции реляционной алгебры

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

[[Категория: Базы данных]]

Реляционная алгебра: соединения, деление

2021-12-20T12:50:16Z

Masmirnov: /* Большое деление */

=Соединения=

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

{{Определение
|definition=
'''Полным''', или '''декартовым соединением''' (англ. ''Cross join'', ''Cartesian join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex>, у которых нет общих атрибутов, называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а тело — декартовым произведением тел <tex>R_1</tex> и <tex>R_2</tex>. Обозначение: <tex>R_1 \times R_2</tex>
}}
В случае, если у двух отношений есть хотя бы один общий атрибут в заголовке, их полное соединение не определено.

===Пример===

Рассмотрим два отношения:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id1'''
!'''FirstName'''
|-
|1
|Иван
|-
|2
|Пётр
|-
|3
|Сидор
|}
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id2'''
!'''LastName'''
|-
|1
|Иванов
|-
|3
|Петров
|-
|4
|Сидоров
|}
Их полным соединением будет следующее отношение:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id1'''
!'''FirstName'''
!'''Id2'''
!'''LastName'''
|-
|1
|Иван
|1
|Иванов
|-
|1
|Иван
|3
|Петров
|-
|1
|Иван
|4
|Сидоров
|-
|2
|Пётр
|1
|Иванов
|-
|2
|Пётр
|3
|Петров
|-
|2
|Пётр
|4
|Сидоров
|-
|3
|Сидор
|1
|Иванов
|-
|3
|Сидор
|3
|Петров
|-
|3
|Сидор
|4
|Сидоров
|}

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

{{Определение
|definition=
'''Естественным соединением''' (англ. ''Natural join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а тело состоит из кортежей, полученных всевозможными соединениями кортежей <tex>R_1</tex> и <tex>R_2</tex>, имеющих равные значения одноимённых атрибутов. Обозначение: <tex>R_1 \Join R_2</tex>
}}
===Пример===

Рассмотрим два отношения:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
|-
|1
|Иван
|-
|2
|Пётр
|-
|3
|Сидор
|}
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''LastName'''
|-
|1
|Иванов
|-
|1
|Петров
|-
|2
|Сидоров
|}
Их естественным соединением будет следующее отношение:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
!'''LastName'''
|-
|1
|Иван
|Иванов
|-
|1
|Иван
|Петров
|-
|2
|Пётр
|Сидоров
|}

===Свойства===

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

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

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

{{Определение
|definition=
'''Левым соединением''' (англ. ''Left join'' или ''Left outer join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а тело состоит из кортежей, полученных всевозможными соединениями кортежей <tex>R_1</tex> и <tex>R_2</tex>, имеющих равные значения одноимённых атрибутов. Если по одноимённым атрибутам кортежу из <tex>R_1</tex> не соответствует ни одного кортежа из <tex>R_2</tex>, то в результат добавляется этот кортеж из <tex>R_1</tex>, дополненный пустыми значениями. Обозначение: <tex>R_1 \, ⟕ \, R_2</tex>
}}
{{Определение
|definition=
'''Правым соединением''' (англ. ''Right join'' или ''Right outer join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а тело состоит из кортежей, полученных всевозможными соединениями кортежей <tex>R_1</tex> и <tex>R_2</tex>, имеющих равные значения одноимённых атрибутов. Если по одноимённым атрибутам кортежу из <tex>R_2</tex> не соответствует ни одного кортежа из <tex>R_1</tex>, то в результат добавляется этот кортеж из <tex>R_2</tex>, дополненный пустыми значениями. Обозначение: <tex>R_1 \, ⟖ \, R_2</tex>
}}
{{Определение
|definition=
'''Внешним соединением''' (англ. ''Outer join'' или ''Full outer join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а тело состоит из кортежей, полученных всевозможными соединениями кортежей <tex>R_1</tex> и <tex>R_2</tex>, имеющих равные значения одноимённых атрибутов. Если по одноимённым атрибутам кортежу из одного отношения не соответствует ни одного кортежа из другого, то в результат добавляется этот кортеж, дополненный пустыми значениями. Обозначение: <tex>R_1 \, ⟗ \, R_2</tex>
}}
===Пример===

Рассмотрим два отношения (<tex>R_1</tex> и <tex>R_2</tex> соответственно):
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
|-
|1
|Иван
|-
|2
|Пётр
|-
|3
|Сидор
|}
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''LastName'''
|-
|1
|Иванов
|-
|1
|Петров
|-
|3
|Сидоров
|-
|4
|Плюшкин
|}
Тогда <tex>R_1 \, ⟕ \, R_2</tex> (левое соединение) равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
!'''LastName'''
|-
|1
|Иван
|Иванов
|-
|1
|Иван
|Петров
|-
|2
|Пётр
|
|-
|3
|Сидор
|Сидоров
|}
<tex>R_1 \, ⟖ \, R_2</tex> (правое соединение) равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
!'''LastName'''
|-
|1
|Иван
|Иванов
|-
|1
|Иван
|Петров
|-
|3
|Сидор
|Сидоров
|-
|4
|
|Плюшкин
|}
<tex>R_1 \, ⟗ \, R_2</tex> (внешнее соединение) равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
!'''LastName'''
|-
|1
|Иван
|Иванов
|-
|1
|Иван
|Петров
|-
|2
|Пётр
|
|-
|3
|Сидор
|Сидоров
|-
|4
|
|Плюшкин
|}

===Свойства===

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

* <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_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_2 \, ⟖ \, R_1</tex>
* <tex>R_1 \, ⟗ \, R_2 = (R_1 \, ⟕ \, R_2) \cup (R_1 \, ⟖ \, R_2)</tex>

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

{{Определение
|definition=
'''Левым полусоединением''' (англ. ''Left semijoin'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок равен заголовку <tex>R_1</tex>, а тело состоит из кортежей в <tex>R_1</tex>, для которых существует кортеж из <tex>R_2</tex> с равными значениями одноимённых атрибутов. Обозначение: <tex>R_1 \ltimes R_2</tex>
}}
{{Определение
|definition=
'''Правым полусоединением''' (англ. ''Right semijoin'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок равен заголовку <tex>R_2</tex>, а тело состоит из кортежей в <tex>R_2</tex>, для которых существует кортеж из <tex>R_1</tex> с равными значениями одноимённых атрибутов. Обозначение: <tex>R_1 \rtimes R_2</tex>
}}
===Пример===

Рассмотрим два отношения (<tex>R_1</tex> и <tex>R_2</tex> соответственно):
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
|-
|1
|Иван
|-
|2
|Пётр
|-
|3
|Сидор
|}
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''LastName'''
|-
|1
|Иванов
|-
|1
|Петров
|-
|3
|Сидоров
|-
|4
|Плюшкин
|}
Тогда <tex>R_1 \ltimes R_2</tex> (левое полусоединение) равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
|-
|1
|Иван
|-
|3
|Сидор
|}
<tex>R_1 \rtimes R_2</tex> (правое полусоединение) равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''LastName'''
|-
|1
|Иванов
|-
|1
|Петров
|-
|3
|Сидоров
|}

===Свойства===

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

* <tex>R_1 \ltimes R_2 = \pi_{R_1}(R_1 \Join R_2)</tex>
* <tex>R_1 \rtimes R_2 = \pi_{R_2}(R_1 \Join R_2)</tex>
* <tex>R_1 \ltimes R_2 = R_2 \rtimes R_1</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_2 \setminus (R_1 \rtimes R_2))</tex>
* <tex>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))</tex>

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

{{Определение
|definition=
'''Условным соединением''' (англ. ''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 \times_{\theta} R_2</tex>
}}
{{Определение
|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>
}}
{{Определение
|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>
}}
{{Определение
|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>
}}
===Пример===

Рассмотрим два отношения (<tex>R_1</tex> и <tex>R_2</tex> соответственно):
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id1'''
!'''FirstName'''
|-
|1
|Иван
|-
|2
|Пётр
|-
|3
|Сидор
|}
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id2'''
!'''LastName'''
|-
|1
|Иванов
|-
|1
|Петров
|-
|3
|Сидоров
|-
|4
|Плюшкин
|}
Тогда <tex>R_1 \, ⟕_{\text{length(FirstName)}+2<\text{length(LastName)}} \, R_2</tex> равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id1'''
!'''FirstName'''
!'''Id2'''
!'''LastName'''
|-
|1
|Иван
|3
|Сидоров
|-
|1
|Иван
|4
|Плюшкин
|-
|2
|Пётр
|3
|Сидоров
|-
|2
|Пётр
|4
|Плюшкин
|-
|3
|Сидор
|
|
|}

===Свойства===

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

* <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_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_1 \, ⟕_{\theta} \, R_2) \cup (R_1 \, ⟖_{\theta} \, R_2)</tex>

=Деление=

==Деление==

{{Определение
|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> — выражение деления через простейшие операции реляционной алгебры

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

{{Определение
|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 \cup 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>LastName = Иванов</tex>. Отфильтровав по этому условию отношение <tex>B</tex>, получим <tex>Id = \{1, 2\}</tex>. Поделив отношение <tex>A</tex> на это, получим <tex>FirstName = \{Иван, Пётр\}</tex>. Поэтому в ответе есть ''Иван Иванов'' и ''Пётр Иванов''.

Зафиксируем <tex>LastName = Петров</tex>. Отфильтровав по этому условию отношение <tex>B</tex>, получим <tex>Id = \{1\}</tex>. Поделив отношение <tex>A</tex> на это, получим <tex>FirstName = \{Иван, Пётр, Сидор\}</tex>. Поэтому в ответе есть ''Иван Петров'', ''Пётр Петров'' и ''Сидор Петров''.

Зафиксируем <tex>LastName = Сидоров</tex>. Отфильтровав по этому условию отношение <tex>B</tex>, получим <tex>Id = \{3\}</tex>. Поделив отношение <tex>A</tex> на это, получим <tex>FirstName = \{Пётр, Сидор\}</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> — выражение большого деления через простейшие операции реляционной алгебры

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

[[Категория: Базы данных]]

Реляционная алгебра: соединения, деление

2021-12-20T12:49:04Z

Masmirnov: /* Большое деление */

=Соединения=

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

{{Определение
|definition=
'''Полным''', или '''декартовым соединением''' (англ. ''Cross join'', ''Cartesian join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex>, у которых нет общих атрибутов, называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а тело — декартовым произведением тел <tex>R_1</tex> и <tex>R_2</tex>. Обозначение: <tex>R_1 \times R_2</tex>
}}
В случае, если у двух отношений есть хотя бы один общий атрибут в заголовке, их полное соединение не определено.

===Пример===

Рассмотрим два отношения:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id1'''
!'''FirstName'''
|-
|1
|Иван
|-
|2
|Пётр
|-
|3
|Сидор
|}
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id2'''
!'''LastName'''
|-
|1
|Иванов
|-
|3
|Петров
|-
|4
|Сидоров
|}
Их полным соединением будет следующее отношение:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id1'''
!'''FirstName'''
!'''Id2'''
!'''LastName'''
|-
|1
|Иван
|1
|Иванов
|-
|1
|Иван
|3
|Петров
|-
|1
|Иван
|4
|Сидоров
|-
|2
|Пётр
|1
|Иванов
|-
|2
|Пётр
|3
|Петров
|-
|2
|Пётр
|4
|Сидоров
|-
|3
|Сидор
|1
|Иванов
|-
|3
|Сидор
|3
|Петров
|-
|3
|Сидор
|4
|Сидоров
|}

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

{{Определение
|definition=
'''Естественным соединением''' (англ. ''Natural join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а тело состоит из кортежей, полученных всевозможными соединениями кортежей <tex>R_1</tex> и <tex>R_2</tex>, имеющих равные значения одноимённых атрибутов. Обозначение: <tex>R_1 \Join R_2</tex>
}}
===Пример===

Рассмотрим два отношения:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
|-
|1
|Иван
|-
|2
|Пётр
|-
|3
|Сидор
|}
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''LastName'''
|-
|1
|Иванов
|-
|1
|Петров
|-
|2
|Сидоров
|}
Их естественным соединением будет следующее отношение:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
!'''LastName'''
|-
|1
|Иван
|Иванов
|-
|1
|Иван
|Петров
|-
|2
|Пётр
|Сидоров
|}

===Свойства===

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

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

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

{{Определение
|definition=
'''Левым соединением''' (англ. ''Left join'' или ''Left outer join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а тело состоит из кортежей, полученных всевозможными соединениями кортежей <tex>R_1</tex> и <tex>R_2</tex>, имеющих равные значения одноимённых атрибутов. Если по одноимённым атрибутам кортежу из <tex>R_1</tex> не соответствует ни одного кортежа из <tex>R_2</tex>, то в результат добавляется этот кортеж из <tex>R_1</tex>, дополненный пустыми значениями. Обозначение: <tex>R_1 \, ⟕ \, R_2</tex>
}}
{{Определение
|definition=
'''Правым соединением''' (англ. ''Right join'' или ''Right outer join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а тело состоит из кортежей, полученных всевозможными соединениями кортежей <tex>R_1</tex> и <tex>R_2</tex>, имеющих равные значения одноимённых атрибутов. Если по одноимённым атрибутам кортежу из <tex>R_2</tex> не соответствует ни одного кортежа из <tex>R_1</tex>, то в результат добавляется этот кортеж из <tex>R_2</tex>, дополненный пустыми значениями. Обозначение: <tex>R_1 \, ⟖ \, R_2</tex>
}}
{{Определение
|definition=
'''Внешним соединением''' (англ. ''Outer join'' или ''Full outer join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а тело состоит из кортежей, полученных всевозможными соединениями кортежей <tex>R_1</tex> и <tex>R_2</tex>, имеющих равные значения одноимённых атрибутов. Если по одноимённым атрибутам кортежу из одного отношения не соответствует ни одного кортежа из другого, то в результат добавляется этот кортеж, дополненный пустыми значениями. Обозначение: <tex>R_1 \, ⟗ \, R_2</tex>
}}
===Пример===

Рассмотрим два отношения (<tex>R_1</tex> и <tex>R_2</tex> соответственно):
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
|-
|1
|Иван
|-
|2
|Пётр
|-
|3
|Сидор
|}
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''LastName'''
|-
|1
|Иванов
|-
|1
|Петров
|-
|3
|Сидоров
|-
|4
|Плюшкин
|}
Тогда <tex>R_1 \, ⟕ \, R_2</tex> (левое соединение) равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
!'''LastName'''
|-
|1
|Иван
|Иванов
|-
|1
|Иван
|Петров
|-
|2
|Пётр
|
|-
|3
|Сидор
|Сидоров
|}
<tex>R_1 \, ⟖ \, R_2</tex> (правое соединение) равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
!'''LastName'''
|-
|1
|Иван
|Иванов
|-
|1
|Иван
|Петров
|-
|3
|Сидор
|Сидоров
|-
|4
|
|Плюшкин
|}
<tex>R_1 \, ⟗ \, R_2</tex> (внешнее соединение) равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
!'''LastName'''
|-
|1
|Иван
|Иванов
|-
|1
|Иван
|Петров
|-
|2
|Пётр
|
|-
|3
|Сидор
|Сидоров
|-
|4
|
|Плюшкин
|}

===Свойства===

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

* <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_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_2 \, ⟖ \, R_1</tex>
* <tex>R_1 \, ⟗ \, R_2 = (R_1 \, ⟕ \, R_2) \cup (R_1 \, ⟖ \, R_2)</tex>

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

{{Определение
|definition=
'''Левым полусоединением''' (англ. ''Left semijoin'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок равен заголовку <tex>R_1</tex>, а тело состоит из кортежей в <tex>R_1</tex>, для которых существует кортеж из <tex>R_2</tex> с равными значениями одноимённых атрибутов. Обозначение: <tex>R_1 \ltimes R_2</tex>
}}
{{Определение
|definition=
'''Правым полусоединением''' (англ. ''Right semijoin'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок равен заголовку <tex>R_2</tex>, а тело состоит из кортежей в <tex>R_2</tex>, для которых существует кортеж из <tex>R_1</tex> с равными значениями одноимённых атрибутов. Обозначение: <tex>R_1 \rtimes R_2</tex>
}}
===Пример===

Рассмотрим два отношения (<tex>R_1</tex> и <tex>R_2</tex> соответственно):
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
|-
|1
|Иван
|-
|2
|Пётр
|-
|3
|Сидор
|}
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''LastName'''
|-
|1
|Иванов
|-
|1
|Петров
|-
|3
|Сидоров
|-
|4
|Плюшкин
|}
Тогда <tex>R_1 \ltimes R_2</tex> (левое полусоединение) равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
|-
|1
|Иван
|-
|3
|Сидор
|}
<tex>R_1 \rtimes R_2</tex> (правое полусоединение) равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''LastName'''
|-
|1
|Иванов
|-
|1
|Петров
|-
|3
|Сидоров
|}

===Свойства===

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

* <tex>R_1 \ltimes R_2 = \pi_{R_1}(R_1 \Join R_2)</tex>
* <tex>R_1 \rtimes R_2 = \pi_{R_2}(R_1 \Join R_2)</tex>
* <tex>R_1 \ltimes R_2 = R_2 \rtimes R_1</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_2 \setminus (R_1 \rtimes R_2))</tex>
* <tex>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))</tex>

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

{{Определение
|definition=
'''Условным соединением''' (англ. ''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 \times_{\theta} R_2</tex>
}}
{{Определение
|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>
}}
{{Определение
|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>
}}
{{Определение
|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>
}}
===Пример===

Рассмотрим два отношения (<tex>R_1</tex> и <tex>R_2</tex> соответственно):
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id1'''
!'''FirstName'''
|-
|1
|Иван
|-
|2
|Пётр
|-
|3
|Сидор
|}
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id2'''
!'''LastName'''
|-
|1
|Иванов
|-
|1
|Петров
|-
|3
|Сидоров
|-
|4
|Плюшкин
|}
Тогда <tex>R_1 \, ⟕_{\text{length(FirstName)}+2<\text{length(LastName)}} \, R_2</tex> равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id1'''
!'''FirstName'''
!'''Id2'''
!'''LastName'''
|-
|1
|Иван
|3
|Сидоров
|-
|1
|Иван
|4
|Плюшкин
|-
|2
|Пётр
|3
|Сидоров
|-
|2
|Пётр
|4
|Плюшкин
|-
|3
|Сидор
|
|
|}

===Свойства===

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

* <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_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_1 \, ⟕_{\theta} \, R_2) \cup (R_1 \, ⟖_{\theta} \, R_2)</tex>

=Деление=

==Деление==

{{Определение
|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> — выражение деления через простейшие операции реляционной алгебры

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

{{Определение
|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 \cup 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>LastName = Иванов</tex>. Отфильтровав по этому условию отношение <tex>B</tex>, получим <tex>Id = \{1, 2\}</tex>. Поделив отношение <tex>A</tex> на это, получим <tex>FirstName = \{Иван, Пётр\}</tex>. Поэтому в ответе есть ''Иван Иванов'' и ''Пётр Иванов''.

Зафиксируем <tex>LastName = Петров</tex>. Отфильтровав по этому условию отношение <tex>B</tex>, получим <tex>Id = \{1\}</tex>. Поделив отношение <tex>A</tex> на это, получим <tex>FirstName = \{Иван, Пётр, Сидор\}</tex>. Поэтому в ответе есть ''Иван Петров'', ''Пётр Петров'' и ''Сидор Петров''.

Зафиксируем <tex>LastName = Сидоров</tex>. Отфильтровав по этому условию отношение <tex>B</tex>, получим <tex>Id = \{3\}</tex>. Поделив отношение <tex>A</tex> на это, получим <tex>FirstName = \{Пётр, Сидор\}</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>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> — выражение большого деления через простейшие операции реляционной алгебры

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

[[Категория: Базы данных]]

Реляционная алгебра: соединения, деление

2021-12-14T18:02:07Z

Masmirnov:

=Соединения=

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

{{Определение
|definition=
'''Полным''', или '''декартовым соединением''' (англ. ''Cross join'', ''Cartesian join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex>, у которых нет общих атрибутов, называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а тело — декартовым произведением тел <tex>R_1</tex> и <tex>R_2</tex>. Обозначение: <tex>R_1 \times R_2</tex>
}}
В случае, если у двух отношений есть хотя бы один общий атрибут в заголовке, их полное соединение не определено.

===Пример===

Рассмотрим два отношения:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id1'''
!'''FirstName'''
|-
|1
|Иван
|-
|2
|Пётр
|-
|3
|Сидор
|}
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id2'''
!'''LastName'''
|-
|1
|Иванов
|-
|3
|Петров
|-
|4
|Сидоров
|}
Их полным соединением будет следующее отношение:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id1'''
!'''FirstName'''
!'''Id2'''
!'''LastName'''
|-
|1
|Иван
|1
|Иванов
|-
|1
|Иван
|3
|Петров
|-
|1
|Иван
|4
|Сидоров
|-
|2
|Пётр
|1
|Иванов
|-
|2
|Пётр
|3
|Петров
|-
|2
|Пётр
|4
|Сидоров
|-
|3
|Сидор
|1
|Иванов
|-
|3
|Сидор
|3
|Петров
|-
|3
|Сидор
|4
|Сидоров
|}

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

{{Определение
|definition=
'''Естественным соединением''' (англ. ''Natural join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а тело состоит из кортежей, полученных всевозможными соединениями кортежей <tex>R_1</tex> и <tex>R_2</tex>, имеющих равные значения одноимённых атрибутов. Обозначение: <tex>R_1 \Join R_2</tex>
}}
===Пример===

Рассмотрим два отношения:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
|-
|1
|Иван
|-
|2
|Пётр
|-
|3
|Сидор
|}
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''LastName'''
|-
|1
|Иванов
|-
|1
|Петров
|-
|2
|Сидоров
|}
Их естественным соединением будет следующее отношение:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
!'''LastName'''
|-
|1
|Иван
|Иванов
|-
|1
|Иван
|Петров
|-
|2
|Пётр
|Сидоров
|}

===Свойства===

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

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

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

{{Определение
|definition=
'''Левым соединением''' (англ. ''Left join'' или ''Left outer join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а тело состоит из кортежей, полученных всевозможными соединениями кортежей <tex>R_1</tex> и <tex>R_2</tex>, имеющих равные значения одноимённых атрибутов. Если по одноимённым атрибутам кортежу из <tex>R_1</tex> не соответствует ни одного кортежа из <tex>R_2</tex>, то в результат добавляется этот кортеж из <tex>R_1</tex>, дополненный пустыми значениями. Обозначение: <tex>R_1 \, ⟕ \, R_2</tex>
}}
{{Определение
|definition=
'''Правым соединением''' (англ. ''Right join'' или ''Right outer join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а тело состоит из кортежей, полученных всевозможными соединениями кортежей <tex>R_1</tex> и <tex>R_2</tex>, имеющих равные значения одноимённых атрибутов. Если по одноимённым атрибутам кортежу из <tex>R_2</tex> не соответствует ни одного кортежа из <tex>R_1</tex>, то в результат добавляется этот кортеж из <tex>R_2</tex>, дополненный пустыми значениями. Обозначение: <tex>R_1 \, ⟖ \, R_2</tex>
}}
{{Определение
|definition=
'''Внешним соединением''' (англ. ''Outer join'' или ''Full outer join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а тело состоит из кортежей, полученных всевозможными соединениями кортежей <tex>R_1</tex> и <tex>R_2</tex>, имеющих равные значения одноимённых атрибутов. Если по одноимённым атрибутам кортежу из одного отношения не соответствует ни одного кортежа из другого, то в результат добавляется этот кортеж, дополненный пустыми значениями. Обозначение: <tex>R_1 \, ⟗ \, R_2</tex>
}}
===Пример===

Рассмотрим два отношения (<tex>R_1</tex> и <tex>R_2</tex> соответственно):
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
|-
|1
|Иван
|-
|2
|Пётр
|-
|3
|Сидор
|}
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''LastName'''
|-
|1
|Иванов
|-
|1
|Петров
|-
|3
|Сидоров
|-
|4
|Плюшкин
|}
Тогда <tex>R_1 \, ⟕ \, R_2</tex> (левое соединение) равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
!'''LastName'''
|-
|1
|Иван
|Иванов
|-
|1
|Иван
|Петров
|-
|2
|Пётр
|
|-
|3
|Сидор
|Сидоров
|}
<tex>R_1 \, ⟖ \, R_2</tex> (правое соединение) равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
!'''LastName'''
|-
|1
|Иван
|Иванов
|-
|1
|Иван
|Петров
|-
|3
|Сидор
|Сидоров
|-
|4
|
|Плюшкин
|}
<tex>R_1 \, ⟗ \, R_2</tex> (внешнее соединение) равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
!'''LastName'''
|-
|1
|Иван
|Иванов
|-
|1
|Иван
|Петров
|-
|2
|Пётр
|
|-
|3
|Сидор
|Сидоров
|-
|4
|
|Плюшкин
|}

===Свойства===

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

* <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_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_2 \, ⟖ \, R_1</tex>
* <tex>R_1 \, ⟗ \, R_2 = (R_1 \, ⟕ \, R_2) \cup (R_1 \, ⟖ \, R_2)</tex>

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

{{Определение
|definition=
'''Левым полусоединением''' (англ. ''Left semijoin'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок равен заголовку <tex>R_1</tex>, а тело состоит из кортежей в <tex>R_1</tex>, для которых существует кортеж из <tex>R_2</tex> с равными значениями одноимённых атрибутов. Обозначение: <tex>R_1 \ltimes R_2</tex>
}}
{{Определение
|definition=
'''Правым полусоединением''' (англ. ''Right semijoin'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок равен заголовку <tex>R_2</tex>, а тело состоит из кортежей в <tex>R_2</tex>, для которых существует кортеж из <tex>R_1</tex> с равными значениями одноимённых атрибутов. Обозначение: <tex>R_1 \rtimes R_2</tex>
}}
===Пример===

Рассмотрим два отношения (<tex>R_1</tex> и <tex>R_2</tex> соответственно):
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
|-
|1
|Иван
|-
|2
|Пётр
|-
|3
|Сидор
|}
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''LastName'''
|-
|1
|Иванов
|-
|1
|Петров
|-
|3
|Сидоров
|-
|4
|Плюшкин
|}
Тогда <tex>R_1 \ltimes R_2</tex> (левое полусоединение) равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
|-
|1
|Иван
|-
|3
|Сидор
|}
<tex>R_1 \rtimes R_2</tex> (правое полусоединение) равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''LastName'''
|-
|1
|Иванов
|-
|1
|Петров
|-
|3
|Сидоров
|}

===Свойства===

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

* <tex>R_1 \ltimes R_2 = \pi_{R_1}(R_1 \Join R_2)</tex>
* <tex>R_1 \rtimes R_2 = \pi_{R_2}(R_1 \Join R_2)</tex>
* <tex>R_1 \ltimes R_2 = R_2 \rtimes R_1</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_2 \setminus (R_1 \rtimes R_2))</tex>
* <tex>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))</tex>

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

{{Определение
|definition=
'''Условным соединением''' (англ. ''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 \times_{\theta} R_2</tex>
}}
{{Определение
|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>
}}
{{Определение
|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>
}}
{{Определение
|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>
}}
===Пример===

Рассмотрим два отношения (<tex>R_1</tex> и <tex>R_2</tex> соответственно):
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id1'''
!'''FirstName'''
|-
|1
|Иван
|-
|2
|Пётр
|-
|3
|Сидор
|}
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id2'''
!'''LastName'''
|-
|1
|Иванов
|-
|1
|Петров
|-
|3
|Сидоров
|-
|4
|Плюшкин
|}
Тогда <tex>R_1 \, ⟕_{\text{length(FirstName)}+2<\text{length(LastName)}} \, R_2</tex> равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id1'''
!'''FirstName'''
!'''Id2'''
!'''LastName'''
|-
|1
|Иван
|3
|Сидоров
|-
|1
|Иван
|4
|Плюшкин
|-
|2
|Пётр
|3
|Сидоров
|-
|2
|Пётр
|4
|Плюшкин
|-
|3
|Сидор
|
|
|}

===Свойства===

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

* <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_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_1 \, ⟕_{\theta} \, R_2) \cup (R_1 \, ⟖_{\theta} \, R_2)</tex>

=Деление=

==Деление==

{{Определение
|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> — выражение деления через простейшие операции реляционной алгебры

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

{{Определение
|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>C</tex> с заголовком <tex>X \cup Z</tex>, такое что для каждого <tex>z \in Z</tex> верно <tex>\pi_x(\sigma_{Z=z}(C)) = A \div \pi_Y(\sigma_{Z=z}(B))</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>LastName = Иванов</tex>. Отфильтровав по этому условию отношение <tex>B</tex>, получим <tex>Id = \{1, 2\}</tex>. Поделив отношение <tex>A</tex> на это, получим <tex>FirstName = \{Иван, Пётр\}</tex>. Поэтому в ответе есть ''Иван Иванов'' и ''Пётр Иванов''.

Зафиксируем <tex>LastName = Петров</tex>. Отфильтровав по этому условию отношение <tex>B</tex>, получим <tex>Id = \{1\}</tex>. Поделив отношение <tex>A</tex> на это, получим <tex>FirstName = \{Иван, Пётр, Сидор\}</tex>. Поэтому в ответе есть ''Иван Петров'', ''Пётр Петров'' и ''Сидор Петров''.

Зафиксируем <tex>LastName = Сидоров</tex>. Отфильтровав по этому условию отношение <tex>B</tex>, получим <tex>Id = \{3\}</tex>. Поделив отношение <tex>A</tex> на это, получим <tex>FirstName = \{Пётр, Сидор\}</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>A ⋇ B = \pi_X(A) \times \pi_Z(B) \setminus \pi_{XZ}(\pi_X(A) \times B \setminus A \Join B)</tex> — выражение большого деления через простейшие операции реляционной алгебры

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

[[Категория: Базы данных]]

Реляционная алгебра: соединения, деление

2021-12-14T17:55:27Z

Masmirnov: Деления

=Соединения=

{{Определение
|definition=
'''Соединение''' (англ. ''Join'') — общее наименование для бинарных операторов на отношениях, позволяющих некоторым образом соединить данные из нескольких отношений в одно.
}}
==Полное соединение==

{{Определение
|definition=
'''Полным''', или '''декартовым соединением''' (англ. ''Cross join'', ''Cartesian join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex>, у которых нет общих атрибутов, называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а тело — декартовым произведением тел <tex>R_1</tex> и <tex>R_2</tex>. Обозначение: <tex>R_1 \times R_2</tex>
}}
В случае, если у двух отношений есть хотя бы один общий атрибут в заголовке, их полное соединение не определено.

===Пример===

Рассмотрим два отношения:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id1'''
!'''FirstName'''
|-
|1
|Иван
|-
|2
|Пётр
|-
|3
|Сидор
|}
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id2'''
!'''LastName'''
|-
|1
|Иванов
|-
|3
|Петров
|-
|4
|Сидоров
|}
Их полным соединением будет следующее отношение:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id1'''
!'''FirstName'''
!'''Id2'''
!'''LastName'''
|-
|1
|Иван
|1
|Иванов
|-
|1
|Иван
|3
|Петров
|-
|1
|Иван
|4
|Сидоров
|-
|2
|Пётр
|1
|Иванов
|-
|2
|Пётр
|3
|Петров
|-
|2
|Пётр
|4
|Сидоров
|-
|3
|Сидор
|1
|Иванов
|-
|3
|Сидор
|3
|Петров
|-
|3
|Сидор
|4
|Сидоров
|}

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

{{Определение
|definition=
'''Естественным соединением''' (англ. ''Natural join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а тело состоит из кортежей, полученных всевозможными соединениями кортежей <tex>R_1</tex> и <tex>R_2</tex>, имеющих равные значения одноимённых атрибутов. Обозначение: <tex>R_1 \Join R_2</tex>
}}
===Пример===

Рассмотрим два отношения:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
|-
|1
|Иван
|-
|2
|Пётр
|-
|3
|Сидор
|}
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''LastName'''
|-
|1
|Иванов
|-
|1
|Петров
|-
|2
|Сидоров
|}
Их естественным соединением будет следующее отношение:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
!'''LastName'''
|-
|1
|Иван
|Иванов
|-
|1
|Иван
|Петров
|-
|2
|Пётр
|Сидоров
|}

===Свойства===

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

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

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

{{Определение
|definition=
'''Левым соединением''' (англ. ''Left join'' или ''Left outer join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а тело состоит из кортежей, полученных всевозможными соединениями кортежей <tex>R_1</tex> и <tex>R_2</tex>, имеющих равные значения одноимённых атрибутов. Если по одноимённым атрибутам кортежу из <tex>R_1</tex> не соответствует ни одного кортежа из <tex>R_2</tex>, то в результат добавляется этот кортеж из <tex>R_1</tex>, дополненный пустыми значениями. Обозначение: <tex>R_1 \, ⟕ \, R_2</tex>
}}
{{Определение
|definition=
'''Правым соединением''' (англ. ''Right join'' или ''Right outer join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а тело состоит из кортежей, полученных всевозможными соединениями кортежей <tex>R_1</tex> и <tex>R_2</tex>, имеющих равные значения одноимённых атрибутов. Если по одноимённым атрибутам кортежу из <tex>R_2</tex> не соответствует ни одного кортежа из <tex>R_1</tex>, то в результат добавляется этот кортеж из <tex>R_2</tex>, дополненный пустыми значениями. Обозначение: <tex>R_1 \, ⟖ \, R_2</tex>
}}
{{Определение
|definition=
'''Внешним соединением''' (англ. ''Outer join'' или ''Full outer join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а тело состоит из кортежей, полученных всевозможными соединениями кортежей <tex>R_1</tex> и <tex>R_2</tex>, имеющих равные значения одноимённых атрибутов. Если по одноимённым атрибутам кортежу из одного отношения не соответствует ни одного кортежа из другого, то в результат добавляется этот кортеж, дополненный пустыми значениями. Обозначение: <tex>R_1 \, ⟗ \, R_2</tex>
}}
===Пример===

Рассмотрим два отношения (<tex>R_1</tex> и <tex>R_2</tex> соответственно):
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
|-
|1
|Иван
|-
|2
|Пётр
|-
|3
|Сидор
|}
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''LastName'''
|-
|1
|Иванов
|-
|1
|Петров
|-
|3
|Сидоров
|-
|4
|Плюшкин
|}
Тогда <tex>R_1 \, ⟕ \, R_2</tex> (левое соединение) равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
!'''LastName'''
|-
|1
|Иван
|Иванов
|-
|1
|Иван
|Петров
|-
|2
|Пётр
|
|-
|3
|Сидор
|Сидоров
|}
<tex>R_1 \, ⟖ \, R_2</tex> (правое соединение) равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
!'''LastName'''
|-
|1
|Иван
|Иванов
|-
|1
|Иван
|Петров
|-
|3
|Сидор
|Сидоров
|-
|4
|
|Плюшкин
|}
<tex>R_1 \, ⟗ \, R_2</tex> (внешнее соединение) равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
!'''LastName'''
|-
|1
|Иван
|Иванов
|-
|1
|Иван
|Петров
|-
|2
|Пётр
|
|-
|3
|Сидор
|Сидоров
|-
|4
|
|Плюшкин
|}

===Свойства===

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

* <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_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_2 \, ⟖ \, R_1</tex>
* <tex>R_1 \, ⟗ \, R_2 = (R_1 \, ⟕ \, R_2) \cup (R_1 \, ⟖ \, R_2)</tex>

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

{{Определение
|definition=
'''Левым полусоединением''' (англ. ''Left semijoin'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок равен заголовку <tex>R_1</tex>, а тело состоит из кортежей в <tex>R_1</tex>, для которых существует кортеж из <tex>R_2</tex> с равными значениями одноимённых атрибутов. Обозначение: <tex>R_1 \ltimes R_2</tex>
}}
{{Определение
|definition=
'''Правым полусоединением''' (англ. ''Right semijoin'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок равен заголовку <tex>R_2</tex>, а тело состоит из кортежей в <tex>R_2</tex>, для которых существует кортеж из <tex>R_1</tex> с равными значениями одноимённых атрибутов. Обозначение: <tex>R_1 \rtimes R_2</tex>
}}
===Пример===

Рассмотрим два отношения (<tex>R_1</tex> и <tex>R_2</tex> соответственно):
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
|-
|1
|Иван
|-
|2
|Пётр
|-
|3
|Сидор
|}
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''LastName'''
|-
|1
|Иванов
|-
|1
|Петров
|-
|3
|Сидоров
|-
|4
|Плюшкин
|}
Тогда <tex>R_1 \ltimes R_2</tex> (левое полусоединение) равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
|-
|1
|Иван
|-
|3
|Сидор
|}
<tex>R_1 \rtimes R_2</tex> (правое полусоединение) равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''LastName'''
|-
|1
|Иванов
|-
|1
|Петров
|-
|3
|Сидоров
|}

===Свойства===

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

* <tex>R_1 \ltimes R_2 = \pi_{R_1}(R_1 \Join R_2)</tex>
* <tex>R_1 \rtimes R_2 = \pi_{R_2}(R_1 \Join R_2)</tex>
* <tex>R_1 \ltimes R_2 = R_2 \rtimes R_1</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_2 \setminus (R_1 \rtimes R_2))</tex>
* <tex>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))</tex>

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

{{Определение
|definition=
'''Условным соединением''' (англ. ''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 \times_{\theta} R_2</tex>
}}
{{Определение
|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>
}}
{{Определение
|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>
}}
{{Определение
|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>
}}
===Пример===

Рассмотрим два отношения (<tex>R_1</tex> и <tex>R_2</tex> соответственно):
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id1'''
!'''FirstName'''
|-
|1
|Иван
|-
|2
|Пётр
|-
|3
|Сидор
|}
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id2'''
!'''LastName'''
|-
|1
|Иванов
|-
|1
|Петров
|-
|3
|Сидоров
|-
|4
|Плюшкин
|}
Тогда <tex>R_1 \, ⟕_{\text{length(FirstName)}+2<\text{length(LastName)}} \, R_2</tex> равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id1'''
!'''FirstName'''
!'''Id2'''
!'''LastName'''
|-
|1
|Иван
|3
|Сидоров
|-
|1
|Иван
|4
|Плюшкин
|-
|2
|Пётр
|3
|Сидоров
|-
|2
|Пётр
|4
|Плюшкин
|-
|3
|Сидор
|
|
|}

===Свойства===

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

* <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_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_1 \, ⟕_{\theta} \, R_2) \cup (R_1 \, ⟖_{\theta} \, R_2)</tex>

=Деление=

==Деление==

{{Определение
|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> — выражение деления через простейшие операции реляционной алгебры

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

{{Определение
|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>C</tex> с заголовком <tex>X \cup Z</tex>, такое что для каждого <tex>z \in Z</tex> верно <tex>\pi_x(\sigma_{Z=z}(C)) = A \div \pi_Y(\sigma_{Z=z}(B))</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>LastName = Иванов</tex>. Отфильтровав по этому условию отношение <tex>B</tex>, получим <tex>Id = \{1, 2\}</tex>. Поделив отношение <tex>A</tex> на это, получим <tex>FirstName = \{Иван, Пётр\}</tex>. Поэтому в ответе есть ''Иван Иванов'' и ''Пётр Иванов''.

Зафиксируем <tex>LastName = Петров</tex>. Отфильтровав по этому условию отношение <tex>B</tex>, получим <tex>Id = \{1\}</tex>. Поделив отношение <tex>A</tex> на это, получим <tex>FirstName = \{Иван, Пётр, Сидор\}</tex>. Поэтому в ответе есть ''Иван Петров'', ''Пётр Петров'' и ''Сидор Петров''.

Зафиксируем <tex>LastName = Сидоров</tex>. Отфильтровав по этому условию отношение <tex>B</tex>, получим <tex>Id = \{3\}</tex>. Поделив отношение <tex>A</tex> на это, получим <tex>FirstName = \{Пётр, Сидор\}</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>A ⋇ B = \pi_X(A) \times \pi_Z(B) \setminus \pi_{XZ}(\pi_X(A) \times B \setminus A \Join B)</tex> — выражение большого деления через простейшие операции реляционной алгебры

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

[[Категория: Базы данных]]

Реляционная алгебра: соединения, деление

2021-12-14T15:57:58Z

Masmirnov: Соединения

=Соединения=

{{Определение
|definition=
'''Соединение''' (англ. ''Join'') — общее наименование для бинарных операторов на отношениях, позволяющих некоторым образом соединить данные из нескольких отношений в одно.
}}
==Полное соединение==

{{Определение
|definition=
'''Полным''', или '''декартовым соединением''' (англ. ''Cross join'', ''Cartesian join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex>, у которых нет общих атрибутов, называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а тело — декартовым произведением тел <tex>R_1</tex> и <tex>R_2</tex>. Обозначение: <tex>R_1 \times R_2</tex>
}}
В случае, если у двух отношений есть хотя бы один общий атрибут в заголовке, их полное соединение не определено.

===Пример===

Рассмотрим два отношения:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id1'''
!'''FirstName'''
|-
|1
|Иван
|-
|2
|Пётр
|-
|3
|Сидор
|}
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id2'''
!'''LastName'''
|-
|1
|Иванов
|-
|3
|Петров
|-
|4
|Сидоров
|}
Их полным соединением будет следующее отношение:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id1'''
!'''FirstName'''
!'''Id2'''
!'''LastName'''
|-
|1
|Иван
|1
|Иванов
|-
|1
|Иван
|3
|Петров
|-
|1
|Иван
|4
|Сидоров
|-
|2
|Пётр
|1
|Иванов
|-
|2
|Пётр
|3
|Петров
|-
|2
|Пётр
|4
|Сидоров
|-
|3
|Сидор
|1
|Иванов
|-
|3
|Сидор
|3
|Петров
|-
|3
|Сидор
|4
|Сидоров
|}

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

{{Определение
|definition=
'''Естественным соединением''' (англ. ''Natural join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а тело состоит из кортежей, полученных всевозможными соединениями кортежей <tex>R_1</tex> и <tex>R_2</tex>, имеющих равные значения одноимённых атрибутов. Обозначение: <tex>R_1 \Join R_2</tex>
}}
===Пример===

Рассмотрим два отношения:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
|-
|1
|Иван
|-
|2
|Пётр
|-
|3
|Сидор
|}
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''LastName'''
|-
|1
|Иванов
|-
|1
|Петров
|-
|2
|Сидоров
|}
Их естественным соединением будет следующее отношение:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
!'''LastName'''
|-
|1
|Иван
|Иванов
|-
|1
|Иван
|Петров
|-
|2
|Пётр
|Сидоров
|}

===Свойства===

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

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

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

{{Определение
|definition=
'''Левым соединением''' (англ. ''Left join'' или ''Left outer join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а тело состоит из кортежей, полученных всевозможными соединениями кортежей <tex>R_1</tex> и <tex>R_2</tex>, имеющих равные значения одноимённых атрибутов. Если по одноимённым атрибутам кортежу из <tex>R_1</tex> не соответствует ни одного кортежа из <tex>R_2</tex>, то в результат добавляется этот кортеж из <tex>R_1</tex>, дополненный пустыми значениями. Обозначение: <tex>R_1 \, ⟕ \, R_2</tex>
}}
{{Определение
|definition=
'''Правым соединением''' (англ. ''Right join'' или ''Right outer join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а тело состоит из кортежей, полученных всевозможными соединениями кортежей <tex>R_1</tex> и <tex>R_2</tex>, имеющих равные значения одноимённых атрибутов. Если по одноимённым атрибутам кортежу из <tex>R_2</tex> не соответствует ни одного кортежа из <tex>R_1</tex>, то в результат добавляется этот кортеж из <tex>R_2</tex>, дополненный пустыми значениями. Обозначение: <tex>R_1 \, ⟖ \, R_2</tex>
}}
{{Определение
|definition=
'''Внешним соединением''' (англ. ''Outer join'' или ''Full outer join'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок является объединением заголовков <tex>R_1</tex> и <tex>R_2</tex>, а тело состоит из кортежей, полученных всевозможными соединениями кортежей <tex>R_1</tex> и <tex>R_2</tex>, имеющих равные значения одноимённых атрибутов. Если по одноимённым атрибутам кортежу из одного отношения не соответствует ни одного кортежа из другого, то в результат добавляется этот кортеж, дополненный пустыми значениями. Обозначение: <tex>R_1 \, ⟗ \, R_2</tex>
}}
===Пример===

Рассмотрим два отношения (<tex>R_1</tex> и <tex>R_2</tex> соответственно):
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
|-
|1
|Иван
|-
|2
|Пётр
|-
|3
|Сидор
|}
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''LastName'''
|-
|1
|Иванов
|-
|1
|Петров
|-
|3
|Сидоров
|-
|4
|Плюшкин
|}
Тогда <tex>R_1 \, ⟕ \, R_2</tex> (левое соединение) равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
!'''LastName'''
|-
|1
|Иван
|Иванов
|-
|1
|Иван
|Петров
|-
|2
|Пётр
|
|-
|3
|Сидор
|Сидоров
|}
<tex>R_1 \, ⟖ \, R_2</tex> (правое соединение) равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
!'''LastName'''
|-
|1
|Иван
|Иванов
|-
|1
|Иван
|Петров
|-
|3
|Сидор
|Сидоров
|-
|4
|
|Плюшкин
|}
<tex>R_1 \, ⟗ \, R_2</tex> (внешнее соединение) равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
!'''LastName'''
|-
|1
|Иван
|Иванов
|-
|1
|Иван
|Петров
|-
|2
|Пётр
|
|-
|3
|Сидор
|Сидоров
|-
|4
|
|Плюшкин
|}

===Свойства===

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

* <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_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_2 \, ⟖ \, R_1</tex>
* <tex>R_1 \, ⟗ \, R_2 = (R_1 \, ⟕ \, R_2) \cup (R_1 \, ⟖ \, R_2)</tex>

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

{{Определение
|definition=
'''Левым полусоединением''' (англ. ''Left semijoin'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок равен заголовку <tex>R_1</tex>, а тело состоит из кортежей в <tex>R_1</tex>, для которых существует кортеж из <tex>R_2</tex> с равными значениями одноимённых атрибутов. Обозначение: <tex>R_1 \ltimes R_2</tex>
}}
{{Определение
|definition=
'''Правым полусоединением''' (англ. ''Right semijoin'') двух отношений <tex>R_1</tex> и <tex>R_2</tex> называется отношение, в котором заголовок равен заголовку <tex>R_2</tex>, а тело состоит из кортежей в <tex>R_2</tex>, для которых существует кортеж из <tex>R_1</tex> с равными значениями одноимённых атрибутов. Обозначение: <tex>R_1 \rtimes R_2</tex>
}}
===Пример===

Рассмотрим два отношения (<tex>R_1</tex> и <tex>R_2</tex> соответственно):
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
|-
|1
|Иван
|-
|2
|Пётр
|-
|3
|Сидор
|}
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''LastName'''
|-
|1
|Иванов
|-
|1
|Петров
|-
|3
|Сидоров
|-
|4
|Плюшкин
|}
Тогда <tex>R_1 \ltimes R_2</tex> (левое полусоединение) равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''FirstName'''
|-
|1
|Иван
|-
|3
|Сидор
|}
<tex>R_1 \rtimes R_2</tex> (правое полусоединение) равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''LastName'''
|-
|1
|Иванов
|-
|1
|Петров
|-
|3
|Сидоров
|}

===Свойства===

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

* <tex>R_1 \ltimes R_2 = \pi_{R_1}(R_1 \Join R_2)</tex>
* <tex>R_1 \rtimes R_2 = \pi_{R_2}(R_1 \Join R_2)</tex>
* <tex>R_1 \ltimes R_2 = R_2 \rtimes R_1</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_2 \setminus (R_1 \rtimes R_2))</tex>
* <tex>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))</tex>

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

{{Определение
|definition=
'''Условным соединением''' (англ. ''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 \times_{\theta} R_2</tex>
}}
{{Определение
|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>
}}
{{Определение
|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>
}}
{{Определение
|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>
}}
===Пример===

Рассмотрим два отношения (<tex>R_1</tex> и <tex>R_2</tex> соответственно):
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id1'''
!'''FirstName'''
|-
|1
|Иван
|-
|2
|Пётр
|-
|3
|Сидор
|}
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id2'''
!'''LastName'''
|-
|1
|Иванов
|-
|1
|Петров
|-
|3
|Сидоров
|-
|4
|Плюшкин
|}
Тогда <tex>R_1 ⟕_{\text{length(FirstName)}+2<\text{length(LastName)}} R_2</tex> равно:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id1'''
!'''FirstName'''
!'''Id2'''
!'''LastName'''
|-
|1
|Иван
|3
|Сидоров
|-
|1
|Иван
|4
|Плюшкин
|-
|2
|Пётр
|3
|Сидоров
|-
|2
|Пётр
|4
|Плюшкин
|-
|3
|Сидор
|
|
|}

===Свойства===

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

* <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_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_1 ⟕_{\theta} R_2) \cup (R_1 ⟖_{\theta} R_2)</tex>

=Деление=

==Деление==

'''TODO'''

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

'''TODO'''

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

[[Категория: Базы данных]]

Реляционная алгебра: соединения, деление

2021-12-14T11:46:08Z

Masmirnov: Структура страницы; полное соединение

Базы данных

2021-12-14T10:37:53Z

Masmirnov:

http://www.kgeorgiy.info/courses/dbms/index.html

==Ответник==

# [[Развитие баз данных]]
# [[Архитектура современной СУБД]]
# [[Физическая модель базы данных]]
# [[Модель сущность-связь]]
# [[Преобразование модели сущность-связь в физическую модель]]
# [[Реляционная модель данных. Ключи]]
# [[Функциональные зависимости: замыкание, эквивалентность и правила вывода]]
# [[Функциональные зависимости: замыкание атрибутов, неприводимые множества функциональных зависимостей, их построение]]
# [[Цели и средства нормализации]]
# [[Нормальные формы: первая и вторая]]
# [[Нормальные формы: третья и Бойса-Кодда]]
# [[Многозначные зависимости и четвертая нормальная форма]]
# [[Зависимости соединения и пятая нормальная форма]]
# [[Процесс нормализации и другие нормальные формы]]
# [[Реляционная алгебра]]
# [[Реляционная алгебра: унарные операции]]
# [[Реляционная алгебра: операции над множествами]]
# [[Реляционная алгебра: соединения, деление]]
# [[Реляционная алгебра: деление и операции над данными|Реляционная алгебра: операции над данными]]
# [[Исчисление кортежей и его реляционная полнота]]
# [[Исчисление доменов и его реляционная полнота]]
# [[Datalog и рекурсия]]
# [[Целостность данных. Триггеры]]
# [[Представления и их обновление]]
# [[Управление доступом к данным]]
# [[Подсистема хранения данных]]
# [[Индексация данных. Упорядоченные и хеш-индексы]]
# [[Индексация данных. Другие типы индексов. Применение индексов]]
# [[Хранимые процедуры и функции. Сходства и различия]]
# [[Императивное подмножество SQL]]
# [[Data Control Language]]
# [[Курсоры]]
# [[Хранимые функции]]
# [[Транзакции. Восстановление. Классический алгоритм]]
# [[Транзакции. Восстановление. Алгоритм ARIES]]
# [[Транзакции. Параллельное исполнение. Блокировки]]
# [[Транзакции. Параллельное исполнение. Уровни изоляции]]
# [[Этапы обработки запроса. Перезапись запросов]]
# [[Оптимизация запросов. Выбор структуры исполнения запроса]]
# [[Оптимизация запросов. Выбор методов исполнения запроса]]
# [[Оптимизация запросов. Оценка размера и распределения]]
# [[Секционирование]]
# [[Репликация]]
# [[Распределенные транзакции]]
# [[Распределенные базы данных. Цели и проблемы]]
# [[Иерархические данные. Модель близости]]
# [[Иерархические данные. Вложенные множества]]
# [[Иерархические данные. Модель путей]]
# [[Временны́е данные. Полутемпоральные базы данных]]
# [[Временны́е данные. Модель интервалов]]
# [[Временны́е данные. Модель событий]]
# [[ORM. Ключи и ссылки]]
# [[ORM. Наследование]]
# [[ORM. Модель сущность-атрибут-значение]]

=== [[Практические навыки по Базам данных|Практические навыки]] ===

Используем категорию <nowiki>[[Категория: Базы данных]]</nowiki>

[[Категория: Базы данных]]