Реляционная модель

Предпосылки: базовое программирование (переменные, типы, функции).

Интернет-магазин хранит данные о сотрудниках, отделах, заказах и клиентах. Эти данные связаны между собой: сотрудник работает в отделе, заказ принадлежит клиенту и обслуживается сотрудником. Первый вопрос, на который нужно ответить, прежде чем писать запросы — как организовать эти данные так, чтобы они оставались корректными и чтобы на любой вопрос можно было получить ответ.

Плоская таблица и её проблемы

Самый простой способ — сложить всё в одну таблицу, как в электронной таблице:

 id | name   | dept_name   | dept_budget | salary | hire_date
----+--------+-------------+-------------+--------+------------
  1 | Анна   | engineering |      500000 |  90000 | 2021-03-15
  2 | Борис  | sales       |      300000 |  60000 | 2020-07-01
  3 | Вера   | engineering |      500000 |  85000 | 2022-01-10
  4 | Глеб   | sales       |      300000 |  70000 | 2019-11-20
  5 | Дина   | engineering |      500000 |  NULL  | 2023-06-01

Пока сотрудников мало, это работает. Но бюджет отдела engineering — 500 000 — записан в трёх строках. Бухгалтерия сообщает, что бюджет вырос до 550 000. Обновили строку Анны, забыли Веру и Дину. Теперь в таблице два разных бюджета для одного отдела — какой из них правильный? Это аномалия обновления (update anomaly, англ. «аномалия при обновлении»): изменение одного факта требует обновления нескольких строк, и пропуск хотя бы одной делает данные противоречивыми.

Есть и другие проблемы. Компания открывает отдел HR с бюджетом 150 000, но сотрудников туда ещё не наняли. В плоской таблице нельзя записать отдел без хотя бы одного сотрудника — строке нужны id, name, salary. Это аномалия вставки (insertion anomaly): невозможно зафиксировать факт о сущности, пока не появится связанная с ней запись. Обратная ситуация: Глеб — единственный оставшийся сотрудник отдела sales. Его увольняют, строку удаляют — и вместе с ней исчезает вся информация об отделе sales, включая его бюджет. Это аномалия удаления (deletion anomaly).

Все три аномалии возникают по одной причине: в одной строке смешаны два независимых факта — информация о сотруднике и информация об отделе. Когда два факта склеены, изменение одного затрагивает другой.

Дореляционный мир

Проблема организации связанных данных возникла задолго до электронных таблиц. В 1960-х годах первые промышленные СУБД — IBM IMS (1966) для программы Apollo и системы на основе стандарта CODASYL — предложили свои решения.

IMS организовала данные как дерево (иерархическая модель): отделы — корневые узлы, сотрудники — дочерние. Запрос «все сотрудники отдела engineering» — быстрый спуск по одной ветке. Но запрос «все сотрудники с зарплатой выше 80 000 независимо от отдела» требовал обхода каждой ветки дерева и проверки каждого дочернего узла. Путь доступа к данным был заложен в саму структуру: дерево оптимизировано под один тип вопросов, а все остальные — дорогие.

CODASYL обобщил дерево до графа (сетевая модель): запись могла иметь несколько родителей, что позволяло выражать более сложные связи. Но программист по-прежнему навигировал по этому графу вручную: «перейти к отделу, перейти к первому сотруднику, перейти к следующему, проверить зарплату…». Программа была переплетена с физической структурой данных. Если администратор базы реорганизовывал хранение на диске для ускорения — программы переставали работать.

Общая проблема обеих моделей — зависимость от пути доступа (data dependence). Логический вопрос («кто зарабатывает больше 80 000?») неотделим от физической навигации («начать с корня, спуститься по левой ветке, проверить каждого ребёнка…»). Изменение структуры хранения означает переписывание программ. Добавление нового типа связи (сотрудники обрабатывают заказы) означает перестройку всего дерева или графа.

Модель Кодда: независимость данных

