Как создать реляционную базу данных с нуля
Открытие черного ящика реляционных баз данных
Реляционные базы данных потрясающие. Они не только очень эффективны при хранении данных, но также имеют прекрасную математическую теорию. Однако, особенно когда кто-то использует базу данных через ORM, это может показаться черным ящиком. Открытие черных ящиков - отличный способ овладеть предметом, поэтому я решил углубиться в детали и самостоятельно создать минимальную, но функциональную систему реляционных баз данных. В этом посте я делюсь с вами своим путешествием.
Вместо того, чтобы пытаться проследить, как SQL работает изнутри, моя цель - показать фундаментальные принципы, лежащие в основе реляционных баз данных. Даже если кто-то хочет быть более конкретным, существует несколько диалектов SQL, таких как PostgreSQL, MySQL и многие другие, которые могут иметь существенные различия.
Прежде чем мы углубимся в реализацию, мы должны иметь твердое представление о лежащих в основе математических объектах. Итак, давайте поговорим о том, какие отношения есть на самом деле!
(Если вы хотите интерактивно следить и поиграть с кодом, вы можете найти репозиторий на GitHub по адресу https://github.com/cosmic-cortex/relational-databases-from-scratch!)
связи
«Математики похожи на французов: все, что вы им говорите, они переводят на их родной язык, и сразу получается нечто совершенно иное». - Иоганн Вольфганг фон Гете
Чтобы понять реляционные базы данных, сначала мы определим, что такое отношение. С математической точки зрения отношение R над множествами
является подмножеством их декартова произведения:
Чтобы дать вам пример, оператор ‹является отношением. Вы можете думать об этом как о наборе всех кортежей натуральных чисел, где первый элемент в кортеже меньше второго. Вот как на самом деле ‹определяется в математике.
Более конкретный пример поможет понять это абстрактное определение. Предположим, мы говорим о сотрудниках компании. У каждого сотрудника есть уникальный идентификатор, имя, должность и зарплата:
В этой модели сотрудник - это вектор четырех измерений:
Отношения сотрудников - это набор из них. Используя терминологию реляционных баз данных, отношение соответствует таблице, а элемент отношения - это запись в этой таблице. В дальнейшем я буду использовать эти термины как синонимы.
В Python мы собираемся моделировать записи с помощью специальных словарей и таблиц с набором записей. Мы могли бы использовать что-то более сложное (например, pandas фреймы данных), но они будут идеальными. Обратите внимание, что при использовании наборов повторяющиеся записи не допускаются.
Поскольку словари по умолчанию не хэшируются, их нельзя вставлять в наборы. Чтобы обойти это, я добавил хэш-метод для класса Record, который возвращает хэш кортежа, полученного с помощью dict.
Это опасно, поэтому мы должны быть осторожны. Поскольку словари изменяемы, их «хэш» (как я определил выше) может изменяться. Таким образом, если вы поместите это в набор и измените одно из его значений, хеш изменится, и поскольку наборы в Python используют хеши под капотом, это может испортить ситуацию. Итак, чтобы избежать этого, я явно отключил изменение записи, перезаписав специальный метод __setitem__.
Чтобы иметь больше данных, с которыми можно поиграть, мы также добавим таблицу для задач со следующими столбцами: id, employee_id, completed. employee_id будет описывать, какой сотрудник выполняет задачу с идентификатором id, а completed является просто логическим значением, указывающим его статус.
Наши таблицы будут наборами записей, которые мы пока создаем вручную.
Теперь, когда мы заложили надлежащую основу, пришло время взглянуть на то, что заставляет реляционные базы данных работать: на операции.
Реляционная алгебра: операции над отношениями
Реляционная база данных была бы практически бесполезной, если бы у нас не было способов извлекать и структурировать информацию в базе данных. Эта задача достигается применением операторов к отношениям. Реляционная алгебра - это математическая структура, определяемая этими операциями. Точнее, элементы реляционной алгебры - это функции, входы и выходы которых являются отношениями.
Если это звучит для вас слишком абстрактно, давайте рассмотрим несколько конкретных примеров!
Выбор
Одним из наиболее фундаментальных операторов является операция выбора, которая фильтрует отношение на основе определенных условий. Обозначается он
где C обозначает условия. В нашем примере базы данных условием может быть «зарплата сотрудника более 60000». Его можно рассматривать как функцию, которая принимает запись и возвращает логическое значение, указывающее, выполнено ли условие.
Если мы применим условие «зарплата более 60000» для нашей employees таблицы, мы получим вот что.
Проекция
Оператор select используется для выбора записей в нашей таблице. Однако мы могли бы также применить фильтры к столбцам для удаления ненужной информации. Это можно сделать с помощью оператора проекции. Обозначается
где S обозначает список столбцов, которые должны остаться. Это также довольно просто реализовать в наших условиях.
Вот что происходит, когда мы проецируем таблицу employees на столбцы id и name.
Переименовать
Переименование столбцов часто бывает очень полезным. Например, в обеих наших таблицах есть столбец id, что может внести некоторую двусмысленность, поэтому необходимо его переименовать.
Перекрестный продукт
Здесь начинается самое интересное. Истинная сила реляционных баз данных заключается в том, что вы можете объединять информацию в нескольких таблицах и отвечать на сложные вопросы, запрашивая эти объединенные таблицы. Самый простой способ сделать это - взять перекрестное произведение, которое объединяет записи всеми возможными способами. Я собираюсь показать пример перед реализацией, чтобы убедиться, что он понятен.
Здесь мы видим, что конфликтующие имена столбцов могут стать проблемой. Перед тем, как быть взято перекрестное произведение, каждый столбец имеет префикс с именем таблицы для каждой таблицы.
Оператор перекрестного произведения обозначается
Вы, наверное, заметили, что кросс-продукт объединяет информацию без учета логической последовательности. Некоторые записи в таблице по продуктам показывают сотрудника и задачу, принадлежащую другому сотруднику. Мы исправим это позже, когда будем использовать объединения.
Союз
Итак, мы увидели, что с помощью перекрестного произведения мы можем комбинировать таблицы «по горизонтали». Естественно ожидать того же «по вертикали», как и в случае с фильтрацией строк (select) и столбцов (project). Это можно сделать с помощью оператора union.
Строго говоря, этот оператор не имеет смысла, когда в таблицах есть отдельные столбцы. Однако для этого есть решение: недостающие столбцы можно дополнить нулевыми значениями, такими как None.
Разница
Наш последний оператор - это difference, что опять же похоже на теоретико-множественное различие. Он просто удаляет строки одной таблицы из другой.
Поскольку таблицы в нашей реализации являются наборами, мы можем просто использовать встроенный метод.
Вы могли заметить, что перекресток отсутствует. Это потому, что пересечение может быть выражено с разницей как
or
difference(left, difference(left, right))
в коде.
Случай оператора пересечения не единственный. Фактически, все соответствующие операторы могут быть получены как комбинация предыдущих шести операторов, как мы увидим позже.
SQL-запросы в терминах реляционной алгебры
Теперь, когда у нас есть все эти, казалось бы, абстрактные операции, мы можем начать видеть, как запросы SQL преобразуются в реляционную алгебру. Предположим, мы хотим запросить имена всех сотрудников, у которых зарплата превышает 60 тысяч долларов США. В SQL это выглядело бы так:
SELECT name FROM employees WHERE salary > 60000
В нашей реализации это эквивалентно
temp_table = select(employees, [lambda x: x['salary'] > 60000]) result = project(temp_table, ['name'])
Итак, мы видим, что наши инструменты достаточно мощные, чтобы выражать запросы такого типа. Однако самое интересное еще впереди. Чтобы иметь возможность отвечать на более сложные вопросы, касающиеся наших данных (например, какова средняя зарплата тех сотрудников, у которых есть незавершенная задача), нам нужно иметь возможность разумно комбинировать информацию между таблицами. Это делается с помощью соединений.
Присоединяется
Существует несколько методов объединения таблиц в реляционной алгебре. До сих пор мы видели одно: перекрестное произведение, которое объединяет все записи вместе, даже если они логически не согласованы. Однако комбинирование таблиц по горизонтали может быть выполнено таким образом, чтобы итоговая таблица содержала значимую информацию. Опять же, для этого есть несколько способов. Мы начнем с самого фундаментального: тета-соединения.
Тета присоединиться
Оператор тета-соединения - это просто комбинация операций перекрестного произведения и выбора. Обозначается
где θ обозначает условие выбора. Например, тета-соединение сотрудников и задач при условии совпадения employee['id'] и task['employee_id'] выглядит следующим образом.
Как видите, это решает проблему, которая была у нас для перекрестного продукта, когда задача в данной записи не обязательно принадлежала сотруднику в той же записи.
Внешние соединения
В некоторых случаях полезно сохранить некоторую информацию во время соединения, даже если в другой таблице нет логически соответствующего элемента. Это то, что делают операторы левого / правого / полного внешнего соединения. Мы не будем вдаваться в подробности, но эти операторы берут строки в левой / правой / обеих таблицах, которые отсутствуют в тета-соединении, и объединяют их вместе.
Запросы как элементы реляционной алгебры
Мы видели, что большинство запросов, даже объединений, можно выразить всего шестью операторами:
- Выбирать
- Проект
- Переименовать
- Перекрестный продукт
- Союз
- Разница
Чтобы увидеть более сложный запрос, давайте представим третью таблицу, содержащую клиентов Dunder Mifflin Scranton. У каждого клиента есть id, name и contact_id, которые являются идентификатором контактного сотрудника.
Теперь рассмотрим следующий вопрос: «как зовут клиентов, в контактах которых есть хотя бы одна незавершенная задача?»
Чтобы ответить на этот вопрос, мы должны объединить информацию из всех трех таблиц. Полезно продумать шаги, которые нам нужно предпринять. Здесь мы собираемся
- найти сотрудников, у которых есть незавершенные задачи, объединив таблицы employee и tasks вместе,
- присоедините полученную таблицу к таблице clients, чтобы сопоставить имена клиентов с сотрудниками,
- выберите имена клиентов, проецируя их в столбец имени клиента.
В коде это будет выглядеть следующим образом.
Независимо от сложности, каждый запрос можно представить в виде графика, называемого деревом выражений.
Фактически, это не единственный возможный способ выполнить этот запрос, есть альтернативные решения. Например, мы могли бы сразу создать перекрестный продукт для всех трех таблиц и отфильтровать необходимые записи с помощью одного select. При использовании SQL движок пытается оптимизировать запрос, оценивая требуемую стоимость для данного плана выполнения и выбирая наиболее оптимальный для вас.
От реляционной алгебры к SQL
Реляционная алгебра - это лишь верхушка айсберга. Он дает нам строительные блоки для представления запросов, однако не дает нам инструментов, чтобы найти, как запрос может быть оптимально представлен. Под капотом SQL фактически использует реляционное исчисление, которое по сути является декларативным языком, основанным на реляционной алгебре. Это означает, что вы описываете только то, что хотите, а не то, как вы этого хотите. Последняя часть выясняется двигателем.
Нам не хватает основных функций SQL, таких как, например, агрегаты, то есть функции, отображающие отношения к элементам, такие как функция усреднения. Итак, до полнофункциональной реляционной базы данных еще предстоит пройти долгий путь. Однако основы заложены, и путь к этому ясен.
Ресурсы
Во время моих поисков у меня было два отличных ресурса, которые помогли мне построить реляционную базу данных:
