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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Структура страницы; полное соединение)
 
(Соединения)
Строка 97: Строка 97:
 
==Естественное соединение==
 
==Естественное соединение==
  
−
'''TODO'''
+
{{Определение
 +
|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>)
  
 
==Внешние соединения==
 
==Внешние соединения==
  
−
'''TODO'''
+
{{Определение
 +
|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>
  
 
==Полусоединения==
 
==Полусоединения==
  
−
'''TODO'''
+
{{Определение
 +
|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'''
  
−
=Деление=
+
==Большое деление==
  
 
'''TODO'''
 
'''TODO'''
 +
 +
=Литература=
 +
* ''Дейт К.'' Введение в системы баз данных (глава 7)
 +
* ''Уидом Д., Ульман Д.'' Основы реляционных баз данных (главы 4 и 5)
 +
 +
[[Категория: Базы данных]]

Версия 18:57, 14 декабря 2021

Соединения

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

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

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

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

Пример

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

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

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

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

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

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

Пример

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

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

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

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

Свойства

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

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

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

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


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


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

Пример

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

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

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

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

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

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

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

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

Свойства

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

  • [math]R_1 \, ⟕ \, R_2 = (R_1 \Join R_2) \cup (R_1 \setminus \pi_{R_1}(R_1 \Join R_2))[/math]
  • [math]R_1 \, ⟖ \, R_2 = (R_1 \Join R_2) \cup (R_2 \setminus \pi_{R_2}(R_1 \Join R_2))[/math]
  • [math]R_1 \, ⟗ \, R_2 = (R_1 \Join R_2) \cup (R_1 \setminus \pi_{R_1}(R_1 \Join R_2)) \cup (R_2 \setminus \pi_{R_2}(R_1 \Join R_2))[/math]

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

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

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

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


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

Пример

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

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

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

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

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

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

Свойства

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

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

Из соответствующих свойств внешних соединений следует:

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

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

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


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


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


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

Пример

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

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

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

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

Свойства

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

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

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

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

Деление

Деление

TODO

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

TODO

Литература

  • Дейт К. Введение в системы баз данных (глава 7)
  • Уидом Д., Ульман Д. Основы реляционных баз данных (главы 4 и 5)
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Реляционная_алгебра:_соединения,_деление&oldid=81362»