Занятие 09 посвящено фундаментальной реляционной операции — соединению отношений (JOIN). В реляционной модели данных Эдгара Кодда нормализованные сущности декомпозируются по отдельным отношениям, чтобы избежать аномалий обновления, удаления и вставки. Однако для решения прикладных аналитических и транзакционных задач данные необходимо собирать воедино. Операция соединения связывает кортежи двух и более отношений по определенному логическому предикату.
Цели занятия:
| Этап занятия | Основной (80 мин) | Сокращенный (60 мин) | Методическое содержание и деятельность преподавателя |
|---|---|---|---|
| 1. Организационный момент и мотивация | 00:00 – 00:05 (5 мин) | 00:00 – 00:05 (5 мин) | Приветствие, фиксация присутствующих. Постановка инженерной проблемы: почему нельзя хранить всю предметную область в одной гигантской таблице Excel и как восстановить целостную картину из нормализованных таблиц без потери связности. |
| 2. Актуализация базовых понятий | 00:05 – 00:15 (10 мин) | 00:05 – 00:12 (7 мин) | Фронтальный опрос: декартово произведение $R \times S$, мощность множества $|R| \times |S|$, предикат селекции $\sigma_P$. Разбор понятия ключа связи (Primary Key — Foreign Key). |
| 3. Изложение нового теоретического материала | 00:15 – 00:45 (30 мин) | 00:12 – 00:35 (23 мин) |
Интерактивная лекция с демонстрацией презентации:
|
| 4. Практический тренинг и моделирование | 00:45 – 00:70 (25 мин) | 00:35 – 00:52 (17 мин) | Самостоятельная работа студентов в интерактивном рабочем листе zanyatie.html по 4 вариантам. Преподаватель выступает в роли архитектора-консультанта, отслеживает типичные ошибки вычисления размерности схем и потери записей. |
| 5. Рефлексия, подведение итогов и инструктаж | 00:70 – 00:80 (10 мин) | 00:52 – 00:60 (8 мин) | Критериальный разбор решений по закрытой рубрике (.rubrika.md), анализ опасности картезианского взрыва, инструктаж по резервному заданию domashnee_zadanie.html. |
В реляционной алгебре общее соединение (тета-соединение) определяется как операция над отношениями $R(A_1, \dots, A_n)$ и $S(B_1, \dots, B_m)$, задаваемая выражением:
$$R \bowtie_\theta S = \sigma_\theta (R \times S)$$
где $\theta$ — логическое условие вида $A_i \odot B_j$, а оператор сравнения $\odot \in \{=, <, \le, >, \ge, \ne\}$.
Если оператор сравнения — строго равенство ($\odot$ есть $=$), операция называется эквисоединением (Equi-Join). Важно подчеркнуть студентам, что в схеме результирующего отношения эквисоединения сохраняются оба атрибута: и $A_i$, и $B_j$, значения которых идентичны.
Естественное соединение $R \bowtie S$ — частный случай эквисоединения по всем атрибутам с одинаковыми именами в схемах $R$ и $S$, при котором:
Внутреннее соединение (Inner Join) отбрасывает кортежи одного отношения, для которых не найдено пары в другом отношении. Это приводит к безвозвратной потере информации при формировании сводок. Для сохранения «одиноких» кортежей Кодд ввел внешние соединения:
"" и не пробел. Это индикатор отсутствия значения или неопределенности. В реляционной алгебре NULL порождает трехзначную логику Лукасевича (3VL: True, False, Unknown). Предикат сравнения NULL = NULL возвращает UNKNOWN, а не TRUE. Поэтому кортежи со значением NULL в ключевых атрибутах никогда не соединяются между собой в классическом эквисоединении.
Эти операции критически важны для понимания работы предикатов EXISTS / IN и оптимизации запросов в СУБД:
Преподаватель обязан показать студентам разрыв между декларативной реляционной формулой и физическим исполнением на дисках и в оперативной памяти:
| Алгоритм соединения | Принцип работы | Временная сложность | Оптимальные условия применения |
|---|---|---|---|
| Nested Loop Join (Вложенные циклы) | Для каждой строки внешнего отношения сканируется внутреннее отношение. При наличии индекса по ключу соединения во внутренней таблице — Index Nested Loop. | $O(|R| \cdot |S|)$ в наивном виде; $O(|R| \cdot \log |S|)$ с индексом. | Одно отношение мало (десятки строк), а на втором есть B-Tree индекс; высокоселективные OLTP-запросы. |
| Hash Join (Хэш-соединение) | Фаза Build: по меньшему отношению в оперативной памяти строится хэш-таблица по ключу соединения. Фаза Probe: сканируется второе отношение, вычисляется хэш ключа и проверяются кортежи. | $O(|R| + |S|)$ в идеале при помещении хэш-таблицы в RAM. | Большие неиндексированные таблицы, эквисоединения в OLAP и хранилищах данных (DWH). Не работает для неравенств ($<, >$). |
| Sort Merge Join (Слияние сортировкой) | Оба отношения предварительно сортируются по ключам соединения, затем два курсора одновременно движутся по потокам, выполняя слияние за один проход. | $O(|R| \log |R| + |S| \log |S|)$; если уже отсортированы — $O(|R| + |S|)$. | Данные уже отсортированы (например, читаются по кластерному индексу), либо условие соединения содержит операторы неравенства ($\le, \ge$). |
WHERE department_id = NULL.
NULL = NULL равен UNKNOWN, и СУБД отфильтровывает такие строки. Корректная конструкция — IS NULL.
На практическом этапе обучающиеся открывают файл zanyatie.html в браузере. Лист содержит 4 индивидуальных варианта, покрывающих все типы соединений:
Оценивание решений осуществляется строго по закрытой 4-балльной рубрике (.rubrika.md). Рабочий лист сохраняет введенные данные в localStorage и адаптирован для печати на формате А4.