Перейти к основному содержимому

Теоретические основы реляционных данных

Play ITЗагрузка интерактивного демо…

ОБЯЗАТЕЛЬНОДЛЯ НОВИЧКОВ

Разработчику Аналитику Тестировщику
Архитектору Инженеру

Теория данных​

Эта глава — "под капотом" реляционной СУБД: от модели Кодда до страниц на диске, WAL и реляционной алгебры. Если знакомство отвечает на "что такое БД", а внутреннее устройство — на "как летит запрос", здесь собран скелет теории, на который опираются SQL, проектирование и администрирование.

Критерии "настоящей" реляционной системы — в отдельной главе Двенадцать правил Кодда. После чтения про WAL логично перейти к Восстановлению после сбоя и к резервному копированию.

Play ITЗагрузка интерактивного демо…

Основы теории информатики в части данных​

Теория данных вытекает из более общей теории информации, предложенной Клодом Шенноном, и из теории вычислимости, развитой Алонзо Чёрчем, Алланом Тьюрингом и другими. Однако в контексте информационных систем данные рассматриваются как структурированные объекты, подлежащие манипуляции в рамках строго определённых моделей.

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

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

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

Наиболее строго и формально развита реляционная модель данных (РМД), предложенная Эдгаром Ф. Коддом в 1969–1970 годах (статья A Relational Model of Data for Large Shared Data Banks). Она опирается на теорию множеств и логику первого порядка и остаётся основой большинства промышленных СУБД.

Состав реляционной модели данных​

РМД традиционно описывают тремя составляющими:

СоставляющаяСодержание
СтруктурнаяДанные — набор отношений (переменных отношений во времени)
ЦелостностиОтношения удовлетворяют ограничениям уровня домена, отношения и всей БД
Обработки (манипуляции)Реляционная алгебра и реляционное исчисление — операторы над отношениями

К модели относят также теорию нормализации (устранение избыточности и аномалий обновления).

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

Три опорных факта (по Кодду и Дейту):

  1. Модель логическая — отношения абстрактны, отдельно от физического размещения на диске.
  2. Информационный принцип — всё содержимое БД представлено явными значениями в кортежах; нет скрытых указателей между значениями (в отличие от сетевой навигации по ссылкам).
  3. Наличие алгебры даёт декларативные запросы и ограничения целостности поверх процедурного доступа.

Исторические альтернативы — иерархическая и сетевая модели; обзор — в Знакомстве с БД.

Отношение — заголовок, тело, ключи​

Отношение степени n — подмножество декартова произведения доменов T₁…Tₙ. Состоит из:

  • Заголовка (схемы) — конечного множества пар (имя атрибута, домен/тип); имена атрибутов в одном отношении уникальны.
  • Тела — множества кортежей; каждый кортеж — набор значений по атрибутам заголовка.

Свойства отношения (в строгой теории):

  • кортежи не повторяются;
  • порядок кортежей не определён;
  • порядок атрибутов в заголовке не определён.

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

К. Дж. Дейт формулирует пять условий, при которых таблица на экране — корректное представление отношения: нет упорядоченности строк и столбцов как носителя смысла; нет дубликатов строк; в каждой ячейке одно значение из домена; нет "скрытых" столбцов (суррогатных OID строк, недоступных в обычном SQL).

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

Целостность базы данных​

Целостность БД — соответствие данных внутренней логике, структуре и явно объявленным правилам. Каждое правило — ограничение целостности; СУБД отклоняет операции, которые его нарушают, и проверяет БД при добавлении нового ограничения.

В реляционной теории выделяют уровни ограничений:

УровеньПример
Тип (домен)Множество допустимых значений атрибута
АтрибутCHECK (возраст >= 0)
Переменная отношенияпотенциальный ключ, UNIQUE
База данныхвнешний ключ между отношениями

Целостность и истинность данных — разные вещи. СУБД гарантирует непротиворечивость (нет "висячих" FK, отрицательного веса, если так запрещено), но не знает реальный мир: в БД может лежать ошибочный, но формально допустимый факт. Проверку смысла (верны ли остатки на складе) обеспечивают приложение, процессы и люди.

Подробнее про внешние ключи в проектировании — Entity Relationship; про ссылочную целостность на диске — раздел ниже в этой главе.

Согласованность данных​

Согласованность данных (англ. data consistency, в русскоязычных текстах иногда консистентность) — согласованность значений друг с другом, целостность и внутренняя непротиворечивость набора данных.