В 1970 году Эдгар Кодд, математик из IBM Research, опубликовал статью «A Relational Model of Data for Large Shared Data Banks» в Communications of the ACM. Центральная проблема, которую он решал — независимость данных (data independence): приложения и пользователи должны работать с данными, не зная и не завися от того, как именно эти данные хранятся на диске. В иерархической и сетевой моделях логический и физический уровни были склеены — программа навигировала по конкретной структуре хранения. Кодд предложил поставить между ними абстракцию: пользователь описывает что он хочет получить, а СУБД сама решает как это достать.

Инструментом для этого разделения стала математика. Кодд описал данные как отношения (relation, от лат. relatio — «соотнесение») — понятие из теории множеств. Отношение — это множество кортежей (tuple, от лат. -pla/-plum — упорядоченная последовательность значений) с одинаковой структурой. Каждый кортеж состоит из атрибутов (attribute, от лат. attributum — «приданное свойство») — именованных значений из определённого домена (domain — область допустимых значений). Математическая модель не самоцель — она гарантирует, что логическое представление данных не зависит от физической реализации. Отношение описывает только структуру данных, ничего не говоря о том, хранятся ли они в отсортированном дереве, в плоском файле или в оперативной памяти.

В терминах SQL, которые используются на практике: отношение — это таблица (table), кортеж — строка (row), атрибут — столбец (column), домен — тип данных столбца. Формальные термины (отношение, кортеж, атрибут) встречаются в академической литературе и спецификациях. В остальных заметках этого курса используются SQL-термины.

Вернёмся к интернет-магазину. Вместо одной плоской таблицы данные разделяются на два отношения — departments и employees:

departments                       employees
 id | name        | budget         id | name   | department_id | salary
----+-------------+--------       ----+--------+---------------+--------
  1 | engineering |  500000         1 | Анна   |             1 |  90000
  2 | sales       |  300000         2 | Борис  |             2 |  60000
  3 | hr          |  150000         3 | Вера   |             1 |  85000
                                    4 | Глеб   |             2 |  70000
                                    5 | Дина   |             1 |   NULL

Бюджет каждого отдела записан ровно один раз — в таблице departments. Обновление бюджета engineering до 550 000 — это изменение одной строки. Аномалия обновления исчезла. Отдел HR существует в departments без единого сотрудника — аномалия вставки исчезла. Удаление последнего сотрудника из sales не затрагивает таблицу departments — аномалия удаления исчезла. Процесс разделения плоской таблицы на несколько связанных для устранения аномалий называется нормализацией (normalization, от лат. norma — «правило, образец»).

Связь между сотрудником и отделом выражается через значение department_id: столбец в employees ссылается на id в departments. Это не физическая ссылка (указатель в памяти, ветка дерева), а логическая — совпадение значений. СУБД может хранить эти таблицы в любом физическом формате: на одном диске или на разных, в произвольном порядке, с любыми внутренними структурами. Пока пользователь видит логическое представление — две таблицы со столбцами и строками — программы работают. Именно это и есть независимость данных на практике: администратор перестраивает хранение, добавляет индексы, перемещает данные между серверами — а SQL-запросы остаются прежними.

Свойства отношений

Отношение в математике — множество кортежей, а множество не имеет порядка и не содержит дубликатов. SQL отступает от математического определения: таблица — это мультимножество (multiset, bag, англ. «мешок») — коллекция, допускающая одинаковые строки. Запрос SELECT dept_name FROM employees над плоской таблицей из первого примера вернул бы пять строк, включая три повторения «engineering». Дубликаты не удаляются автоматически — для этого нужен явный инструмент (DISTINCT, который рассматривается в сортировке и ограничении).

Строки в таблице не имеют порядка. В отличие от массива, где у каждого элемента есть индекс (0, 1, 2…), таблица — неупорядоченная коллекция. PostgreSQL хранит строки в произвольном физическом порядке, и то, что «Анна» отображается первой — случайность, не гарантия. Если нужен порядок в результате (сотрудники по дате найма, от старших к новым), его нужно явно запросить через ORDER BY.

У каждого столбца есть фиксированный тип данных: salary хранит целые числа, name — текст, hire_date — дату. Записать в salary текст «девяносто тысяч» нельзя. Это ограничение не бюрократия — оно делает операции осмысленными: сравнение «зарплата больше 80 000» возможно только потому, что столбец содержит числа, а не произвольные строки. Типы данных подробно рассматриваются в следующей заметке.

