Skip to content

DataModels-Databases.md

Latest commit

 

History

History
2381 lines (1686 loc) · 180 KB

DataModels-Databases.md

File metadata and controls

2381 lines (1686 loc) · 180 KB
Raw

Оглавление

Общие понятия баз данных

О базе данных

Базой данных (англ. database), БД (англ. DB) называют организованную структуру, которая предназначена для хранения, чтения и изменения данных.

Самой простой базой данных может послужить обычный текстовый файл, однако искать и изменять данные в такой "базе" было бы как минимум неудобно.

Нормализация и денормализация базы данных

Транзакция

О транзакции

Транзакция (англ. transaction) — это логическая единица (logical unit), которая осуществляет доступ к базе данных и, возможно, изменяет данные в ней.

Транзакции работают с данными, используя операции чтения и записи.

Свойства транзакции (ACID)

  • Атомарность (англ. Atomicity) гарантирует, что транзакция не может быть зафиксирована частично: либо выполняются все подоперации транзакции, либо ни одна. Если какая-то операция из последовательности не проходит, то происходит откат (англ. rollback) всей последовательности.
  • Согласованность, консистентность (англ. Consistency). Каждая успешная транзакция фиксирует только допустимый для системы результат. База данных должна быть согласована до и после транзакции, во время проведения транзакции согласованность не требуется.
  • Изолированность (англ. Isolation). Способность базы данных гарантировать, что параллельно выполняющиеся транзакции не мешают друг другу. Во время выполнения транзакции другие параллельные транзакции не должны оказывать влияния на её результат. Требование "дорогое", поэтому в реальных базах транзакции изолируются не полностью: создаются уровни изолированности.
  • Долговечность (англ. Durability). Если пользователь получил подтверждение от системы, что транзакция выполнена, он может быть уверен, что сделанные им изменения не будут отменены из-за какого-либо сбоя. Изменения, сделанные успешно завершённой транзакцией, должны остаться сохранёнными после возвращения системы в работу.

Пример транзакции

Пусть деньги переводятся с одного счёта на другой. Используются две основные операции: вывод денег с одного счёта 1000$ - 100$ = 400$, зачисление их на другой счёт 500$ + 100$ = 600$. Если первая операция удалась, а вторая нет, то происходит откат, поскольку в противном случае имеем несогласованность (inconsistency) данных до и после транзакции: до транзакции на счетах в сумме было 1500$, после — 1400$.

Пример транзакции на SQL

BEGIN TRANSACTION;

-- Операция 1
INSERT INTO Employees (EmployeeID, FirstName, LastName, Position, Salary)
VALUES (104, 'Петр', 'Петров', 'Разработчик', 80000);

-- Установка точки сохранения
SAVEPOINT AfterInsert;

-- Операция 2
UPDATE Employees
SET Salary = Salary * 1.05
WHERE EmployeeID = 104;

-- Возникла ошибка, откат к точке сохранения
ROLLBACK TO SAVEPOINT AfterInsert;

-- Фиксация транзакции
COMMIT;

Уровни изолированности транзакций (Transaction Isolation Levels)

Уровни изолированности транзакций (англ. Transaction Isolation Levels) — фундаментальная концепция в реляционных базах данных, которая определяет, как транзакции изолированы друг от друга и какие “аномалии” могут или не могут возникнуть при одновременном доступе к данным.

Уровни:

  • Чтение неподтверждённых данных (англ. Read Uncommitted) - можно читать неподтверждённые данные (грязное чтение). Грязные чтения, неповторяющиеся чтения, фантомные чтения возможны.
  • Чтение подтверждённых данных (англ. Read Committed) - можно читать лишь подтверждённые данные (грязное чтение невозможно). Неповторяющиеся чтения, фантомные чтения возможны.
  • Повторяемое чтение (англ. Repeatable Read) - все данные, прочитанные в транзакции, будут одинаковыми при повторном чтении. Грязные и неповторяющиеся чтения невозможны. Возможны фантомные чтения.
  • Сериализуемость (англ. Serializable) - полная изолированность, максимальная защита от всех аномалий.

Примеры применения:

-- PostgreSQL
BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE;

-- MySQL
SET TRANSACTION ISOLATION LEVEL REPEATABLE READ;
START TRANSACTION;

Аномалии

  • Грязное чтение (англ. Dirty read) - транзакции читают данные, которые ещё не подтверждены другой транзакцией.
  • Неповторяющееся чтение (англ. Non-repeatable read) - повторное чтение тех же данных возвращает различные значения.
  • Фантомное чтение (англ. Phantom read) - повторное чтение тех же данных возвращает новые строки, добавленные другой транзакцией.

Выбор уровня изолированности

  • Read Committed - максимальная производительность, мало конфликтов.
  • Repeatable read - стабильное чтение, терпимы фантомы
  • Serializable - критичные данные, важно избегать любых конфликтов

Индекс базы данных

Об индексе базы данных

Индекс базы данных (англ. database index) — это структура данных, ускоряющая операции поиска (англ. speed up querying) в заданной таблице (или коллекции) базы данных за счёт хранения дополнительной информации в базе (говоря простыми словами, тех же данных таблицы, но в другом виде, в упорядоченном).

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

По умолчанию записи в таблице (коллекции) могут храниться произвольно (неупорядоченно). И если таблица довольно большая, то последовательный просмотр всех записей может занимать довольно продолжительное время. Индексы приводят данные в такой вид (упорядочивают их), чтобы это ускорило поиск. Например, структура индекса может быть представлена сбалансированным деревом поиска, и тогда скорость поиска будет логарифмичной O(log n) вместо линейной O(n).

Индекс формируется из значений одного или нескольких столбцов таблицы (полей документов коллекции) и указателя на соответствующие строки таблицы (документы коллекции). Также иногда индексы могут создаваться из выражений.

Основные типы индексов:

B-дерево (B-tree)

Наиболее распространённый тип индекса (чаще всего используется по умолчанию). Организован в виде сбалансированного дерева поиска. Когда использовать:

  • Поиск точных значений (например, WHERE id = 10)
  • Поиск диапазонов (WHERE date BETWEEN x AND y)
  • Сортировка (ORDER BY)
  • JOIN по индексированным полям

Недостатки:

  • Менее эффективен при поиске текста по шаблону (например, с LIKE '%search%')
  • Ненужное создание множества таких индексов может снизить производительность при вставке и обновлении записей

Хеш-индексы (Hash Index)

Используют хеш-функции для быстрого поиска по точному соответствию ключа.

Когда использовать:

  • Очень быстрый поиск по точному совпадению (например, WHERE username = 'user123')

Недостатки:

  • Не поддерживают поиск по диапазону (BETWEEN, <, >) или сортировку
  • Не подходят для поиска частичных совпадений
  • Чаще используются в специализированных БД (например, in-memory хранилищах)

Полнотекстовый индекс (Full-Text Index)

Используются для поиска слов или фраз в тексте. Когда использовать:

  • Полнотекстовый поиск по большим текстовым полям (LIKE недостаточно эффективен)

Примеры СУБД:

  • MySQL (MATCH AGAINST)
  • PostgreSQL (GIN, GiST индексы)

Многоколоночные (композитные) индексы (Composite Index)

Состоят из нескольких полей таблицы.

Когда использовать:

  • Запросы, включающие несколько полей одновременно (WHERE name = X AND date = Y)
  • Частые сложные условия с множеством критериев

Важно:

  • Порядок столбцов в индексе очень важен. Первым указывается поле, по которому чаще всего происходит поиск или фильтрация.

Уникальный индекс (Unique Index)

Не допускает повторяющихся значений.

Когда использовать:

  • Поля, значения которых должны быть уникальными (например, email, phone, username)

Частичные индексы (Partial Index)

Индексы, применяемые только к части строк таблицы (по условию). Когда использовать:

  • Если часто выбирается лишь небольшая часть данных (например, только активные пользователи)

Многомерные индексы (R-Tree, GIN, GiST)

Используются для специфических типов данных (пространственные данные, JSON и пр.). Когда использовать:

  • Геоданные (например, геолокации, поиск по карте)
  • JSON-данные с поиском по внутренним полям

Преимущества и недостатки индексов

Количество индексов прямо влияет на производительность

  • Много индексов:
    • ➕ Ускоряет многие запросы на чтение
    • ➖ Значительно замедляет операции записи (INSERT, UPDATE, DELETE), увеличивает размер базы данных, повышает нагрузку на сервер.
  • Недостаточно индексов:
    • ➕ Быстрая запись данных
    • ➖ Медленные запросы на чтение, полное сканирование таблиц, неоптимальная нагрузка на сервер.

Если у таблицы 5 индексов, то при добавлении новой строки база данных должна обновить все 5 индексов, что занимает больше времени, чем без индексов или с одним индексом.

Создавайте индексы только на те поля, которые часто используются в запросах. Избегайте индексов на полях с низкой селективностью (например, пол (мужчина/женщина) — плохой кандидат для индекса, так как пользы почти не принесёт).

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

Индексы ускоряют чтение, но замедляют операции записи (INSERT, UPDATE, DELETE).

  • Используйте индексы осознанно: больше индексов ≠ всегда лучше.
  • Регулярно проверяйте производительность запросов (с помощью EXPLAIN) и оптимизируйте набор индексов.

Курсор

О курсоре

Курсор (англ. cursor) — управляющая структура, которая производит обход записей (англ. traversal) в базе данных.

Принцип работы с курсором похож на работу с итератором (англ. iterator), поскольку курсор позволяет последовательно обработать каждую строку (каждый документ) из выбранного набора строк (документов).

Курсор также можно рассматривать как указатель (pointer) на одну строку таблицы (на один документ). Курсор может ссылаться только на одну строку (один документ) в один момент времени, но может перемещаться к другим строкам при необходимости.

Курсоры подразделяются на явные и неявные.

Явный курсор создаётся разработчиком вручную, неявный курсор создаётся системой автоматически.

Пример курсора в MongoDB

const usersCursor = db.users.find({ role: 'admin' });
/* последовательный перебор всех документов результирующего набора в цикле while */
while (usersCursor.hasNext()) {
   const user = usersCursor.next();
   console.log(user);
}

Пример курсора в SQL

# объявление временных переменных, которые будут использованы для записи данных курсора
DECLARE @id VARCHAR(50);
DECLARE @role VARCHAR(50);
# объявление явного курсора, который будет брать данные столбцов id, role из таблицы users
DECLARE @users_cursor CURSOR FOR
  SELECT id, role
  FROM users
# открытие курсор (наполнение его данными)
OPEN @users_cursor
# последовательное извлечение строк из результирующего набора в цикле WHILTE,
# запись значений в переменные и вывод этих переменных 
WHILE @@FETCH_STATUS = 0
BEGIN
  FETCH NEXT FROM @users_cursor INTO @id, @role
  PRINT @id + ' ' + @role
END
# после извлечения всех строк следует закрыть курсор и освободить занимаемые им ресурсы
CLOSE @users_cursor
# иногда нужно вручную освобождать память курсора (зависит от реализации SQL)
DEALLOCATE @users_cursor

Возможные варианты перемещений с FETCH по результирующему набору строк.

  • FIRST — первая строка.
  • NEXT — следующая строка после текущей.
  • PRIOR — строка, находящаяся перед текущей.
  • LAST — последняя строка.
  • ABSOLUTE int — строка по её абсолютному порядковому номеру int при отсчёте с начала (конца), если перед int знак + (-). Если указать 0, то ничего не вернётся.
  • RELATIVE int — перемещение на int строк вперёд (назад) от текущей, если перед int знак + (-). Если указать 0, то вернётся текущая строка.