КонтекстЧто задаёт согласованность
ER-модельДопустимые значения атрибутов сущностей; какие связи можно устанавливать; минимальное и максимальное число связей данного типа для одного узла
Реляционная БДОграничения целостности (ключи, домены, CHECK, внешние ключи) — см. таблицу выше
Структуры данных в кодеИнварианты структуры: у BST — отсутствие циклов, порядок ключей, согласованность указателей parent с left/right
ООПИнкапсуляция: операции над объектом не выводят его из согласованного состояния

Целостность в СУБД — частный и формализованный случай согласованности: правила объявлены в схеме и проверяются движком. Согласованность в распределённых системах (реплики, кэши, микросервисы) шире одной транзакции — см. конкурентный доступ и материалы про eventual consistency в разделе микросервисов.

Случайные байты в массиве фиксированной длины дают набор чисел без "поломки" структуры; в строке UTF-8 те же байты могут нарушить кодировку — пример, почему согласованность привязана к модели данных, а не только к объёму памяти.

Как работает база данных и СУБД на самом низшем уровне​

Система управления базами данных (СУБД) — это программный комплекс, предоставляющий интерфейс для хранения, извлечения, модификации и управления данными с гарантией их целостности, безопасности и производительности. На самом низком уровне СУБД — это набор алгоритмов и структур данных, которые взаимодействуют с операционной системой и, через неё, с аппаратными ресурсами вычислительной машины.

Основные компоненты СУБД на уровне реализации:

  • Менеджер буферов (Buffer Manager) — отвечает за перемещение данных между оперативной памятью и диском.
  • Менеджер дискового пространства (Storage Manager) — управляет физическим расположением данных на диске, включая файлы, страницы и блоки.
  • Менеджер транзакций (Transaction Manager) — обеспечивает ACID-свойства (атомарность, согласованность, изолированность, долговечность).
  • Менеджер выполнения запросов (Query Execution Engine) — преобразует логические операции (например, SELECT) в последовательность физических действий над данными.
  • Оптимизатор запросов (Query Optimizer) — выбирает наиболее эффективный план выполнения запроса на основе статистики и стоимости операций.

На аппаратном уровне данные хранятся в виде последовательностей байтов на энергонезависимом носителе — традиционно на жёстком диске (HDD) или твердотельном накопителе (SSD). СУБД использует системные вызовы операционной системы (read, write, mmap и др.) для доступа к файлам базы данных.

Где хранятся данные (на диске)​

Физическое хранение данных в реляционной СУБД обычно организовано по принципу страничной структуры. База данных представляет собой один или несколько файлов, разделённых на фиксированные блоки — страницы (pages), типичный размер которых составляет 4 КБ, 8 КБ или 16 КБ, в зависимости от СУБД (например, PostgreSQL использует 8 КБ, Microsoft SQL Server — 8 КБ по умолчанию).

Каждая страница содержит:

  • заголовок (метаданные — тип страницы, идентификатор отношения, контрольные суммы и т.п.);
  • тело — фрагменты записей (tuples или rows);
  • иногда — слот-массив, указывающий смещения записей внутри страницы.

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

Важно понимать: диск — это иерархический, последовательный по природе носитель. Даже в SSD, где отсутствует механический seek, эффективность чтения/записи зависит от выравнивания блоков и внутренней архитектуры контроллера NAND-памяти. Поэтому СУБД стремятся минимизировать количество случайных обращений и максимизировать локальность данных.

Как СУБД работает с диском​

Когда приходит SQL-запрос, например SELECT * FROM users WHERE id = 100, СУБД не читает всю таблицу с диска целиком. Вместо этого она:

  1. Анализирует запрос и строит его логическое представление (предикаты, соединения и т.п.).
  2. Оптимизатор выбирает план выполнения — например, использовать индекс по полю id.
  3. Менеджер выполнения инициирует чтение нужных страниц с диска через менеджер буферов.
  4. Менеджер буферов проверяет, есть ли запрашиваемая страница в оперативной памяти (в буферном пуле). Если нет — выполняется системный вызов для чтения с диска.
  5. Прочитанная страница кэшируется в памяти, чтобы последующие запросы к тем же данным не требовали повторного обращения к диску.

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

СУБД также использует запись журналов (Write-Ahead Logging, WAL) — перед тем как изменить данные на диске, СУБД записывает изменения в специальный лог (журнал транзакций), что позволяет восстановить согласованное состояние после сбоя.

Почему базы данных предпочтительнее хранения в ОЗУ​