Реляционная алгебра

Реляционная модель отделила данные от путей доступа. Но как задавать вопросы к данным без навигации по дереву? Кодд определил набор операций, каждая из которых принимает одно или несколько отношений на входе и возвращает новое отношение на выходе. Этот набор — реляционная алгебра (relational algebra), и из этих операций строится каждый SQL-запрос.

Выборка (selection, σ) отвечает на вопрос с условием. «Какие сотрудники зарабатывают больше 80 000?» — выборка берёт таблицу employees и возвращает только те строки, где salary > 80000. В SQL этой операции соответствует WHERE.

Проекция (projection, π) отвечает на вопрос «какие именно данные показать?». «Только имена и зарплаты сотрудников» — проекция берёт таблицу со всеми столбцами и возвращает таблицу с двумя. В SQL это список столбцов в SELECT: SELECT name, salary.

Переименование (rename, ρ) меняет имена атрибутов. Необходимо, когда две таблицы имеют столбцы с одинаковым именем и их нужно отличить. В SQL: AS.

Объединение (union, ∪) отвечает на вопрос «все элементы из обоих множеств». «Все люди, которые являются либо сотрудниками, либо клиентами» — объединяет строки двух таблиц с одинаковой структурой. В SQL: UNION.

Разность (difference, −) — «элементы из первого множества, которых нет во втором». «Сотрудники, которые не являются клиентами». В SQL: EXCEPT.

Декартово произведение (cartesian product, ×) — каждая строка одной таблицы соединяется с каждой строкой другой. Если в employees 5 строк, а в departments 3, результат — 15 строк со всеми возможными комбинациями. Само по себе декартово произведение редко полезно, но в сочетании с выборкой оно даёт самую мощную операцию — соединение.

Соединение (join, ⋈) отвечает на вопрос, связывающий две таблицы. «Для каждого сотрудника — название и бюджет его отдела»: берём employees и departments, находим пары строк, где employees.department_id = departments.id, и объединяем их в одну. В иерархической модели такой запрос возможен только если данные заранее организованы в нужное дерево. В реляционной модели любые две таблицы можно соединить по любому условию. В SQL: JOIN … ON.

Важное свойство реляционной алгебры — замкнутость (closure, англ. «замыкание»): каждая операция принимает отношения и возвращает отношение. Результат одной операции можно подать на вход другой. Запрос «имена сотрудников с зарплатой выше 80 000» — это выборка (строки с salary > 80000), за которой следует проекция (оставить только name), и результат — тоже таблица. Операции можно комбинировать в произвольные цепочки. Подробнее о каждой операции и её SQL-реализации см. в разделе Запросы.

Декларативность SQL

Реляционная алгебра определяет какие операции существуют. Второй принцип Кодда: пользователь должен описывать что ему нужно, а не как это вычислить. SQL — декларативный язык (declarative, от лат. declarare — «объявлять»). Запрос SELECT name FROM employees WHERE salary > 80000 — это вопрос: «имена сотрудников с зарплатой выше 80 000». Он соответствует двум операциям реляционной алгебры — выборке и проекции — но программист не указывает, в каком порядке их выполнять, использовать ли индекс, сканировать ли таблицу целиком или прочитать данные из кеша. СУБД сама выбирает стратегию.

Контраст с иерархической моделью: там программист писал навигационные инструкции — «перейти к корню, спуститься к первому ребёнку, проверить поле, перейти к следующему…». Если администратор базы добавлял индекс или перемещал данные на другой диск, программу нужно было переписывать. В SQL программа остаётся прежней — меняется только внутренняя стратегия СУБД.

Операции реляционной алгебры и их SQL-эквиваленты:

Операция алгебры	SQL
Выборка (σ)	`WHERE`
Проекция (π)	Список столбцов в `SELECT`
Переименование (ρ)	`AS`
Объединение (∪)	`UNION`
Разность (−)	`EXCEPT`
Декартово произведение (×)	`CROSS JOIN`
Соединение (⋈)	`JOIN ... ON`