Изменение данных таблицы при помощи курсора и CURRENT. Курсор должен быть открыт для операции.

UPDATE new_users
SET ...
WHERE CURRENT OF @sers_cursor

Аналогично можно делать с DELETE.

Масштабирование баз данных

Когда одного сервера базы данных перестаёт хватать, его можно усилить (вертикальное масштабирование) или разделить работу между серверами (горизонтальное) — об этом в заметке про масштабирование. Горизонтально базы масштабируют тремя приёмами:

  • репликация копирует одни и те же данные на несколько серверов;
  • шардинг раскладывает разные данные по разным серверам;
  • партиционирование делит большую таблицу на части.

Приёмы сочетаются: например, в MongoDB каждый шард должен быть развёрнут как набор реплик (документация).

Репликация

Репликация (англ. replication) — постоянное копирование данных с одного сервера на другие. Сервер, который хранит копию, называют репликой (англ. replica).

Обычно все изменения принимает один сервер — ведущий (англ. primary). Остальные — ведомые (англ. standby, secondary) — повторяют его изменения и отвечают на чтение. В MongoDB, например, ведущий получает все операции записи, а вторичные узлы повторяют журнал его операций (документация).

В старых текстах ведущего и ведомых называют мастером (англ. master) и слейвами (англ. slaves). Документация PostgreSQL и MongoDB использует слова primary, standby и secondary.

Синхронная и асинхронная репликация

Главный вопрос — когда ведущий считает запись завершённой.

Асинхронная репликация (англ. asynchronous replication): ведущий подтверждает запись сразу, а ведомые получают изменения чуть позже. В PostgreSQL потоковая репликация по умолчанию асинхронная: между фиксацией транзакции на ведущем и появлением изменений на ведомом есть небольшая задержка (документация). Такую задержку называют отставанием реплики (англ. replication lag). MongoDB предупреждает: чтение со вторичных узлов может вернуть данные, которые ещё не отражают состояние ведущего.

const sleep = (ms: number) => new Promise((resolve) => setTimeout(resolve, ms));

class Replica {
  readonly data = new Map<string, string>();
}

/* ведущий подтверждает запись сразу, а ведомым отправляет её с задержкой */
class Primary extends Replica {
  constructor(private readonly standbys: Replica[], private readonly lagMs: number) {
    super();
  }

  write(key: string, value: string): void {
    this.data.set(key, value);
    for (const standby of this.standbys) {
      setTimeout(() => standby.data.set(key, value), this.lagMs);
    }
  }
}

const standby = new Replica();
const primary = new Primary([standby], 100);

primary.write('user:1:name', 'Max');
console.log(primary.data.get('user:1:name')); // Max
console.log(standby.data.get('user:1:name')); // undefined
await sleep(150);
console.log(standby.data.get('user:1:name')); // Max

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

Синхронная репликация (англ. synchronous replication): фиксация ждёт, пока запись не окажется в журнале на диске и ведущего, и ведомого. Потерять данные можно, только если оба сервера упадут одновременно. Цена — время ответа: каждая пишущая транзакция ждёт как минимум время пути туда и обратно между серверами, а транзакции только для чтения не ждут (PostgreSQL).

О выходе из строя

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

Если выходит из строя ведущий, одного из ведомых повышают до ведущего — это переключение (англ. failover). В MongoDB оно происходит само: если ведущий недоступен, подходящий вторичный узел проводит выборы (англ. election) нового ведущего (документация). PostgreSQL отказ ведущего сам не обнаруживает — для этого нужны внешние инструменты, а повысить ведомого можно командой pg_ctl promote или функцией pg_promote() (документация).

Опасен старый ведущий: если он вернётся и не узнает, что его заменили, оба сервера будут считать себя ведущими, а это ведёт к путанице и в итоге к потере данных. Механизм, который сообщает старому ведущему, что он больше не ведущий, иногда называют STONITH (англ. Shoot The Other Node In The Head). Чтобы вернуться к нормальной работе, нового ведомого создают — на бывшем ведущем, когда тот поднимется, или на другой машине: ведущий и ведомый меняются ролями (PostgreSQL).

Для чего нужна репликация

  • Масштабирование чтения: запросы на чтение можно отправлять на ведомых. В PostgreSQL ведомый, который отвечает на запросы только для чтения, называют горячим резервом (англ. hot standby). Запись так не масштабируется: все изменения по-прежнему идут через ведущего.
  • Отказоустойчивость: копия данных заменит упавший сервер.
  • Отдельные задачи: тяжёлые отчёты можно запускать на отдельной реплике, чтобы они не мешали основной работе. PostgreSQL прямо описывает такие серверы для отчётов: они только снимают с ведущего запросы на чтение и повышать их до ведущего не нужно (документация).

Шардинг

Шардинг (англ. sharding) — распределение данных по нескольким машинам: каждая часть — шард (англ. shard) — хранит своё подмножество данных (MongoDB). Репликация копирует одни и те же данные, а шардинг делит разные, поэтому он распределяет не только чтение, но и запись.

Какой шард хранит запись, решает ключ шардинга (англ. shard key) — одно или несколько полей записи. Например, в социальной сети ключом может быть идентификатор пользователя: все данные одного пользователя окажутся на одном сервере, и их не придётся собирать по частям.

При выборе ключа MongoDB советует смотреть на три вещи (документация):

  • кардинальность — сколько разных значений у ключа;
  • частоту — как часто встречается каждое значение;
  • монотонность — растёт ли ключ всё время. Если ключ только растёт (время создания, счётчик), все новые записи попадают в один и тот же шард, и он становится узким местом для записи.

Два способа разложить данные по ключу:

  • по диапазонам (англ. ranged sharding): близкие значения ключа лежат рядом, поэтому запросы по диапазону («заказы за сентябрь») идут в один шард (MongoDB);
  • по хешу (англ. hashed sharding): данные распределяются равномернее, но близкие значения разлетаются по разным шардам, и запрос по диапазону приходится рассылать на все (англ. broadcast) (MongoDB).

Сложнее всего — добавить шард. Если номер шарда — остаток от деления хеша ключа на число шардов, то при переходе с четырёх шардов на пять переедет почти всё:

import { createHash } from 'node:crypto';

const hash = (key: string) => createHash('md5').update(key).digest().readUInt32BE(0);
const keys = Array.from({ length: 10_000 }, (_, i) => `user:${i}`);

/* шард = хеш по модулю числа шардов */
const moved = keys.filter((key) => hash(key) % 4 !== hash(key) % 5).length;
console.log(moved); // 7975

Поэтому данные часто делят на фиксированное число слотов (англ. slots), а серверам раздают слоты. Новому серверу отдают часть слотов, и переезжают только их ключи:

const SLOTS = 1024;
const slotOf = (key: string) => hash(key) % SLOTS;

/* было четыре сервера: слот → сервер */
const before = Array.from({ length: SLOTS }, (_, slot) => slot % 4);
/* пятому серверу отдаём каждый пятый слот */
const after = before.map((server, slot) => (slot % 5 === 4 ? 4 : server));

console.log(keys.filter((key) => before[slotOf(key)] !== after[slotOf(key)]).length); // 1942

Так устроен Redis Cluster: ключи делятся на 16384 слота по формуле CRC16(key) mod 16384, и каждый ведущий узел отвечает за свою часть слотов (спецификация). MongoDB с версии 5.0 умеет менять ключ шардинга и перераспределять данные командой reshardCollection.

Шарды тоже нужно реплицировать: если у шарда нет копий, отказ одного сервера сделает недоступной его часть данных. Поэтому в MongoDB каждый шард — набор реплик.

Партиционирование

Партиционирование (англ. partitioning) — разбиение одной логической таблицы на несколько физических частей — партиций (англ. partitions) (PostgreSQL). Для запросов таблица остаётся одной, а база сама решает, в какую партицию идти. Шардинг — по сути тоже разбиение, но его части лежат на разных серверах; партиции обычно живут в одной базе.

Виды партиционирования в PostgreSQL:

  • по диапазону (англ. range), например по датам: нижняя граница входит в партицию, а верхняя — нет;
  • по списку (англ. list): для каждой партиции перечислены значения ключа;
  • по хешу (англ. hash): строка попадает в партицию по остатку от деления хеша ключа.

Что даёт партиционирование (PostgreSQL):

  • запросы ускоряются, когда нужные строки лежат в одной или нескольких партициях: планировщик пропускает остальные. Это отсечение партиций (англ. partition pruning);
  • часто используемые части индексов легче помещаются в память;
  • старые данные удаляют целой партицией: DROP TABLE или ALTER TABLE ... DETACH PARTITION намного быстрее массового DELETE и не создают работы для VACUUM;
  • редко нужные данные можно перенести на дешёвые и медленные носители.

Выгода заметна только на очень больших таблицах. По эмпирическому правилу таблица должна быть больше оперативной памяти сервера базы данных.

Жизненный пример: новостной сайт партиционирует новости по дате публикации. Свежие новости читают чаще архивных, а архив за старый год удаляется одной командой. Вывод ниже — из PostgreSQL 17.

CREATE TABLE news (
    id bigint,
    published_at date NOT NULL,
    title text
) PARTITION BY RANGE (published_at);

CREATE TABLE news_2025 PARTITION OF news FOR VALUES FROM ('2025-01-01') TO ('2026-01-01');
CREATE TABLE news_2026 PARTITION OF news FOR VALUES FROM ('2026-01-01') TO ('2027-01-01');

INSERT INTO news VALUES (1, '2025-12-31', 'Итоги года'), (2, '2026-09-28', 'Свежая новость');

SELECT tableoid::regclass AS partition, title FROM news;
--  partition |     title
-- -----------+----------------
--  news_2025 | Итоги года
--  news_2026 | Свежая новость

EXPLAIN (COSTS OFF) SELECT title FROM news WHERE published_at >= '2026-09-01';
--  Seq Scan on news_2026 news
--    Filter: (published_at >= '2026-09-01'::date)
-- партицию news_2025 планировщик даже не открывает

DROP TABLE news_2025; -- архив за 2025 год удалён целиком

Сравнение подходов

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

Критерий Репликация Шардинг Партиционирование
Что делает копирует все данные на несколько серверов делит данные между серверами по ключу делит таблицу на части внутри одной базы
Что лежит на каждом сервере полная копия своя часть данных сервер один, а части — в разных партициях
Что масштабирует чтение чтение, запись и объём данных мощности не добавляет: ускоряет запросы к части данных и обслуживание
Отказ сервера ведомый заменит ведущего переживёт, только если каждый шард реплицирован не защищает
Главная сложность отставание реплик выбор ключа, запросы во все шарды, перенос данных запросы без ключа партиционирования читают все партиции
Что меняется в приложении чтение и запись идут на разные серверы нужно знать, где лежат данные, или нужен маршрутизатор запросов почти ничего: таблица остаётся одной

Приёмы не исключают друг друга, и их часто сочетают (пример ниже).

Какой приём выбрать

Задача Приём Пример
чтений намного больше, чем записей репликация новостной сайт: статьи читают постоянно, а пишут несколько редакторов
сервис должен работать, даже если сервер базы упал репликация интернет-магазин: ведомого повышают до ведущего
тяжёлые отчёты мешают основной работе реплика для отчётов бухгалтерия строит годовой отчёт на отдельной реплике
огромная таблица с данными по времени, старое удаляют партиционирование по диапазону логи или новости по месяцам: старую партицию удаляют целиком
данные делятся по понятному признаку партиционирование по списку заказы по странам
огромная таблица без естественного признака партиционирование по хешу сессии по идентификатору
запись или объём данных не помещаются на один сервер шардинг мессенджер: сообщения шардируют по чату
всё сразу сочетание шарды по клиентам, у каждого — реплики, а внутри — партиции по месяцам

