Конспект лекции: Реляционная алгебра — Соединение

Дисциплина: ОП.08 Основы проектирования баз данных
Раздел: Тема 2. Взаимосвязи в моделях и реляционный подход к построению моделей (§2.2 с.7 программы)

1. Введение: почему соединение — центральная операция РМД

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

Однако для пользователя базы данных ценность представляют не изолированные идентификаторы, а целостные информационные сводки: «Какой клиент, когда, какой товар приобрел и через какой филиал банка оплатил покупку?».

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

2. Пошаговая блок-схема: от декартова произведения к соединению

Теоретический фундамент любого соединения — это композиция двух базовых операций: Декартова произведения (Cartesian Product, $\times$) и Селекции (Selection, $\sigma$).

Отношения на входе: Заданы два отношения $R(A_1, \dots, A_n)$ мощностью $|R|$ и $S(B_1, \dots, B_m)$ мощностью $|S|$.

Вычисление декартова произведения ($R \times S$): Формируется множество из всех возможных комбинаций кортежей. Мощность результата составляет $|R| \cdot |S|$, а степень (число атрибутов) — $n + m$.

Проверка логического предиката ($\theta$): К каждой строке применяется условие связи $\theta$ (например, $R.ID\_клиента = S.Клиент\_ID$). Строки, дающие FALSE или UNKNOWN, отбрасываются.

Проекция (для Natural Join): При естественном соединении одноименные атрибуты сливаются в один столбец, устраняя дублирование ключа.

Рис 1. Концептуальный конвейер выполнения реляционного соединения через селекцию декартова произведения

3. Классификация типов соединения с диаграммами Венна и примерами

Для наглядности разберем все операции на едином модельном примере двух отношений:

Отношение R: Студенты

Студент_ID	ФИО	Группа
101	Иванов А.	ИС-21
102	Петров Б.	ИС-21
103	Сидоров В.	ИС-22

Отношение S: Стипендии

Студент_ID	Сумма_руб	Категория
101	4500	Академическая
103	7000	Повышенная
104	5000	Социальная

Обратите внимание: студент 102 (Петров) не получает стипендию. А стипендия для студента 104 назначена, но сам студент еще не внесен в таблицу студентов.

3.1. Внутреннее / Естественное соединение (Inner / Natural Join, $\bowtie$)

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

Рис 2. Диаграмма Венна: Внутреннее (естественное) пересечение множеств

Студент_ID	ФИО	Группа	Сумма_руб	Категория
101	Иванов А.	ИС-21	4500	Академическая
103	Сидоров В.	ИС-22	7000	Повышенная

3.2. Левое внешнее соединение (Left Outer Join, $R ⟕ S$)

Сохраняет абсолютно все строки левого отношения $R$ (Студенты). Если у студента нет стипендии (Петров, 102), поля таблицы стипендий заполняются маркером NULL.

Рис 3. Диаграмма Венна: Left Outer Join (все из R + совпадения из S)

Студент_ID	ФИО	Группа	Сумма_руб	Категория
101	Иванов А.	ИС-21	4500	Академическая
102	Петров Б.	ИС-21	NULL	NULL
103	Сидоров В.	ИС-22	7000	Повышенная

3.3. Правое внешнее соединение (Right Outer Join, $R ⟖ S$)

Сохраняет все строки правого отношения $S$ (Стипендии). Для не привязанной стипендии 104 поля студента заполняются маркером NULL.

Студент_ID	ФИО	Группа	Сумма_руб	Категория
101	Иванов А.	ИС-21	4500	Академическая
103	Сидоров В.	ИС-22	7000	Повышенная
104	NULL	NULL	5000	Социальная

3.4. Полное внешнее соединение (Full Outer Join, $R ⟗ S$)

Объединение результатов левого и правого внешних соединений. Сохраняет кортежи из обоих отношений без потерь.

Рис 4. Диаграмма Венна: Full Outer Join (полное объединение непарных кортежей)

Студент_ID	ФИО	Группа	Сумма_руб	Категория
101	Иванов А.	ИС-21	4500	Академическая
102	Петров Б.	ИС-21	NULL	NULL
103	Сидоров В.	ИС-22	7000	Повышенная
104	NULL	NULL	5000	Социальная

3.5. Полусоединение ($R \ltimes S$) и Антисоединение ($R \rhd S$)

Полусоединение ($R \ltimes S$): извлекает кортежи $R$, у которых есть стипендия. Схема содержит только атрибуты отношения R:

Студент_ID	ФИО	Группа
101	Иванов А.	ИС-21
103	Сидоров В.	ИС-22

Антисоединение ($R \rhd S$): извлекает кортежи $R$, у которых нет соответствия в $S$ (студенты без стипендии). Это реляционный аналог конструкции WHERE NOT EXISTS:

Студент_ID	ФИО	Группа
102	Петров Б.	ИС-21

4. Проблема NULL и трехзначная логика (3VL)

Фундаментальное правило: Значение NULL означает «неизвестно» (UNKNOWN). В связи с этим:

NULL = NULL дает результат UNKNOWN, а не TRUE!
NULL <> 5 дает результат UNKNOWN!
В реляционной фильтрации кортеж попадает в результат только тогда, когда логическое выражение дает строго TRUE.

Именно поэтому два кортежа, содержащие NULL в ключевых атрибутах, при обычном соединении не соединятся. Для проверки отсутствия данных используется специальный предикат IS NULL.

5. Физические алгоритмы реализации соединения в СУБД

Когда СУБД получает декларативный запрос, оптимизатор выбирает один из трех физических алгоритмов:

Nested Loop Join: Вложенный цикл. Для каждой строки таблицы $R$ СУБД ищет совпадение в таблице $S$. Если в $S$ есть B-Tree индекс по ключу соединения, сложность составляет $O(|R| \log |S|)$.
Hash Join: В оперативной памяти строится хэш-таблица по ключам меньшей таблицы (Build-фаза). Затем большая таблица последовательно сканируется (Probe-фаза). Идеально для больших объемов данных при равенстве ключей.
Sort Merge Join: Обе таблицы сортируются по ключу соединения, после чего параллельно сканируются курсорами. Эффективно, если данные уже физически отсортированы на диске (кластерный индекс).

6. Вопросы для самопроверки

Вопрос 1: В чем ключевое отличие эквисоединения от естественного соединения?

Ответ: В схеме эквисоединения сохраняются оба ключевых атрибута из обоих отношений (с дублированием). В естественном соединении одноименные атрибуты сливаются в один столбец.

Вопрос 2: Чему равна мощность естественного соединения двух отношений, если они не имеют общих атрибутов?

Ответ: Мощность равна $|R| \cdot |S|$, так как естественное соединение при отсутствии общих атрибутов вырождается в декартово произведение.

Вопрос 3: Почему операция соединения по условию равенства не связывает строки, у которых ключ равен NULL?

Ответ: Потому что предикат равенства NULL = NULL в трехзначной логике вычисляется в UNKNOWN, а операторы реляционной селекции отбирают только строки со значением TRUE.

Вопрос 4: Чем полусоединение (Semi-Join) отличается от обычного внутреннего соединения?

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