SQL не является прямой реализацией реляционной алгебры — в нём есть агрегация, группировка, оконные функции, сортировка, которые выходят за рамки базовой алгебры. Но ядро любого SQL-запроса можно выразить через эти семь операций.

Первичный ключ и ссылочная целостность

Каждая строка в таблице должна быть однозначно идентифицируема. Первичный ключ (primary key) — столбец или комбинация столбцов, значение которых уникально для каждой строки. В таблице employees это id: не может быть двух сотрудников с одинаковым id.

Когда таблица employees ссылается на departments через столбец department_id, этот столбец называется внешним ключом (foreign key, англ. «внешний ключ» — ключ, указывающий на другую таблицу). Реляционная модель вводит правило ссылочной целостности (referential integrity): значение внешнего ключа должно указывать на существующую строку в связанной таблице. Нельзя назначить сотрудника в отдел с id = 99, если такого отдела не существует. СУБД проверяет это ограничение автоматически.

В иерархической и сетевой моделях связи между записями были структурными — физические указатели от родителя к ребёнку. Разрыв указателя оставлял «осиротевшие» записи. В реляционной модели связи выражаются через совпадение значений ключей, а целостность гарантируется декларативными правилами, а не физической структурой. Подробнее о ключах и ограничениях — в ограничениях.

Данные для примеров

Все файлы в этом курсе используют один набор таблиц — интернет-магазин. Определения таблиц (CREATE TABLE) и заполнение данными (INSERT) подробно разбираются в DDL. Здесь — минимальный набор для запуска примеров:

CREATE TABLE departments (
    id        integer,
    name      text,
    budget    integer
);
 
INSERT INTO departments VALUES
(1, 'engineering', 500000),
(2, 'sales',       300000),
(3, 'hr',          150000);
 
CREATE TABLE employees (
    id            integer,
    name          text,
    department_id integer,
    salary        integer,
    hire_date     date
);
 
INSERT INTO employees VALUES
(1, 'Анна',    1, 90000,  '2021-03-15'),
(2, 'Борис',   2, 60000,  '2020-07-01'),
(3, 'Вера',    1, 85000,  '2022-01-10'),
(4, 'Глеб',    2, 70000,  '2019-11-20'),
(5, 'Дина',    1, NULL,   '2023-06-01'),
(6, 'Евгений', NULL, 55000, '2024-02-01');
 
CREATE TABLE customers (
    id    integer,
    name  text,
    email text,
    city  text
);
 
INSERT INTO customers VALUES
(1, 'Alice',   'alice@example.com',   'New York'),
(2, 'Bob',     'bob@example.com',     'London'),
(3, 'Charlie', 'charlie@example.com', 'Tokyo');
 
CREATE TABLE orders (
    id          integer,
    customer_id integer,
    employee_id integer,
    total       integer,
    created_at  date
);
 
INSERT INTO orders VALUES
(1, 1, 1, 15000, '2024-01-15'),
(2, 2, 2, 8000,  '2024-02-20'),
(3, 1, 3, 22000, '2024-03-10'),
(4, 3, 1, 5000,  '2024-03-25'),
(5, 2, 4, 12000, '2024-04-05');

Таблица employees — основная для примеров в querying/. departments появляется при изучении JOIN. orders и customers — для сложных многотабличных запросов.

Sources

E.F. Codd, 1970, A Relational Model of Data for Large Shared Data Banks. Communications of the ACM. https://www.seas.upenn.edu/~zives/03f/cis550/codd.pdf
E.F. Codd, 1982, Relational Database: A Practical Foundation for Productivity. Communications of the ACM — Тьюринговская лекция, где Кодд формулирует data independence как центральную цель.
C.J. Date, 2003, An Introduction to Database Systems (8th ed.). Addison-Wesley.
Two-Bit History, 2017, Important Papers: Codd and the Relational Model. https://twobithistory.org/2017/12/29/codd-relational-model.html
PostgreSQL Documentation (v16). https://www.postgresql.org/docs/16/

Типы данных и NULL →

CS Notes

Explorer

relational-model