Когда нужна репликация

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

Пример: новостной сайт. Статьи читают постоянно, а пишут редакторы изредка. Запись идёт на ведущего, а чтение — по кругу на реплики:

type Query = { sql: string; readOnly: boolean };

const primaryServer = 'db-primary';
const replicaServers = ['db-replica-1', 'db-replica-2'];
let next = 0;

/* запись — только на ведущего, чтение — по кругу на реплики */
const route = ({ readOnly }: Query) => (readOnly ? replicaServers[next++ % replicaServers.length] : primaryServer);

console.log(route({ sql: "UPDATE articles SET title = 'Новый заголовок' WHERE id = 1", readOnly: false })); // db-primary
console.log(route({ sql: 'SELECT * FROM articles WHERE id = 1', readOnly: true })); // db-replica-1
console.log(route({ sql: 'SELECT * FROM articles ORDER BY id DESC LIMIT 10', readOnly: true })); // db-replica-2

Редактор, который только что сохранил статью, может не увидеть правку на реплике — это отставание реплики. Поэтому его запросы сразу после сохранения отправляют на ведущего. В PostgreSQL есть и другой путь: с настройкой synchronous_commit = remote_apply фиксация ждёт, пока синхронные ведомые не применят транзакцию, и она станет видна запросам на них (документация).

Пример: реплика для отчётов. Бухгалтерия строит отчёт за год: запрос читает все заказы и долго нагружает сервер. На отдельной реплике он не замедлит покупателей, а повышать такую реплику до ведущего не нужно (PostgreSQL).

Пример: отказ ведущего. Ночью упал ведущий интернет-магазина: ведомого повышают до ведущего, и магазин снова принимает заказы. Но при асинхронной репликации часть уже подтверждённых транзакций может не успеть дойти до ведомого и потеряется: чем больше отставание в момент отказа, тем больше потери. Важные данные можно писать синхронно: PostgreSQL позволяет задать синхронность для отдельных пользователей, подключений и даже транзакций. Пример из документации: данные клиентов — синхронно, а сообщения в чате — асинхронно, чтобы не замедлять основную нагрузку (документация).

Когда нужен шардинг

Шардинг нужен, когда один сервер не справляется с записью или не вмещает данные. Цена — ключ шардинга: он определяет, как будут работать запросы, а сменить его потом — значит перенести данные между шардами.

Пример: мессенджер. Главный запрос — открыть чат и показать последние сообщения. Ключ — идентификатор чата: все сообщения одного чата лежат на одном шарде.

const SHARDS = 4;
/* упрощённо: номер шарда — остаток от деления; на практике — слоты, как выше */
const shardOf = (chatId: number) => chatId % SHARDS;

/* все сообщения одного чата — на одном шарде */
console.log([101, 101, 101].map(shardOf)); // [ 1, 1, 1 ]
/* разные чаты расходятся по шардам */
console.log([101, 102, 103, 104].map(shardOf)); // [ 1, 2, 3, 0 ]

Открыть чат — запрос в один шард. Найти слово во всех чатах пользователя — запрос во все шарды. MongoDB называет такие запросы scatter-gather: они менее эффективны и не масштабируются линейно, когда шардов становится больше. Исключение — агрегации по большому объёму данных: там параллельная работа всех шардов даже полезна (документация). Поэтому ключ выбирают под самые частые запросы.

Пример: сервис для многих компаний. В SaaS каждая компания — отдельный клиент (англ. tenant), и её данные почти никогда не смешиваются с чужими. Ключ — идентификатор компании: запросы внутри компании идут в один шард. Но одна огромная компания может перегрузить свой шард — это проблема частоты. MongoDB советует в таком случае составной ключ с уникальным или редким значением, например (company_id, user_id).

Пример: плохие ключи. Ошибки, о которых предупреждает MongoDB:

Ключ Что не так Что будет
continent мало разных значений значений всего 7, поэтому больше семи шардов пользы не дадут (пример из документации)
country в сервисе, где почти все из одной страны одно значение встречается слишком часто шард с этой страной станет узким местом
created_at значение всё время растёт все новые записи идут в один шард; совет MongoDB — шардинг по хешу
chat_id, user_id всё в порядке много разных значений, а запросы обычно касаются одного чата или пользователя

Когда нужно партиционирование

Партиционирование помогает, когда одна таблица стала огромной, а запросы и обслуживание касаются её части: последнего месяца, одной страны. Мощности оно не добавляет — сервер тот же. Пример по диапазону — новости по годам выше, а ниже — два других вида. Вывод — из PostgreSQL 17.

Пример: заказы по странам (по списку). Заказы разных стран лежат в разных партициях, а для остальных есть партиция по умолчанию (DEFAULT). Без неё заказ из страны вне списков не вставится: PostgreSQL ответит ошибкой no partition of relation "orders" found for row.

CREATE TABLE orders (
    id bigint,
    country text NOT NULL,
    total numeric
) PARTITION BY LIST (country);

CREATE TABLE orders_eu PARTITION OF orders FOR VALUES IN ('DE', 'FR', 'PL');
CREATE TABLE orders_us PARTITION OF orders FOR VALUES IN ('US');
CREATE TABLE orders_other PARTITION OF orders DEFAULT;

INSERT INTO orders VALUES (1, 'DE', 250), (2, 'US', 100), (3, 'AM', 70);

SELECT tableoid::regclass AS partition, country FROM orders ORDER BY id;
--  partition    | country
-- --------------+---------
--  orders_eu    | DE
--  orders_us    | US
--  orders_other | AM

EXPLAIN (COSTS OFF) SELECT sum(total) FROM orders WHERE country = 'DE';
--  Aggregate
--    ->  Seq Scan on orders_eu orders
--          Filter: (country = 'DE'::text)

Отчёт по одной стране читает одну партицию, а отчёт по всем — все.

Пример: сессии (по хешу). У сессий нет удобного признака для разбиения, а таблица огромная. Хеш раскладывает строки почти поровну, а поиск по id идёт в одну партицию:

CREATE TABLE sessions (id uuid, data jsonb) PARTITION BY HASH (id);

CREATE TABLE sessions_0 PARTITION OF sessions FOR VALUES WITH (MODULUS 4, REMAINDER 0);
CREATE TABLE sessions_1 PARTITION OF sessions FOR VALUES WITH (MODULUS 4, REMAINDER 1);
CREATE TABLE sessions_2 PARTITION OF sessions FOR VALUES WITH (MODULUS 4, REMAINDER 2);
CREATE TABLE sessions_3 PARTITION OF sessions FOR VALUES WITH (MODULUS 4, REMAINDER 3);

/* 10 000 сессий с повторяемыми идентификаторами */
INSERT INTO sessions SELECT md5(i::text)::uuid, '{}' FROM generate_series(1, 10000) AS i;

SELECT tableoid::regclass AS partition, count(*) FROM sessions GROUP BY 1 ORDER BY 1;
--  partition  | count
-- ------------+-------
--  sessions_0 |  2480
--  sessions_1 |  2526
--  sessions_2 |  2497
--  sessions_3 |  2497

EXPLAIN (COSTS OFF) SELECT data FROM sessions WHERE id = 'a1d0c6e8-3f02-7327-d846-1063f4ac58a6';
--  Seq Scan on sessions_0 sessions
--    Filter: (id = 'a1d0c6e8-3f02-7327-d846-1063f4ac58a6'::uuid)

Всё вместе

Приёмы решают разные задачи, поэтому большие системы используют их вместе. Например, так может расти интернет-магазин:

  1. Один сервер. Сначала — индексы, оптимизация запросов и сервер помощнее (вертикальное масштабирование).
  2. Чтения стало много → реплики для чтения, а заодно отказоустойчивость.
  3. Таблица orders разрослась → партиции по месяцам; старые удаляют или переносят на дешёвые носители.
  4. Записи стало больше, чем выдерживает один ведущий → шардинг по customer_id. У каждого шарда — свои реплики, а внутри — те же партиции.
orders — шардинг по customer_id
├── шард 1: ведущий + 2 ведомых
│   ├── orders_2026_08   ← партиции по месяцам
│   └── orders_2026_09
└── шард 2: ведущий + 2 ведомых
    ├── orders_2026_08
    └── orders_2026_09

Шардинг делит клиентов между серверами, репликация держит копии каждого шарда для чтения и на случай отказа, а партиции ускоряют запросы за месяц и упрощают удаление старых заказов.

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

О реляционной модели данных

Реляционная модель данных основана на понятии отношения, которое пришло из теории множеств.

Коротко о главном из теории множеств

Множество

Множество - это неупорядоченный набор уникальных объектов, обладающих схожими признаками. Эти объекты называются элементами множества.

Примеры множеств: множество женских имён: N = { Ася, Сара, Рози }, множество профессий: J = { дизайнер, программист }, множество дат: D = { 2019, 2020 }.

Неупорядоченность множества означает, что множества { 2019, 2020 } и { 2020, 2019 } считаются одинаковыми.

Уникальность элементов множества означает, что множество не может содержать двух и более одинаковых элементов. То есть набор { 3, 2, 2 } - не множество.

Кортеж

Кортежем длины n называют упорядоченный набор объектов (не обязательно уникальных) (x1, x2, ..., xn), где x1, x2, ..., xn принадлежат множествам X1, X2, ... Xn (не обязательно различным).

Примеры кортежей: кортеж из элементов множеств N, J, D соответственно: (Ася, дизайнер, 2019), координаты точки на плоскости: (1, 1), набор аргументов функции f(x1, x2, x3).

Упорядоченность кортежа означает, что кортежи (Рози, 2020) и (2020, Рози) считаются различными. Соблюдение порядка элементов кортежа так же важно, как соблюдение порядка букв в словах и цифр в числах.

Кортеж длины 2 также называют упорядоченной парой, кортеж длины 3 - упорядоченной тройкой.

Декартово произведение множеств

Декартово произведение множеств X1, X2, ..., Xn - это операция над множествами X1, X2, ..., Xn (не обязательно различными), результатом которой является множество всевозможных кортежей (x1, x2, ..., xn), где элементы x1, x2, ..., xn принадлежат множествам X1, X2, ..., Xn соответственно. Обозначение: X1 × X2 × ... × Xn.

Например, декартово произведение N × D = { (Ася, 2019), (Ася, 2020), (Сара, 2019), (Сара, 2020), (Рози, 2019), (Рози, 2020) }, а декартово произведение N × J × D состоит из 3 • 2 • 2 = 12 кортежей по типу (Ася, дизайнер, 2019).

Отношение в теории множеств

n-арным отношением R между множествами X1, X2, ..., Xn называют подмножество декартового произведения X1 × X2 × ... × Xn, то есть множество, содержащее некоторые элементы (кортежи) множества X1 × X2 × ... × Xn. Число n - арность отношения.

Например, множество { (Сара, 2019), (Рози, 2020) } является бинарным отношением между множествами N и D.

Отношения могут обладать некоторыми свойствами и наделять ими свои элементы.

Примеры известных отношений: меньше (x < y), больше (x > y), равно (x = y), перпендикулярность, параллельность (x || y), x - отец y и так далее.

Операция в теории множеств

