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

Соединения

Определение:

Соединение (англ. 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)