PostgreSQL (Postgres) — это мощная реляционная база данных, способная хранить широкий спектр типов и структур данных. Когда нам нужно хранить графовые структуры данных, мы часто обращаемся к базам данных, позиционируемым как подходящее для этого решение, например, к Neo4J или Dgraph. Но не торопитесь! Хотя при работе с графовыми структурами данных о Postgres обычно не вспоминают, она идеально справляется с эффективным хранением графовых данных и запросами к ним.

Разбираемся с графовыми структурами данных

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


Визуальный пример графовой структуры данных.

Чтобы начать воспринимать графы в рамках кода, можно написать следующий TypeScript:

class Node {
  edges: Edge[] = [];
  data: string;
}

class Edge {
  previousNode: Node;
  nextNode?: Node;
}

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

Facebook — популярная социальная сеть, использующая для описания людей и их связей граф. У человека могут быть друзья, и у этих друзей тоже есть свой список друзей. Каждый человек представлен узлом, а каждую дружбу можно задать ребром. Графы используются для моделирования множества различных систем, например npm-зависимостей, рабочих процессов, транспортных систем, производственных линий и многого другого!

Хранение графовых структур данных в Postgres

Для хранения графа в Postgres нам достаточно создать две таблицы: nodes и edges. Таблица nodes будет хранить информацию о каждой сущности, а в таблице edges будет храниться информация о связях между этими сущностями.

Давайте начнём с создания таблицы nodes:

CREATE TABLE nodes (
  id SERIAL PRIMARY KEY,
  data VARCHAR(255)
);

Определённая нами таблица nodes имеет два столбца: id и data. Столбец id содержит целочисленные значения с автоматическим инкрементом, служащие первичным ключом таблицы. Столбец data — это строки, хранящие дополнительные данные, связанные с узлом. В этом примере мы не будем усложнять и сохраним только строковый столбец, однако в реальном мире эта таблица могла бы содержать что угодно и иметь любое количество столбцов.

Самой важной таблицей при создании графовой структуры данных является таблица edges:

CREATE TABLE edges (
  previous_node INTEGER REFERENCES nodes(id),
  next_node INTEGER REFERENCES nodes(id),
  PRIMARY KEY (previous_node, next_node)
);

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

Создав таблицы, мы можем вставить в них данные.

INSERT INTO nodes (data) VALUES ('Bob');
INSERT INTO nodes (data) VALUES ('Hank');
INSERT INTO nodes (data) VALUES ('Jeff');

А теперь соединим узлы рёбрами:

INSERT INTO edges (previous_node, next_node) VALUES (1, 2);
INSERT INTO edges (previous_node, next_node) VALUES (1, 3);

Если бы мы визуализировали этот граф, то он бы выглядел так:

Запросы к графовым структурам данных в Postgres

Создав графовую структуру данных, мы можем начать выполнять запросы к ней при помощи известного нам и любимого SQL!

Хотите знать, с кем дружит Боб?

SELECT id, data
FROM nodes
JOIN edges ON nodes.id = edges.next_node
WHERE edges.previous_node = 1;

Находим все nodes, связанные с узлом, имеющим id 1 (id Боба).

Похоже, Боб популярен! Но что, если мы захотим узнать, с кем дружат друзья Боба?

Давайте вставим ещё несколько узлов и рёбер, чтобы показать это:

INSERT INTO nodes (data) VALUES ('Sally');
INSERT INTO nodes (data) VALUES ('Sue');
INSERT INTO nodes (data) VALUES ('Sam');

INSERT INTO edges (previous_node, next_node) VALUES (2, 4);
INSERT INTO edges (previous_node, next_node) VALUES (3, 4);
INSERT INTO edges (previous_node, next_node) VALUES (4, 5);

Чтобы запросить всех друзей друзей Боба, мы можем расширить предыдущий запрос, снова выполнив в нём join таблицы edges, но тогда поддержка базы данных превратится в кошмар, ведь нам пришлось бы выполнять join для каждого «уровня» графа.

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

Чтобы создать рекурсивный запрос для поиска всех друзей Боба и их друзей, нам нужно написать следующий SQL:

WITH RECURSIVE friend_of_friend AS (
  SELECT edges.next_node
  FROM edges
  WHERE edges.previous_node = 1
  UNION
  SELECT edges.next_node
  FROM edges
  JOIN friend_of_friend ON edges.previous_node = friend_of_friend.next_node
)
SELECT nodes.data
FROM nodes
JOIN friend_of_friend ON nodes.id = friend_of_friend.next_node;

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

WITH RECURSIVE {name} AS (
  {base case}
  UNION
  {recursive case}
)

Выше показана простейшая структура SQL рекурсивного запроса.

В нашем примере нужно начать запрос с друзей Боба, чтобы найти рёбра, в которых Боб (id: 1) является previous_node. Затем в рекурсивном случае мы непрерывно выполняем join таблицы edges с самой собой, пока не достигнем конца графа Боба (то есть пока не достигнем friend_of_friend.next_node = NULL). Вне рекурсивного случая мы объединяем всё это вместе. Нам нужно запросить nodes, связанные с рёбрами из рекурсивного запроса, чтобы можно было получить имена всех друзей Боба.

В заключение

При помощи встроенных функций Postgres можно сохранять графовые структуры данных и выполнять к ним запросы. Мы использовали похожий подход в моей предыдущей работе для динамической генерации рабочих инструкций на производственной линии. На основании заданных параметров и определённых в каждом ребре правил можно сгенерировать корректный документ при помощи обхода графа, целиком хранящегося в Postgres. Если вы уже используете Postgres для работы с реляционными данными, то можете интегрировать графовые структуры данных в имеющуюся базу данных добавления лишних систем!