Пусть имеются множества X и Y, причём множество X является подмножеством декартова произведения n непустых множеств: X = X1 × X2 × … × Xn. Тогда n-арной операцией называется бинарное отношение f ⊆ X × Y, такое, что каждому значению x ∈ X соответствует единственное значение y ∈ Y. Здесь элемент x представляет собой кортеж (x1, x2, …, xn).

Элементы x1, x2, …, xn называют операндами, а элемент y - результатом операции f.

Общее обозначение n-арной операции f: f(x1, x2, ..., xn) = y.

Операция с одним операндом называется унарной операцией, с двумя - бинарной.

Операции обычно имеют своё уникальное символьное обозначение.

Самыми широко используемыми операциями являются арифметические операции. Например, бинарная операция “сложение” (x1 + x2 = y), бинарная операция “возведение в степень” (x1 ^ x2 = y), унарная операция “факториал” (x! = y) и так далее.

Тип данных (домен)

Тип данных - это множество допустимых значений. Любое значение (переменной, константы, параметра, атрибута и так далее) принадлежит какому-то типу данных.

В реляционной модели данных тип данных также называют доменом.

Вообще говоря, основными типами данных в программировании являются числовой (7, 3.14), строковый ("развитие", 'engineer') и логический (истина, ложь).

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

Если мы указываем, что значение принадлежит какому-то типу, то другому типу оно уже принадлежать не может.

Типы, предопределённые в системе, называют базовыми типами. Многие системы позволяют пользователю на основе базовых типов создавать новые типы, называемые в таком случае пользовательскими типами.

В реляционной модели данных обязательным базовым типом является лишь логический (boolean): без него невозможно рассматривать операции над отношениями.

Отношение и его структура

Об отношении и его структуре

Понятие отношения в реляционной модели данных довольно близко по смыслу к понятию отношения в теории множеств. При этом множествами X1, X2, ..., Xn выступают типы данных T1, T2, ..., Tn, являющиеся множествами по определению.

Ниже рассмотрим несколько видоизменённое математическое определение.

Пусть имеются типы данных T1, T2, ..., Tn (не обязательно различные), тогда n-арным отношением (англ. relation) R называют подмножество декартового произведения T1 × T2 × ... × Tn. Говоря другими словами, отношение - это некоторое множество (набор) кортежей, имеющих одинаковую схему, то есть кортежей (t1, t2, ..., tn), элементы t1, t2, ..., tn которых принадлежат типам данных T1, T2, ..., Tn соответственно.

На деле же отношение реляционной модели данных имеет особую структуру и не является множеством как таковым. Отношение R состоит из заголовка H и тела B. Фактически, его можно рассматривать как упорядоченную пару заголовка и тела: R = (H, B).

Атрибуты и их значения

Атрибут (лат. attributio - признак) в философии - отличительный, существенный, неотъемлемый признак (черта, свойство) предмета или явления. Атрибуты независимы друг от друга, то есть один атрибут не может повлиять на другой.

В программировании атрибут (англ. attribute) представляет собой свойство некоторого объекта, элемента или файла.

Объект характеризуется и определяется значениями своих атрибутов.

Атрибут объекта обычно состоит из имени атрибута (name) и значения атрибута (value).

Например, “цвет глаз” можно назвать атрибутом человека, тогда “карий”, “зелёный”, “голубой” и “серый” - некоторые из возможных значений атрибута.

В реляционной модели данных некоторый класс объектов представляется отношением и характеризуется конечным множеством атрибутов, а информация (данные) о конкретном объекте хранится в виде набора значений атрибутов. В этом и кроется главное различие между отношением (из реляционной модели данных) и множеством (из теории множеств): множество обычно представляет собой набор наименований объектов, в то время как отношение представляет множество характеристик объектов.

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

Фактически, атрибут в реляционной модели данных можно рассматривать как упорядоченную пару (a, t), где a - название атрибута, t - название типа данных, которому принадлежат значения атрибута. В таком случае значение атрибута можно рассматривать как упорядоченную тройку (a, t, v), где v - значение атрибута a типа t.

Заголовок отношения

Говоря простыми словами, заголовок отношения состоит из атрибутов.

Заголовком (схемой) H (англ. header) отношения R называют множество упорядоченных пар (a, t), где a (англ. attribute) - название атрибута, t (англ. type) - название типа данных (не сам тип данных, являющийся множеством), которому принадлежат значения атрибута a.

Таким образом, заголовок n-арного отношения имеет вид: H = { (a1, t1), (a2, t2), ..., (an, tn) }.

Пример заголовка для отношения между множествами N, J, D: H = { (Имя, string), (Профессия, string), (Дата, date) }.

Число атрибутов n называется степенью отношения или арностью отношения.

Отношение с одним атрибутом называют унарным, с двумя — бинарным, с тремя - тернарным и так далее.

Поскольку множество не может содержать одинаковые элементы, а типы данных в заголовке могут повторяться, названия атрибутов должны быть уникальными. Иначе возможна была бы ситуация H = { (Дата, date), (Дата, date) }, что недопустимо для множеств.

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

Тело отношения

Говоря простыми словами, тело отношения - это множество кортежей, содержащих значения атрибутов.

Итак, заголовок представляет собой множество атрибутов (a, t): H = { (a1, t1), (a2, t2), ..., (an, tn) }.

Значение атрибута должно быть привязано к самому атрибуту, поэтому оно представляется упорядоченной парой ((a, t), v) или, что то же самое, упорядоченной тройкой (a, t, v), где v (англ. value) - значение атрибута a типа t. Но, поскольку название атрибута уникально, а тип данных привязан к нему парой в заголовке отношения, значение атрибута можно представить ещё проще - упорядоченной двойкой (a, v).

Пусть имеется n атрибутов a1, a2, ..., an. Тогда тело B (англ. body) отношения R - это множество кортежей k = ((a1, v1), (a2, v2), ..., (an, vn)): B = { k1, k2, ..., km }.

Количество упорядоченных пар (a, v) в кортеже k должно совпадать с количеством атрибутов (степенью отношения) n.

Число m (число кортежей k) называется кардинальным числом отношения или кардинальностью отношения.

Стоит отметить, что, несмотря на математическое определение кортежа и начальное определение автора, кортеж k не обязательно должен быть упорядочен. Действительно, значения напрямую привязаны к своим атрибутам упорядоченными парами и в случае перестановки ((a2, v2), (a1, v1)) эта связь не нарушается. Более того, сами атрибуты в заголовке не упорядочены по определению множества, а значит упорядоченность значений избыточна. Упорядоченность имела бы смысл, если бы кортежи k имели вид: (v1, v2, ..., vn). Далее при необходимости в упорядоченности, чтобы не путать упорядоченные математические кортежи и неупорядоченные кортежи k, будем использовать понятия “упорядоченный набор”, “упорядоченная пара” и “упорядоченная тройка”.

Пусть имеется заголовок H вида:

H = { (Имя, string), (Профессия, string), (Дата, date) }

Ниже представлен пример тела B, соответствующего заголовку H:

B = {
  ((Имя, Сара), (Профессия, программист), (Дата, 2019)),
  ((Имя, Рози), (Профессия, дизайнер), (Дата, 2019)),
}

Графически, упорядоченная пара (a, v) - одна ячейка таблицы, а кортеж k - строка таблицы.

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

Свойства отношения опираются на его структуру.

Поскольку заголовок H и тело B отношения R являются множествами, их свойства вытекают из свойств множеств:

  1. Тело отношения B не может содержать двух и более одинаковых кортежей.
  2. Порядок следования атрибутов в заголовке H отношения не имеет значения.
  3. Порядок следования кортежей в теле B отношения не имеет значения.

Графическое представление отношения (таблица)

Понятие таблицы

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

Отношение R из последнего примера выше можно представить таблицей следующего вида:

Отношение R

Имя Профессия Дата
Ася дизайнер 2019
Сара программист 2020

Сравнение понятий отношения и таблицы

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

Например, понятие таблицы не подразумевает уникальности строк, в то время как в отношении требуется уникальность кортежей.

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

  1. Все свойства отношений должны быть верны для строк и столбцов таблицы.
  2. Таблица не должна содержать дополнительных возможностей, выходящих за рамки понятия отношения. (например, скрытые поля с порядком строк и скрытые методы их сортировки, встроенные в строки даты и так далее).

Ключи

Об идентификации

Идентификатор, ID (англ. identifier — опознаватель) — это уникальный признак объекта.

Идентификаторы позволяют идентифицировать объект, то есть выделить (найти) его среди других объектов.

Например, можно по номеру паспорта определить (идентифицировать) человека, по IP-адресу - физический компьютер, по координатам - точку на карте, по штрих-коду - товар в магазине, по QR-коду - ссылку, по ссылке - сайт и так далее.

Для идентификации кортежей отношения используются ключи.

Потенциальный ключ

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

Пусть имеется отношение R, содержащее в заголовке n атрибутов.

Потенциальным ключом (англ. candidate key) называют подмножество из m <= n атрибутов отношения R, которое удовлетворяет условиям уникальности и минимальности.

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

Важно отметить, что R именно “не может содержать двух кортежей”, а не “не содержит двух кортежей”. Например, если в компании работает несколько сотрудников и все имеют различный цвет глаз, это не означает, что цвет глаз является уникальным идентификатором: всегда может появиться новый сотрудник с уже существующим цветом глаз и идентификация станет невозможной.

Таким образом, уникальность опирается не на наличие объекта в текущий момент времени, а на особенности (природу) класса объектов, которые допускают возможность появления нового объекта в любой момент времени. Неплохими идентификаторами сотрудника компании могут стать: серия и номер паспорта, номер трудовой книги, рабочий email или номер телефона (все они не могут повториться у двух сотрудников).

Условие минимальности (несократимости) требует, чтобы среди атрибутов потенциального ключа отсутствовало меньшее подмножество из k <= m атрибутов, которое удовлетворяет условию уникальности.

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

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

В отношении может одновременно существовать несколько потенциальных ключей.

На примере ниже представлено отношение с двумя потенциальными ключами, каждый из которых состоит из одного элемента: { Номер телефона } и { Email }.

Отношение R (пользователи)

Имя Фамилия Номер телефона Email
Джон Дрим 8768 johndream@example
Фрэнк Старк 1442 frankstark@example
Ален Стоун 3567 alenstone@example

Первичный ключ

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

Если в отношении содержится только один потенциальный ключ, то он и является первичным ключом данного отношения.

Если в отношении содержится несколько потенциальных ключей, то имеется два основных критерия выбора первичного ключа:

  1. Удобство использования. Чаще всего выбирается потенциальный ключ с наименьшим физическим размером (занимает меньше памяти на компьютере) или содержит наименьшее количество атрибутов.
  2. Сохранение уникальности с течением времени. Некоторые идентификаторы могут утрачивать свою уникальность со временем.

Простые и составные ключи

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

Чаще всего используются простые ключи (id, number, username, email, phone), поскольку их проще хранить, с ними проще работать.

Редко, но бывают случаи, когда удобнее использовать составной ключ или нет возможности использовать простой ключ.

Рассмотрим пример составного ключа, разбив телефонный номер на группы. В системе, работающей с телефонными номерами, разбиение номера могло бы оптимизировать поиск и фильтрацию. Из чего состоит телефонный номер? Его схема различна в разных странах. Например, американский номер состоит из кода страны, кода региона, кода телефонного узла и абонентского номера: +1 (234) 235 1779.

Отношение R