Хранение данных исключительно в оперативной памяти (in-memory) возможно и используется в специализированных системах (например, Redis, SingleStore — ранее MemSQL, in-memory OLTP в SQL Server). Однако классические СУБД с дисковым хранением обладают рядом фундаментальных преимуществ:

  • Долговечность (Durability): данные сохраняются после выключения питания или аварийного завершения работы. ОЗУ — энергозависимый ресурс.
  • Масштабируемость по объёму: объём диска измеряется терабайтами и петабайтами, тогда как ОЗУ ограничено физическими и экономическими рамками.
  • Контроль целостности — СУБД реализует сложные механизмы (ограничения, внешние ключи, триггеры, ACID), которые невозможно или нецелесообразно воспроизводить вручную в пользовательском коде.
  • Конкуренция и изоляция — СУБД управляет параллельным доступом множества клиентов к данным, обеспечивая корректность через механизмы блокировок, MVCC (многоверсионного управления конкурентным доступом) и т.д.
  • Оптимизированная работа с носителем — СУБД знают структуру данных и могут эффективно использовать индексы, кластеризацию, сжатие и предвыборку (prefetching), что недоступно при простом хранении в памяти.

In-memory хранилища — это частный случай, оправданный при строгих требованиях к задержке, но они не заменяют дисковые СУБД в общем случае.

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

Мост из дискретной математики

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

Ниже — алгебра Кодда (σ, π, ⋈), на которой строится оптимизатор SQL.

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

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

  • Выборку (selection) — фильтрация строк по условию;
  • Проекцию (projection) — выбор подмножества столбцов;
  • Декартово произведение — комбинирование всех строк двух отношений;
  • Соединение (join) — комбинирование строк с учётом условия соответствия;
  • Объединение, пересечение и разность — теоретико-множественные операции над совместимыми по структуре отношениями;
  • Переименование атрибутов — изменение имён столбцов без изменения содержания.

Каждая операция алгебры строго определена и всегда возвращает корректное отношение. Это позволяет строить планы выполнения запросов как последовательности этих операций. Именно реляционная алгебра лежит в основе внутреннего представления SQL-запросов в большинстве СУБД — парсер SQL преобразует запрос в древовидную структуру, соответствующую выражению реляционной алгебры, которое затем оптимизируется и исполняется.

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

Ключевой теоретический результат — эквивалентность реляционной алгебры и реляционного исчисления в выразительной силе. Это означает, что любой запрос, выразимый в одной системе, может быть выражен и в другой. Более того, Кодд ввёл понятие реляционной полноты: СУБД считается реляционно полной, если она способна реализовать все операции реляционной алгебры. SQL, несмотря на некоторые отклонения от чистой теории (например, допускает дубликаты строк и отсутствие полной поддержки всех свойств отношений), в своей основе соответствует этому требованию.

Эти формальные основы обеспечивают предсказуемость и корректность обработки данных. Пользователь описывает что ему нужно, а СУБД берёт на себя задачу как это получить, используя мощный аппарат оптимизации на основе алгебраических преобразований и статистики данных.

Как вычисляются связи на низком уровне​

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

На логическом уровне это выглядит как декларативное правило: "значение столбца user_id в таблице orders должно существовать в столбце id таблицы `users". Однако на физическом уровне реализация этого правила требует конкретных механизмов.

Проверка внешнего ключа выполняется СУБД в момент модификации данных:

  • При вставке строки в дочернюю таблицу (orders) СУБД ищет соответствующую запись в родительской таблице (users). Это поиск по индексу первичного ключа — операция, в большинстве случаев логарифмическая по времени.
  • При удалении или обновлении строки в родительской таблице СУБД проверяет, ссылаются ли на неё какие-либо строки в дочерних таблицах. В зависимости от политики (например, CASCADE, RESTRICT, SET NULL) могут быть выполнены дополнительные действия.

Важно: сами связи не хранятся как отдельные объекты на диске. Нет "ссылок" в том смысле, в каком они существуют в памяти (например, указатели). Связь — это логическое ограничение, реализуемое через:

  • наличие индексов по столбцам внешнего и первичного ключей (для эффективного поиска);
  • выполнение проверок при операциях изменения данных;
  • поддержание согласованности при восстановлении после сбоев (через WAL-журналы).

При выполнении операции соединения (JOIN) СУБД физически комбинирует строки из двух таблиц, сопоставляя значения в соответствующих столбцах. Существует несколько алгоритмов соединения:

  • Вложенные циклы (nested loops) — для каждой строки из левой таблицы просматриваются все строки правой;
  • Соединение по хешу (hash join) — строится хеш-таблица по одной таблице, затем вторая таблица сканируется и сверяется по хешу;
  • Сортировка и слияние (sort-merge join) — обе таблицы сортируются по ключу соединения, затем выполняется линейное слияние.

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

Таким образом, связи в реляционной модели — это логические зависимости, поддерживаемые через индексы, алгоритмы соединения и механизмы контроля целостности, реализованные на уровне СУБД.

См. также​

Содержание