Код региона Код узла Абонентский номер Фамилия владельца
234 145 1984 Ирвинг
234 310 7817 Купер
235 420 6168 Редли

Тогда первичный ключ PK отношения R имеет вид:

{
  (Код региона, integer),
  (Код узла, integer),
  (Абонентский номер, integer)
}

Исключение любых атрибутов из ключа PK приведёт к утрате уникальности этого ключа.

Другие примеры составных ключей: серия и номер паспорта (не уникальны по-отдельности), масть и число на игровой карте, номер ряда и номер места в кинотеатре, составные части URL, составные части адреса электронной почты и так далее.

Значение ключа

Значением ключа называют кортеж, состоящий из значений атрибутов этого ключа.

Отношение R (места в кинозале)

Номер ряда Номер места Место для влюблённых VIP
7 18 true false
7 19 true false
3 22 false false
10 3 false true

Тогда первичный ключ PK отношения R имеет вид:

{
  (Номер ряда, integer),
  (Номер места, integer)
}

Кортеж ((Номер ряда, 7), (Номер места, 18)) - одно из доступных значений ключа PK.

Естественный ключ

Разделим понятия реального объекта (дом, машина, человек, дерево) и его физического представления в некоторой базе данных (например, набор значений атрибутов).

Естественный ключ (англ. natural key, business key, domain key) - это уникальный ключ, который идентифицирует некоторый реальный объект, при этом полностью зависит от свойств (природы) этого объекта и не зависит от его физического представления (реализации) в конкретной базе данных.

Естественный ключ подбирается на основе реальных наблюдений за объектом, поэтому его уникальность опирается исключительно на уникальные черты реального объекта.

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

Как и в случае с потенциальными ключами, естественных ключей у отношения может быть несколько.

Примеры естественных ключей всё те же, что и примеры потенциальных ключей: человека можно идентифицировать по серии и номеру паспорта, пользователя - по email, дом - по адресу и так далее. Всё это - естественные ключи, взятые из предметных областей (доменов) соответствующих объектов.

Естественные ключи являются полноценной частью приложения и не скрываются от глаз пользователя (например, на сайтах можно часто видеть email или номер телефона).

Суррогатный ключ

Суррогатный ключ (англ. surrogate key, pseudokey, synthetic key) - это уникальный идентификатор как для реального объекта, так и для его физического представления в базе данных.

В отличие от естественного ключа, суррогатный ключ никак не зависит от свойств реального объекта, а следовательно и от атрибутов. Суррогатный ключ генерируется системой по заданному алгоритму, поэтому не имеет смысла вне системы.

Чаще всего суррогатный ключ представляет собой некоторый хэш (произвольно сгенерированная строка) или целое число.

Самые распространённые способы генерации суррогатного ключа:

  1. Universally Unique Identifier (UUID). Пример: 9fc2e9ad-fae7-4f25-ae48-3f45284f2299.
  2. Globally Unique Identifier (GUID). Пример: 75f067fa-b95f-405c-a1bd-29164461a65f.
  3. Object Identifier (ObjectID). Пример: ObjectId("507f1f77bcf86cd899439017").
  4. AUTO_INCREMENT (MySQL), AUTOINCREMENT (SQLite), SEQUENCE (SQL Server, Oracle).

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

У отношения может быть несколько суррогатных ключей.

Преимущества использования суррогатных ключей:

  1. Неизменность (стабильность). Благодаря независимости суррогатного ключа от атрибутов объекта, ключ остаётся неизменным при изменении этого объекта.
  2. Компактность. Суррогатный ключ всегда состоит только из одного значения, размер которого фиксирован и обычно невелик (размер ключа зависит от алгоритма генерации, который можно выбирать), что уменьшает расход памяти и увеличивает скорость поиска объектов по ключу.
  3. Единообразие. Если все ключи в системе создаются по одному алгоритму (например, везде используется UUID), то логика обработки данных упрощается и становится предсказуемой для разработчика в любом месте системы.
  4. Уникальность ключа во всей системе - не только в отдельном отношении.

Основным недостатком суррогатного ключа является то, что он не связан с самим объектом по смыслу: по такому ключу нельзя судить как о содержимом объекта, так и о классе, которому этот объект принадлежит.

Внешний ключ

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

Использование внешних ключей лишает нас необходимости в дублировании данных. На эти данные можно просто сослаться из другого места. Такой подход

Пусть имеются отношения R и S (не обязательно различные). Внешним ключом (англ. foreign key) FK называют такое подмножество атрибутов отношения S, для которого выполняются условия:

  1. Отношение R имеет такой потенциальный ключ CK, что у ключей CK и FK совпадают количество атрибутов и их типы данных (при переименовании атрибутов ключи совпадают).
  2. Каждое значение внешнего ключа FK в некотором кортеже отношения S совпадает со значением потенциального ключа CK в некотором кортеже отношения R. Иначе говоря, множество значений ключа FK содержится (является подмножеством) в множестве значений ключа CK.

Обозначение внешнего ключа FK, ссылающегося на потенциальный ключ CK: FK → CK.

Отношение R, содержащее потенциальный ключ CK, называют главным (родительским) отношением, отношение S, содержащее внешний ключ FK, называют подчинённым (дочерним) отношением.

Ниже представлен пример простенькой реализации чата. Родительское отношение R имеет потенциальный ключ ID, дочернее отношение S имеет два внешних ключа: SENDER_ID → ID (идентификатор отправителя) и RECIPIENT_ID → ID (идентификатор получателя).

Отношение R (пользователи)

ID Имя пользователя
cde Сара
fkh Рози

Отношение S (сообщения)

ID Текст SENDER_ID RECIPIENT_ID
erksh Доброй ночи cde fkh
jhtbe И тебе fkh cde

Связи между отношениями

О связях между отношениями

Связи между отношениями похожи по смыслу на бинарные отношения из теории множеств. Связи передают то, как объекты соотносятся (связаны) друг с другом. В терминах реляционной модели данных: связь устанавливает соотношение (соответствие) между кортежами двух отношений, причём не обязательно различных.

Связи между двумя отношениями устанавливаются при помощи внешних ключей.

Как уже ранее отмечалось, отношение, содержащее внешний ключ FK → CK, называют дочерним, а отношение, содержащее потенциальный ключ CK, называют родительским.

Между родительским и дочерним отношениями существует 4 вида связей:

Один к одному (1:1)

Один к одному 1:1 (англ. one-to-one) - такая связь между отношениями R и S, при которой каждому кортежу отношения R соответствует только один (или ни одного) кортеж отношения S и каждому кортежу отношения S соответствует только один (или ни одного) кортеж отношения R. Другими словами, отношение R имеет потенциальный ключ R.CK и внешний ключ R.FK → S.CK, а отношение S имеет потенциальный ключ S.CK и внешний ключ S.FK → R.CK.

Пример связи 1:1: одно королевство - один король (королева).

Отношение R, представленное таблицей ниже, содержит потенциальный ключ R.ID и внешний ключ R.KINGDOM_ID → S.ID, отношение S содержит потенциальный ключ S.ID и внешний ключ S.KING_ID → R.ID.

Отношение R (современные короли и королевы)

ID Имя KINGDOM_ID
val Виллем-Александр NL
el2 Елизавета II GB
k16 Карл XVI Густав SE
ma2 Маргрета II DK
fil Филипп BE
fi6 Филипп VI ES
ha5 Харальд V NO

Отношение S (страны)

ID Название KING_ID
BE Бельгия fil
GB Великобритания el2
DK Дания ma2
ES Испания fi6
NL Нидерланды val
NO Норвегия ha5
SE Швеция k16

Один ко многим (1:M)

Один ко многим 1:M (англ. one-to-many) - такая связь между отношениями R и S, при которой каждому кортежу отношения R соответствует несколько (или ни одного) кортежей отношения S и каждому кортежу отношения S соответствует не более одного кортежа отношения R. Другими словами, отношение R имеет потенциальный ключ R.CK, а отношение S имеет внешний ключ S.FK → R.CK.

Рассмотрим интересный пример связи 1:M: один отец может иметь нескольких детей, но каждый ребёнок имеет лишь одного биологического отца.

Как уже ранее отмечалось, отношения R и S не обязательно различны (они могут представлять собой одно и то же отношение). Отношение R, представленное таблицей ниже, содержит потенциальный ключ R.ID и внешний ключ R.PARENT_ID → R.ID.

Отношение R (отцы и дети)

ID Имя Возраст PARENT_ID
P1 Джон 65 NULL
P2 Джим 43 P1
P3 Джек 20 P2
P4 Джоан 22 P2

Многие к одному (M:1)

Многие к одному M:1 (англ. many-to-one) - зеркальное отражение связи 1:M (в определении достаточно поменять местами отношения R и S).

Пример связи M:1: много городов может принадлежать одной стране, но один город не может принадлежать двум странам одновременно.

Отношение R, представленное таблицей ниже, имеет потенциальный ключ R.ID и внешний ключ R.COUNTRY_ID → S.ID, а отношение S содержит только потенциальный ключ S.ID.

Отношение R (города)

ID Имя COUNTRY_ID
kiev Киев UA
lviv Львов UA
sydney Сидней AU

Отношение S (страны)

ID Название
UA Украина
AU Австралия

Многие ко многим (M:M)

Многие ко многим M:M (англ. many-to-many) - такая связь между отношениями R и S, при которой каждому кортежу отношения R соответствует несколько (или ни одного) кортежей отношения S и каждому кортежу отношения S соответствует несколько (или ни одного) кортежей отношения R. С помощью двух отношений такую связь на практике реализовать нельзя.

Другими словами, отношение R имеет потенциальный ключ R.CK, отношение S имеет потенциальный ключ S.CK и существует такое отношение T, тело которого состоит из кортежей (T.FK1 → S.CK, T.FK2 → R.CK), содержащих внешние ключи, ссылающиеся на потенциальные ключи отношений R и S. Отношение T имеет связь M:1 (многие к одному) с каждым из отношений R и S.

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

Отношение R (разговорные языки)

ID Язык
en Английский
ru Русский
fr Французский

Отношение S (сотрудники)

ID Имя Должность
sara1 Сара программист
dina7 Дина дизайнер

Пусть Сара знает английский и французский, а Дина - английский и русский, тогда:

Отношение T (соответствие между языками и сотрудниками)

ID WORKER_ID LANGUAGE_ID
t1 sara1 en
t2 sara1 fr
t3 dina7 en
t4 dina7 ru

В таблице выше можно увидеть, что отношение T имеет внешний ключ T.LANGUAGE_ID → R.ID (связь M:1 между T и R) и внешний ключ T.WORKER_ID → S.ID (связь M:1 между T и S).

Ещё один пример связи M:M: у научной статьи может быть несколько авторов, у автора может быть много научных статей.

Ссылочная целостность

Первичные ключи могут изменяться. Простой пример: пользователь хочет сменить email или номер телефона. Если существует связь, использующая подобный потенциальный ключ CK, то ссылающийся на него внешний ключ FK → CK также должен измениться.

Ссылочной целостностью (англ. referential integrity) называют корректность значений всех внешних ключей, то есть хранение актуального значения потенциального ключа CK в каждом внешнем ключе FK → CK.

Чтобы обеспечить ссылочную целостность, необходимо при изменении значения потенциального ключа CK заменить значения всех ссылающихся на него внешних ключей FK или отменить операцию изменения, если замена невозможна.

В некоторых системах управления базами данных ссылочная целостность поддерживается автоматически.

Операции над отношениями (реляционные операции)

О реляционных операциях

Большинство операций над отношениями являются бинарными, то есть такими, которые оперируют двумя отношениями. При необходимости произвести бинарную операцию над большим количеством отношений, её необходимо применить последовательно несколько раз: P • R • S • T = ((P • R) • S) • T.

Любая операция над отношениями, результатом которой является отношение, называется реляционной операцией.

Систему реляционных операций называют реляционной алгеброй.

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

Эдгар Кодд, создатель реляционной модели данных, ввёл следующий набор из 8 реляционных операций:

Операции объединения, пересечения, вычитания и декартова произведения относят к теоретико-множественным операциям: они являются аналогами одноимённых операций над множествами в теории множеств.

Операции проекции, выборки, соединения и деления называют специальными операциями: они имеют смысл только в рамках реляционной модели данных.

Операции объединения, вычитания, проекции, декартова произведения и выборки являются примитивными реляционными операциями — такими операциями, которые нельзя выразить друг через друга.

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

Ограничения на применение операций

Операции объединения, пересечения и вычитания требуют совпадения заголовков у своих отношений-операндов.

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

Объединение отношений

Объединение отношений R и S - бинарная операция, требующая совпадения заголовков отношений R и S, результатом которой является отношение с тем же заголовком и телом, содержащим все кортежи обоих отношений. Иначе говоря, каждый кортеж отношения-результата принадлежит или отношению R, или отношению S. Если отношения R и S имеют между собой совпадающие кортежи (пересечения), то в отношение-результат попадает только один из них.

Обозначение объединения отношений R и S: R UNION S.

Объединение отношений является аналогом объединения множеств из теории множеств.

Ниже представлен пример объединения отношений R и S.

Отношение R

Имя Профессия Дата
Ася дизайнер 2019
Сара программист 2020

Отношение S

Имя Профессия Дата
Рози дизайнер 2020
Сара программист 2020

Отношение R UNION S

Имя Профессия Дата
Ася дизайнер 2019
Сара программист 2020
Рози дизайнер 2020

Пересечение отношений

Пересечение отношений R и S - бинарная операция, требующая совпадения заголовков отношений R и S, результатом которой является отношение с тем же заголовком и телом, содержащим только те кортежи, которые содержатся в обоих отношениях. Иначе говоря, каждый кортеж отношения-результата содержится и в отношении R, и в отношении S.

Обозначение пересечения отношений R и S: R INTERSECT S.

Пересечение отношений является аналогом пересечения множеств из теории множеств.

Операция пересечения отношений не является примитивной, поскольку её можно выразить через операцию вычитания отношения: R INTERSECT S = R MINUS (R MINUS S).

Ниже представлен пример пересечения отношений R и S.

Отношение R

Имя Профессия Дата
Ася дизайнер 2019
Сара программист 2020

Отношение S

Имя Профессия Дата
Рози дизайнер 2020
Сара программист 2020

Отношение R INTERSECT S

Имя Профессия Дата
Сара программист 2020

Вычитание отношения

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

Обозначение вычитания отношения S из R: R MINUS S.

Вычитание отношения является аналогом разности множеств из теории множеств.

Ниже представлен пример вычитания отношения S из R.

Отношение R

Имя Профессия Дата
Ася дизайнер 2019
Сара программист 2020

Отношение S

Имя Профессия Дата
Рози дизайнер 2020
Сара программист 2020

Отношение R MINUS S

Имя Профессия Дата
Ася дизайнер 2019

Декартово произведение отношений

Пусть имеются отношение R с атрибутами a1, a2, ..., an и значениями атрибутов x1, x2, ..., xn в кортежах и отношение S с атрибутами b1, b2, ..., bm и значениями атрибутов y1, y2, ..., ym в кортежах.

Декартово произведение отношений R и S - это бинарная операция, требующая отсутствия совпадающих названий атрибутов между заголовками отношений R и S (между { a1, a2, ..., an } и { b1, b2, ..., bm }), результатом которой является новое отношение T, заголовок которого получается в результате конкатенации (соединения, сцепления) заголовков отношений R и S, а тело состоит из упорядоченных пар ((x1, x2, ..., xn), (y1, y2, ..., ym)), содержащих всевозможные комбинации кортежей отношений R и S соответственно. Для упрощения можно раскрыть скобки внутри упорядоченной пары (порядок элементов сохранится): (x1, x2, ..., xn, y1, y2, ..., ym).

Обозначение декартова произведения R и S: R TIMES S.

Декартово произведение отношений является аналогом декартова произведения множеств из теории множеств.

Ниже представлен пример декартова произведения отношений R и S.

Отношение R(Имя, Фамилия)

Имя Фамилия
Ася Тургенева
Рози Фицджеральд
Сара Фаулз

Отношение S(Профессия, Дата)

Профессия Дата
дизайнер 2019
программист 2020

Количество атрибутов в отношении R TIMES S: n(R) + n(S) = 2 + 2 = 4, количество кортежей: m(R) • m(S) = 3 • 2 = 6.

Отношение R TIMES S = T(Имя, Фамилия, Профессия, Дата)

Имя Фамилия Профессия Дата
Ася Тургенева дизайнер 2019
Ася Тургенева программист 2020
Рози Фицджеральд дизайнер 2019
Рози Фицджеральд программист 2020
Сара Фаулз дизайнер 2019
Сара Фаулз программист 2020

Проекция отношения

Проекция отношения R - унарная операция над отношением R, которая позволяет составить новое отношение из выбранных атрибутов отношения R и их значений в кортежах отношения R.

Графически проекция отношения R - это выборка столбцов таблицы.

Если при проецировании возникают кортежи-дубликаты, то они удаляются из результата.

Если отношение R имеет n атрибутов, то его можно обозначить: R(a1, a2, ..., an). Тогда проекция, включающая в себя первый и третий атрибуты отношения R обозначается: PROJECT R { a1, a3 } или R[a1, a3].

Ниже представлен пример проекции отношения R.

Отношение R(Имя, Профессия, Дата)

Имя Профессия Дата
Ася дизайнер 2019
Рози дизайнер 2019
Сара программист 2020
Рози дизайнер 2020

Отношение R[Имя, Профессия]

Имя Профессия
Ася дизайнер
Рози дизайнер
Сара программист
Рози дизайнер

Перечёркнутая строка является дубликатом второй строки, поэтому она не попадает в результат.

Выборка (ограничение)

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

Условие c задаётся логическим выражением (его результатом являются истина или ложь), которое может содержать названия атрибутов и константы (числа, строки, даты и так далее). Если результат выполнения выражения c - истина, то кортеж попадает в результат выборки, иначе - не попадает.

Обозначение выборки из отношения R: R WHERE c.

Ниже представлен пример выборки из отношения R.

Отношение R

Имя Профессия Дата
Ася дизайнер 2019
Сара программист 2020
Рози дизайнер 2020

Отношение R WHERE (Профессия = дизайнер)

Имя Профессия Дата
Ася дизайнер 2019
Рози дизайнер 2020

Отношение R WHERE (Дата > 2019)

Имя Профессия Дата
Сара программист 2020
Рози дизайнер 2020

Отношение R WHERE (Имя != Рози)

Имя Профессия Дата
Ася дизайнер 2019
Сара программист 2020

Соединение

Соединение отношений R и S - бинарная операция, результатом которой является результат последовательного применения операций декартового произведения R TIMES S и выборки из получившегося отношения с условием c.

Как и в случае с декартовым произведением, в заголовках отношений R и S не должно быть совпадающих атрибутов. Если такие имеются, то их необходимо переименовать перед тем, как производить операцию соединения.

Обозначение соединения отношений R и S: (R TIMES S) WHERE c.

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

Отношение R

Имя Фамилия
Ася Тургенева
Рози Фицджеральд
Сара Фаулз

Отношение S

Профессия Дата
дизайнер 2019
программист 2020

Отношение R TIMES S

Имя Фамилия Профессия Дата
Ася Тургенева дизайнер 2019
Ася Тургенева программист 2020
Рози Фицджеральд дизайнер 2019
Рози Фицджеральд программист 2020
Сара Фаулз дизайнер 2019
Сара Фаулз программист 2020

Отношение (R TIMES S) WHERE (Дата = 2019)

Имя Фамилия Профессия Дата
Ася Тургенева дизайнер 2019
Рози Фицджеральд дизайнер 2019
Сара Фаулз дизайнер 2019

Деление отношений

Пусть имеются отношение R с заголовком { a1, a2, ..., an, b1, b2, ... bm } и телом, содержащим множество кортежей вида (x1, x2, ... xn, y1, y2, ... ym), и отношение S с заголовком { b1, b2, ... bm } и телом, содержащим множество кортежей вида (y1, y2, ... ym).

Делением отношения R на отношение S называют бинарную операцию над отношениями R и S, результатом которой является отношение T с заголовком { a1, a2, …, an } и телом, содержащим множество таких кортежей (x1, x2, …, xn), что для каждого кортежа (y1, y2, …, ym) отношения S в R существует кортеж (x1, x2, …, xn, y1, y2, …, ym). В этом случае отношение R называют делимым, отношение S - делителем, отношение T - частным.

Другими словами, в результат деления отношения R на отношение S попадают такие кортежи x = (x1, x2, ... xn) делимого R, c которыми каждый кортеж y = (y1, y2, …, ym) делителя S (то есть все кортежи отношения S без исключения) состоит в упорядоченной паре (x, y), или, что то же самое, в кортеже (x1, x2, ..., xn, y1, y2, ..., ym), принадлежащем отношению R.

Обозначение деления отношения R на S: R DIVIDEBY S.

Чем деление отношений похоже на деление чисел? При делении чисел x ÷ y мы считаем, сколько раз делитель y целиком поместится в делимое x. Пример: 7 ÷ 3 = 3 + 3 + 1 = 2 полных раза. При делении отношений в результат попадает каждый кортеж x, который связан упорядоченными парами со всеми без исключения кортежами y, заданными в отношении-делителе.

Деление отношений проще понять на примере. Ниже представлен пример деления отношения R на отношение S.

Отношение R

Имя Работа Разговорный язык
Ася дизайнер русский
Ася дизайнер немецкий
Сара программист английский
Сара программист французский
Дина программист русский
Дина программист итальянский
Дина программист английский
Рози дизайнер русский
Рози дизайнер английский

Отношение S

Разговорный язык
русский
английский

Кто из сотрудников компании в отношении R знает все перечисленные в отношении S языки?

Отношение R DIVIDEBY S

Имя Работа
Сара программист
Рози дизайнер

Сара и Рози знают все перечисленные языки.

Кортежи x = (x1, x2) = (Сара, программист) и x = (x1, x2) = (Рози, дизайнер) попали в результат, поскольку они состоят в упорядоченных парах с каждым из кортежей y = (y1) = (русский), y = (y1) = (английский) отношения S.

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

Переименование атрибутов отношения

Переименование атрибутов отношения R - унарная операция над отношением R, результатом которой является отношение с телом отношения R и изменёнными названиями указанных атрибутов в заголовке.

Результатом применения операции переименования атрибутов является отношение с изменёнными именами атрибутов.

Обозначение переименования атрибутов { a1, a2, ..., am } отношения R на новые имена { b1, b2, ..., bm }: R RENAME a1, a2, …, am AS b1, b2, …, bm.

Отношение R

Имя Профессия Дата
Ася дизайнер 2019
Сара программист 2020
Рози дизайнер 2020

Отношение R RENAME Профессия, Дата AS Специальность, Год

Имя Специальность Год
Ася дизайнер 2019
Сара программист 2020
Рози дизайнер 2020

Разновидности операций соединения

В зависимости от вида условия c различают несколько разновидностей соединений.

Тэта-соединение

Пусть a - один из атрибутов отношения R, b - один из атрибутов отношения S.

Тэта-соединением (Θ-соединением) отношения R по атрибуту a с отношением S по атрибуту b называют соединение отношений R и S с условием c вида a Θ b, где символ Θ является одним из следующих символов сравнения { <, >, ≤ (<=), ≥ (>=), =, ≠ (!=) }.

Обозначение Θ-соединения отношения R по атрибуту a с отношением S по атрибуту b: (R TIMES S) WHERE a Θ b, или более кратко R(a Θ b)S.

Рассмотрим Θ-соединение на примере продажи и покупки некоторого предмета, имеющего в качестве характеристик цвет и качество материала. Пусть имеются отношение R, содержащее запросы на покупку предмета, и отношение S, содержащее выставленные на продажу предметы.

Отношение R (запросы на покупку предмета)

Покупатель Желаемая цена
magic 240
woodruf 180

Отношение S (выставленные на продажу предметы)

Продавец Предлагаемая цена Качество материала Цвет
evergreen 230 0.7 зелёный
funnyrabbit 180 0.5 бирюзовый
redhot 300 1.0 красный

Найдём все соответствия между запросами на покупку предметов и выставленными на продажу предметами при условии, что желаемая цена покупателя выше (или равна) установленной цены продавца.

Отношение (R TIMES S) WHERE Желаемая цена >= Предлагаемая цена

Покупатель Желаемая цена Продавец Предлагаемая цена Качество материала Цвет
magic 240 evergreen 230 0.7 зелёный
magic 240 funnyrabbit 180 0.5 бирюзовый
woodruf 180 funnyrabbit 180 0.5 бирюзовый

Итак, пользователь magic по своему запросу может купить предмет у пользователя evergreen или у funnyrabbit, а пользователь woodruf - только у funnyrabbit. Пользователь redhot остался без потенциальных покупателей, поскольку установил слишком высокую цену.

Экви-соединение

Экви-соединением отношения R по атрибуту a с отношением S по атрибуту b называют тэта-соединение, при котором символ Θ является символом равенства =.

Обозначение экви-соединения отношения R по атрибуту a с отношением S по атрибуту b: (R TIMES S) WHERE a = b, или более кратко R(a = b)S.

Рассмотрим экви-соединение на примере отношений R и S, имеющих связь 1:1 и представленных таблицами ниже.

Отношение R (современные короли и королевы)

ID Имя KINGDOM_ID
val Виллем-Александр NL
el2 Елизавета II GB
k16 Карл XVI Густав SE
ma2 Маргрета II DK
fil Филипп BE
fi6 Филипп VI ES
ha5 Харальд V NO

Отношение S (страны)

ID Название KING_ID
BE Бельгия fil
GB Великобритания el2
DK Дания ma2
ES Испания fi6
NL Нидерланды val
NO Норвегия ha5
SE Швеция k16

Операцией экви-соединения получим новое отношение, содержащее и страны, и их королей одновременно.

Благодаря тому, что между R и S установлена связь 1:1 (взаимооднозначное соответствие), можем использовать одно из двух условий c (результат будет тот же):

  1. R.KINGDOM_ID = S.ID.
  2. S.KING_ID = R.ID.

Отношение R(ID = KING_ID)S = R(KINGDOM_ID = ID)S

R.ID Имя KINGDOM_ID S.ID Название KING_ID
val Виллем-Александр NL NL Нидерланды val
el2 Елизавета II GB GB Великобритания el2
k16 Карл XVI Густав SE SE Швеция k16
ma2 Маргрета II DK DK Дания ma2
fil Филипп BE BE Бельгия fil
fi6 Филипп VI ES ES Испания fi6
ha5 Харальд V NO NO Норвегия ha5

Понятно, что получившееся отношение имеет избыточные атрибуты. После применения операций проекции и переименования атрибутов получим новое отношение P:

Отношение P

ID Имя правителя Название страны
NL Виллем-Александр Нидерланды
GB Елизавета II Великобритания
SE Карл XVI Густав Швеция
DK Маргрета II Дания
BE Филипп Бельгия
ES Филипп VI Испания
NO Харальд V Норвегия

Атрибуты в экви-соединении не обязательно должны быть ключами, но в этом виде соединения ключи в качестве атрибутов используются чаще всего.

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

Естественное соединение является особым видом соединения, при котором наличие одноимённых атрибутов между отношениями не только разрешено, но и является принципиально важным.

Пусть имеются отношение R с заголовком { a1, a2, ..., an, b1, b2, ... bk } и телом, содержащим кортежи вида (x1, x2, ..., xn, y1, y2, ..., yk), и отношение S с заголовком { b1, b2, ..., bk, c1, c2, ..., cm } и телом, содержащим кортежи вида (y1, y2, ..., yk, z1, z2, ..., zm). Атрибуты b1, b2, ..., bk отношений R и S совпадают (то есть совпадают их имена и типы).

Тогда естественным соединением отношений R и S называют соединение T, имеющее заголовок { a1, a2, ..., an, b1, b2, ... bk, c1, c2, ..., cm }, и тело, содержащее кортежи вида (x1, x2, ..., xn, y1, y2, ..., yk, z1, z2, ..., zm).

Таким образом, при естественном соединении кортежи вида (x1, x2, ..., xn, y1, y2, ..., yk) и (y1, y2, ..., yk, z1, z2, ..., zm) объединяются в один кортеж при совпадении между ними значений y1, y2, ..., yk.

Обозначение естественного соединения отношений R и S: R JOIN S.

Отношение G (Товары)

Название Количество Номер товара
Стол 16 501
Стул 64 502
Шкаф 8 503

Отношение P (Цена)

Цена Номер товара
1000 502
2000 501
5000 503

Общим атрибутом отношений G и P является только Номер товара.

Отношение G JOIN P

Название Количество Цена Номер товара
Стол 16 2000 501
Стул 64 1000 502
Шкаф 8 5000 503

Свойства операций над отношениями

Рекомендуется сперва прочесть: «Свойства бинарных операций (теория множеств)».

Обозначим символом ◇ произвольную реляционную операцию, тогда при изучении свойств обозначение ◇ ∈ { INTERSECT, UNION } будет означать, что свойство выполняется для операций пересечения и объединения.

  1. Идемпотентность унарных операций: ◇ R = ◇ (◇ R), ◇ ∈ { PROJECT, WHERE }. То есть R[a] = (R[a])[a] и R WHERE c = (R WHERE c) WHERE c.
  2. Идемпотентность бинарных операций: R ◇ R = R , ◇ ∈ { UNION, INTERSECT }.
  3. Коммутативность: R ◇ S = S ◇ R , ◇ ∈ { TIMES, JOIN, UNION, INTERSECT }. То есть R TIMES S = S TIMES R.
  4. Ассоциативность: (R ◇ S) ◇ T = R ◇ (S ◇ T) , ◇ ∈ { TIMES, JOIN, UNION, INTERSECT }.
  5. Дистрибутивность
  • проекции относительно пересечения, объединения, разности и декартова произведения: (R ◇ S)[a] = R[a] ◇ S[a], ◇ ∈ { INTERSECT, UNION, MINUS, TIMES }.
  • выборки относительно объединения и декартова произведения: (R ◇ S) WHERE c = (R WHERE c) ◇ (S WHERE c), ◇ ∈ { UNION, TIMES }.
  1. Выборку R WHERE c и проекцию R[a] можно менять местами при условии, что c зависит только от выбранных атрибутов a: (R WHERE c)[a] = R[a] WHERE c.

Важно отметить, что декартово произведение отношений коммутативно и ассоциативно в отличие от декартова произведения множеств. Это связано с тем, что кортежи отношения не должны быть упорядоченными.

Операция переименования атрибутов в общем случае не идемпотентна.

Функциональная зависимость

Функциональной зависимостью (англ. functional dependency) называют бинарное отношение между двумя подмножествами атрибутов некоторого отношения R.

Фактически, функциональная зависимость - это бинарное отношение между двумя ключами (англ. constraint between two keys) в некотором отношении R. Обычно функциональная зависимость отражает связь "один-ко-многим" (1:M).

Пусть у нас имеются два подмножества атрибутов A и B отношения R. Говорят, что множество B функционально зависит (англ. A functionally determine B) от множества A тогда и только тогда, когда каждое значение множества A связано в точности с одним значением множества B.

Говоря другими словами, если два кортежа отношения R совпадают по значениям в подмножестве атрибутов A, то эти кортежи также должны совпадать по значениям и в подмножестве атрибутов B.

Функциональную зависимость B от A обозначают: A → B, при этом подмножество атрибутов A называют детерминантом (англ. determinant set), а подмножество атрибутов B называют зависимой частью (англ. dependent set).

Функциональную зависимость называют тривиальной (англ. trivial), если B ⊆ A, то есть если зависимая часть является подмножеством детерминанта.

Отношение R (Работник)

ID Дата поступления Название проекта
ID1001 2019 Jest
ID1001 2020 Graphql Apollo
ID7017 2020 Graphql Apollo
ID7017 2021 Koa

Нормализация и нормальные формы

О нормальной форме и нормализации

Нормальной формой (англ. normal form) называют некоторое требование или совокупность требований, которым должно удовлетворять отношение для устранения избыточности.

Если эти требования выполняются для каждого отношения некоторой базы данных, то её называют нормализованной базой данных (англ. normalized database). Сам процесс приведения базы данных к нормализованному виду называется нормализацией этой базы данных (англ. database normalization).

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

Понятие нормализации ввёл Эдгар Кодд как часть своей реляционной модели.

О денормализации

Денормализацией базы данных (англ. database denormalization) называют процесс, обратный нормализации. В этом случае в базу данных умышленно добавляют избыточные данные (дубликаты данных) для ускорения получения данных.

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

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

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

Ниже представлен пример денормализации в табличном виде.

Публикация (дублирует только те поля пользователя, которые нужны для отображения на странице)

ID Заголовок Текст Автор
N1 Нормализация Нормализацией базы данных называют.... ID: U1
Никнейм: @max.starling
Почта: max.starling@email
N2 Денормализация Денормализацией базы данных называют.... ID: U1
Никнейм: @max.starling
Почта: max.starling@email
N3 Реляционная модель данных Реляционной моделью данных называют.... ID: U2
Никнейм: @ray.gray
Почта: ray.gray@email

Пользователь (хранит идентификаторы публикаций, чтобы публикации было проще найти на странице пользователя)

ID Никнейм Почта Возраст Публикации
U1 @max.starling max.starling@email 23 [N1, N2]
U2 @ray.gray ray.gray@email 27 [N3]

Ниже представлен пример денормализации в документном виде.

Публикации в формате JSON

[{
  "_id": "N1",
  "title": "Нормализация",
  "text": "Нормализацией базы данных называют....",
  "user": {
    "_id": "U1",
    "username": "@max.starling",
    "email": "max.starling@email"
  }
},
{
  "_id": "N2",
  "title": "Денормализация",
  "text": "Денормализацией базы данных называют....",
  "user": {
    "_id": "U1",
    "username": "@max.starling",
    "email": "max.starling@email"
  }
},
{
  "_id": "N3",
  "title": "Реляционная модель данных",
  "text": "Реляционной моделью данных называют....",
  "user": {
    "_id": "U2",
    "username": "@ray.gray",
    "email": "ray.gray@email"
  }
}]

Пользователи в формате JSON

[{
  "_id": "U1",
  "username": "@max.starling",
  "email": "max.starling@email",
  "age": 23,
  "posts": ["N1", "N2"]
}, {
  "_id": "U2",
  "username": "@ray.gray",
  "email": "ray.gray@email",
  "age": 27,
  "posts": ["N3"]
}]

Первая нормальная форма

Отношение находится в первой нормальной форме (англ. first normal form), 1НФ (англ. 1NF) тогда и только тогда, когда любой кортеж отношения может содержать только одно значение для каждого из атрибутов.

Таким образом, значение атрибута не может представлять собой набор значений (массив, множество, таблицу и так далее), если отношение находится в 1НФ.

В реляционной модели данных отношение всегда находится в 1НФ по своему определению.

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

Например, SQL не поддерживает использование столбцов с табличными значениями (англ. table-valued columns).

Пример ненормализованной таблицы:

Страна Город
Россия Москва, Санкт-Петербург
Украина Киев, Львов
Беларусь Минск

Пример нормализованной таблицы:

Страна Город
Россия Москва
Россия Санкт-Петербург
Украина Киев
Украина Львов
Беларусь Минск

Базы данных, которые нарушают первую нормальную форму, обычно называют NoSQL базами данных. Примером такой базы данных является документная база данных MongoDB, которая позволяет хранить любые JSON-документы (значения могут быть массивами или объектами).

Оптимизация баз данных

Паттерны баз данных

Движки баз данных

Проблема n + 1

N+1 проблема возникает, когда для получения связанных данных делается 1 запрос на основную сущность и n отдельных запросов на связанные сущности. Рассмотрим эту проблему на примере GraphQL и Prisma.

Например, у нас есть users и posts в отношении 1:M (один-ко-многим), мы хотим вытянуть данные о пользователях и их постах. При нативной реализации такого запроса на SQL мы сначала возьмём пользователей

SELECT * FROM users

а затем для каждого получаем посты по айди пользователя (n дополнительных запросов):

SELECT * FROM posts WHERE user_id = 1
SELECT * FROM posts WHERE user_id = 2
...
SELECT * FROM posts WHERE user_i = n

Отсюда и n + 1 запросов, что неэффективно.

Проблема решается объединением запросов при помощи JOIN. Например, на чистом SQL решение было бы следующим:

SELECT * FROM users u LEFT JOIN posts p WHERE p.user_id = u.id

Итого у нас лишь один запрос к базе вместо n + 1.

Проблема n + 1 в Prisma

Допустим, у нас есть следующая схема Prisma.

model User {
  id    Int    @id @default(autoincrement())
  name  String
  posts Post[]
}

model Post {
  id     Int    @id @default(autoincrement())
  title  String
  user   User   @relation(fields: [userId], references: [id])
  userId Int
}

Тогда проблема n + 1 выглядела бы так на языке JavaScript

const users = await prisma.user.findMany(); // 1 запрос, чтобы получить всех пользователей

const usersWithPosts = await Promise.all(
  users.map(async (user) => {
    const posts = await prisma.post.findMany({ where: { userId: user.id } }); // n запросов, по одному для каждого пользователя
    return { ...user, posts };
  })
);

Решение проблемы - жадная загрузка (англ. eager loading), подробнее о ней будет ещё далее.

  • через include
const usersWithPosts = await prisma.user.findMany({
  include: {
    posts: true, // загружаем связанные посты сразу
  },
});
  • через select
const usersWithPosts = await prisma.user.findMany({
  select: {
    id: true,
    name: true,
    posts: {
      select: {
        id: true,
        title: true,
      },
    },
  },
});

Проблема n + 1 в GraphQL

Пример проблемы n + 1 запроса в GraphQL

query {
  users {
    id
    name
    posts {
      id
      title
    }
  }
}
const resolvers = {
  Query: {
    users: () => prisma.user.findMany(), // 1 запрос
  },
  User: {
    posts: (parent) => prisma.post.findMany({ where: { userId: parent.id } }), // дополнительные n запросов
  },
};

Решение

  • через include в корневом запросе (если ORM предоставляет такую возможность)
const resolvers = {
  Query: {
    users: () => prisma.user.findMany({ include: { posts: true } }), // ✔️ Один запрос
  },
};

тогда GraphQL схема будет

type User {
  id: ID!
  name: String!
  posts: [Post!]!
}
  • через DataLoader
const postLoader = new DataLoader(async (userIds) => {
  const posts = await prisma.post.findMany({
    where: { userId: { in: userIds } },
  });

  // Группируем посты по userId
  return userIds.map(userId => posts.filter(post => post.userId === userId));
});
const resolvers = {
  User: {
    posts: (parent) => postLoader.load(parent.id), // одно обращение к DataLoader вместо n запросов
  },
};

Проблема n + 1 в MongoDB (NoSQL)

Оставляем задачу с пользователями и постами, имеем 1 запрос для пользователей и n запросов постов для каждого из n пользователей.

const users = await db.collection('users').find().toArray(); // 1 запрос

const usersWithPosts = await Promise.all(
  users.map(async (user) => {
    const posts = await db.collection('posts').find({ user_id: user._id }).toArray(); // n запросов
    return { ...user, posts };
  })
);

Почему плохо:

  • большая нагрузка на сервер (много запросов)
  • медленное выполнение
  • бОльшие траты из-за бОльшего количества облачных вычислений

Решение:

  • Денормализация. Хранить вложенные объекты (объекты постов вложены в объекты пользователей), не вынося их в разные коллекции.
{
  "_id": "123",
  "name": "Alice",
  "posts": [
    { "title": "Post 1" },
    { "title": "Post 2" }
  ]
}
  • Агрегации и $lookup (Аналог JOIN в MongoDB)
const usersWithPosts = await db.collection('users').aggregate([
  {
    $lookup: {
      from: "posts",
      localField: "_id",
      foreignField: "user_id",
      as: "posts"
    }
  }
]).toArray();
  • Запрос $in. Передаём список айдишек пользователей и имеем 1 + 1 запрос вместо n + 1:
const users = await db.collection('users').find().toArray();
const userIds = users.map(u => u._id);
const posts = await db.collection('posts').find({ user_id: { $in: userIds } }).toArray();

Проблема n + 1 в elasticsearch

Опять же, пользователи и посты.

Получаем пользователей.

GET /users/_search
{
  "query": {
    "match_all": {}
  }
}

Получаем посты для каждого из пользователей, n пользователей = n дополнительных запросов

GET /posts/_search
{
  "query": {
    "term": { "user_id": "1" }
  }
}

...

GET /posts/_search
{
  "query": {
    "term": { "user_id": "n" }
  }
}

Решения:

  • Денормализация. Поскольку Elasticsearch не реляционная база, то лучший способ оптимизировать запросы — избегать JOIN-подобных операций, вкладывать нужные данные сразу в документ (хранить вложенные (англ. nested) объекты).
  • Вложенные документы (англ. Nested fields). Если данные часто меняются и денормализация невозможна, то можно использовать тип nested. Тогда можно искать и фильтровать вложенные объекты без отдельного запроса.
{
  "mappings": {
    "properties": {
      "posts": {
        "type": "nested"
      }
    }
  }
}
  • Multi-search, batch-запросы. Если предыдущие опции не подходят, батчим запросы и отправляем их вместе
POST /_msearch
{ }
{ "query": { "term": { "user_id": "123" } } }
{ }
{ "query": { "term": { "user_id": "124" } } }
...
  • Запрос terms позволяет передать списком id пользователей. Таким образом вместо n + 1 запросов имеем 1 + 1 запрос (один на пользователей, один на посты):
GET /posts/_search
{
  "query": {
    "terms": {
      "user_id": [ "123", "124", "125", "126" ] // список всех id пользователей
    }
  }
}

Mongoose, проблема n + 1 и populate

Проблема n + 1 запросов в Mongoose часто возникает при использовании populate(), особенно в ситуациях, когда у нас есть список сущностей, и для каждой из них мы подгружаем связанные данные. Это может приводить к выполнению большого количества отдельных запросов к базе, что существенно замедляет приложение.

const UserSchema = new mongoose.Schema({
  name: String,
});

const PostSchema = new mongoose.Schema({
  title: String,
  author: { type: mongoose.Schema.Types.ObjectId, ref: 'User' },
});

Проблемы n + 1 в Mongoose

  • Проблема n + 1:
const posts = await Post.find();
for (const post of posts) {
  post.author = await User.findById(post.author);
}
  • Проблема n + 1 с populate в цикле:
const posts = await Post.find();
for (const post of posts) {
  await post.populate('author');
}

Решение проблемы

  • Многоуровневый populate:
const posts = await Post.find().populate({
  path: 'author',
  populate: { path: 'profile' }
});
  • populate на уровне поста (без цикла):
const posts = await Post.find().populate('author').lean();
  • Использование $in:
const posts = await Post.find();
const authorIds = posts.map(post => post.author);
const authors = await User.find({ _id: { $in: authorIds } }).lean();
const authorsMap = new Map();
authors.forEach(author => {
  authorsMap.set(author._id.toString(), author);
});
const postsWithAuthors = posts.map(post => ({
  ...post.toObject(),
  author: authorsMap.get(post.author.toString()) || null
}));

Сравнение жадной загрузки и populate

Жадная загрузка (англ. eager loading) — это общий подход для загрузки связанных данных сразу, а populate — конкретный механизм в Mongoose/MongoDB для подстановки связанных данных, который может вести себя как “ленивая” или “жадная” загрузка в зависимости от реализации.

  • Eager loading — архитектурный подход загрузки данных сразу (в SQL, Prisma и др.).
const users = await prisma.user.findMany({
  include: {
    posts: true, // жадная загрузка постов
  },
});
  • Populate — специфическая реализация этого подхода в MongoDB (но часто через дополнительные запросы, если не “optimized populate”).
const users = await User.find().populate('posts');

Оптимизация SQL-запросов

Анализ производительности запросов

Команда EXPLAIN — основной инструмент анализа производительности запросов.

EXPLAIN SELECT * FROM users WHERE email = 'test@example.com';

Она позволяет смотреть

  • типы доступа к данным (Index Scan, Full table scan и тд)
  • используемые индексы и их эффективность
  • количество просматриваемых строк

Используйте индексы правильно

Индексы – важнейший инструмент ускорения поиска запроса Создавайте индекс для полей, которые используются в

  • JOIN
  • WHERE
  • ORDER BY
  • GROUP BY

Учитывайте селективность (индексируйте поля с высокой уникальностью).

Пример создания индекса

CREATE INDEX idx_users_email ON users(email);

Выбирайте только нужные поля таблицы и не используйте SELECT *

# плохо
SELECT *
# хорошо
SELECT id, username FROM users; # хорошо

Избегайте лишних JOIN и подзапросов

Используйте JOIN вместо подзапросов, если это возможно

# плохо - подзапрос
SELECT id, (SELECT id FROM orders WHERE orders.user_id = users.id) FROM users;
# хорошо - JOIN
SELECT users.id, orders.id FROM users JOIN orders ON orders.user_id = users.id;

Используйте пагинацию, когда это возможно

Задайте LIMIT и OFFSET

SELECT id, username FROM users LIMIT 50 OFFSET 0;

Грамотно используйте условия WHERE и агрегацию

Регулярно чистите базу, выполняйте оптимизацию таблиц и перестройку индексов

OPTIMIZE TABLE your_table

Следите за производительностью запросов

Например, в MySQL можно сделать так

SET GLOBAL slow_query_log = 'ON';