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

В этой статье мы рассмотрим несколько тем:

когда стоит использовать графовые СУБД, а когда нет;
как моделировать данные в формате графа в базе;
за счет чего Neo4j получает прирост в производительности при работе с графами;
как писать запросы на языке Cypher.

Зачем вообще нужны графовые СУБД?

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

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

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

Графовые СУБД хороший выбор, если:

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

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

Ну и наоборот, графовые СУБД плохой выбор, если:

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

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

Основы графового моделирования в Neo4j

Neo4j - open-source графовая СУБД, написанная на Java. Прежде всего стоит сказать, что в Neo4j вершины графа называются узлами, а ребра - отношениями.

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

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

На изображении ниже представлен простой граф в Neo4j, где содержатся узлы книг, их авторов и покупателей, а также имеются связи, сообщающие о факте написания или покупки книги. Например, узел со свойством name: Graham Greene одновременно имеет две метки: Person и Author. Он связан по средствам отношения WROTE с узлом книги, имеющей название Out Man in Havana.

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

Рассматриваемая предметная область, но уже в табличном виде

Запомните то, что в Neo4j тип сущности не регулирует то, какие поля будут у этой сущности. Если в реляционной СУБД мы указали, что таблица персон имеет определенные столбцы, то каждая запись в этой таблице будет иметь значение для них. Но в Neo4j узлы с одинаковыми метками или отношения с одинаковыми типами могут иметь абсолютно разные поля , т.е. в один момент времени в базе данных может храниться узел Person с одним полем name и узел Person с тремя полями first_name, last_name и age.

При проектировании графовой базы данных отличной отправной точкой может быть следование простыми правилами:

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

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

Графовая модель зависит от данных и запросов

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

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

На рисунке ниже представлены узлы с меткой Airport и полями name и code. Отношение типа FLYING_TO между аэропортами - это сущность рейса, которая имеет поля code, airline, departure, arrival и distance.

Два аэропорта, связанные отношением FLYING_TO — Два аэропорта, связанные отношением `FLYING_TO`

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

Добавили узел с меткой Flight для представления сущности рейса — Добавили узел с меткой `Flight` для представления сущности рейса

Теперь начинается самое интересное - оптимизация модели базы данных под запрос. Напоминаю, наша задача - фильтровать рейсы. Подумаем о том, что есть крупные аэропорты, у которых в один день может быть например 1000 перелетов, т.е. очень много отношений HAS_FLIGHT (365 000 за год). Чтобы сделать выборку рейсов такого аэропорта по дате, нам нужно перебирать отношения HAS_FLIGHT и проходить по ним к узлам Flight, чтобы проверить подходит ли дата рейса. Для решения этой проблемы мы можем добавить узел дня между аэропортом и рейсом, тогда у аэропорта всего будет 365 связей (если рассматриваем 1 год):

Добавили узел с меткой AirportDay между аэропортом и рейсом — Добавили узел с меткой `AirportDay` между аэропортом и рейсом

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

Но проблема с ненужным переходом от аэропорта до связанного узла для проверки даты перелета все еще не решена. Мы по прежнему должны переходить по каждой связи HAS_DAY, чтобы узнать дату рейса. Чтобы исправить это, мы можем перенести свойство даты из узла AirportDay в отношение HAS_DAY, тогда будем проверять свойство у отношения. Но можно сделать еще быстрее - перенести дату не в поля отношения, а в его тип:

Тип отношения HAS_DAY заменен типом, содержащим дату рейса — Тип отношения `HAS_DAY` заменен типом, содержащим дату рейса

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

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

Больше никаких аэропортов в базе данных авиарейсов!

При поиске подходящих рейсов пассажир указывает аэропорт отправления и аэропорт прибытия. Чтобы найти рейсы от одного конкретного аэропорта до другого, нужно перебрать каждый сегодняшний рейс и проследовать по связи DESTINATION, чтобы узнать аэропорт прибытия и решить подходит ли он нам. Мы знаем, что у одного аэропорта может быть много рейсов за день, но гораздо меньше различных конечных точек перелетов. Например, в день может быть 1000 рейсов из аэропорта, но различных направлений всего 100. Для оптимизации добавим узел Destination к каждому узлу AirportDay и таким образом уменьшим количество связей, которые нужно перебрать для поиска подходящих рейсов.

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

Внутреннее устройство Neo4j

Neo4j - это нативная графовая СУБД, в которой используется смежность без индексов (index-free adjacency) - способ хранения, при котором узлы физически хранят указатели на своих соседей, что исключает необходимости поиска по индексу во время обхода графа.

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

Например, наша база данных в реляционной СУБД состоит из трех таблиц:

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

Мы хотим получить идентификаторы тех постов, которые лайкнул определенный пользователь. Сперва нам нужно найти пользователя по его ID в таблице users. Затем найти ID тех постов, которые он лайнул, соединив таблицу likes с таблицей пользователей по user_id, что требует пройтись по всем строкам индекса, соответствующим этому пользователю, а такая операция становится довольно ресурсоемкой по мере увеличения данных в таблицах. Алгоритмическая сложность растет с увеличением уровня связей (количеством таблиц, которые нужно джоинить).

В случае с Neo4j нам потребуется также как и в реляционной СУБД сперва найти пользователя по ID, а затем просто перебрать исходящие из узла отношения типа LIKES с затратами O(1) на каждое, что будет гораздо быстрее. При этом количество данных в базе и увеличение уровня связей не повлияют на скорость выполнения запроса с проходом по связям в отличие от реляционных СУБД. Достигается это за счет физического хранения графа на диске.

Как же организовано хранение данных в Neo4j?

Есть 5 сущностей:

Узел;
Метка (тип узла);
Отношение;
Тип отношения;
Свойства.

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

Структура хранения узлов и отношений в файлах Neo4j

Все узлы хранятся в файле neostore.nodestore.db. Каждая запись узла имеет фиксированную длину в 15 байтов и хранит следующие данные:

inUse - задействована ли запись или в нее можно поместить сведения о новом узле;
nextRelId - указатель на первое отношения узла;
nextPropId - указатель на первое свойства узла;
labels - указатель на метку узла в хранилище меток;
extra - для признаков (одним из таких признаков является идентификация тесно связанных узлов).

Отношения хранятся в файле neostore.relationshipstore.db. Запись каждого отношения также имеет фиксированный размер. Каждая запись содержит следующие данные:

inUse - задействована ли запись;
firstNode и secondNode - указатели на начальный узел и конечный;
relationshipType - указатель на тип взаимосвязи;
firstPrevRelId и firstNextRelId - указатели на следующее отношение и предыдущее для начального узла;
secondPrevRelId и secondNextRelId - указатели на следующее отношение и предыдущее для конечного узла;
nextPropId - указатель на первое свойство отношения;
firstInChainMarker - является ли текущая запись первой в цепочке отношений.

На рисунке ниже показано как физически хранится граф в Neo4j:

Схема физического хранения графа в Neo4j

Запись об узле содержит указатель на первое свойство узла и первую связь. Чтобы прочитать все свойства узла, необходимо обойти однонаправленный список, начав с указателя на первое свойство. Чтобы найти отношения узла, нужно перейти по указателю на первое отношение (в данном случае LIKES) и проследовать по двусвязанному списку для рассматриваемого узла. Интересный момент - одно отношение содержит указатели для перехода по двусвязанному списку отношений как для начального узла так и для конечного. Получив запись взаимосвязи, можно прочитать свойства этой взаимосвязи с помощью такого же односвязанного списка, как для свойств узла, или перейти к записям двух связанных узлов по указателям.

Язык запросов Cypher

В Neo4j используется декларативный язык запросов Cypher с довольно понятным "ASCII-art-like" форматом описания маршрутов. В запросах мы буквально рисуем с помощью кружков и стрелочек шаблон, по которому будем искать необходимые данные.

Маршрут в графе и запрос, по которому он будет найден

На примере графа с авторами, книгами и покупателями мы разберем базовые возможности Cypher:

создание узлов и отношений между ними;
обновление полей у узлов и отношений;
поиск узлов и отношений.

Граф, с которым будем работать с помощью Cypher

Создание узлов и отношений

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

Первым делом создадим узел одной из книг. В запросе мы указываем что создаваемый узел будет иметь метку Book и поле title со значением:

CREATE (:Book {title:"Tinker, Tailor, Soldier, Spy"})

Теперь создадим узел автора этой книги. В отличие от предыдущего запроса укажем две метки для узла (Person и Author):

CREATE (:Person:Author {name:"John Le Carre"})

Указывая две метки для узла автора, мы присоединяем его к множеству персон и множеству авторов, благодаря чему сможем найти этот узел как по метке Author, так и по метке Person.

Для создание связи WROTE между автором и книгой выполним более сложный запрос. Сперва потребуется найти уже созданные узлы автора и книги с нужными полями с помощью ключевого слова MATCH:

MATCH (author:Author {name:"John Le Carre"})
MATCH (book:Book {title:"Tinker, Tailor, Soldier, Spy"})
CREATE (author)-[:WROTE]->(book)

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

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

MATCH (book:Book {title:"Tinker, Tailor, Soldier, Spy"})
CREATE (:Person {name:"Alan"})-[:PURCHASED {date:date("2011-09-09")}]->(book)
CREATE (:Person {name:"Ian"})-[:PURCHASED {date:date("2011-07-05")}]->(book)

Для завершения создания желаемого графа остается совсем немного. Добавим недостающего автора и книгу со связью между ними:

CREATE (:Person:Author {name:"Graham Greene"})-[:WROTE]->(:Book {title:"Our Man in Havana"})

Свяжем книгу Our Man in Havana с покупателем Ian:

MATCH (book:Book {title:"Our Man in Havana"})
MATCH (ian:Person {name:"Ian"})
CREATE (ian)-[:PURCHASED {date: date("2011-09-09")}]->(book)

Обновление данных

Теперь рассмотрим возможность обновления данных в графе. С помощью ключевого слова SET мы можем добавить/изменить/удалить поле у узла или отношения.

MATCH (b:Book {title:"Tinker, Tailor, Soldier, Spy"})
SET b.price = 1000

MATCH (b:Book {title: "Our Man in Havana"})
SET b.price = 2000

Можем найти все отношения типа PURCHASED и задать им одинаковую дату:

MATCH ()-[p:PURCHASED]-()
SET p.date = date("2025-02-06")

Если нужно удалить поле, то просто присваиваем ему null. Если в Neo4j поле = null, значит поля нет.

Выборка данных

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

Запрос на получение всех узлов в базе:

MATCH (n) RETURN n

╒═══════════════════════════════════════════════════════════╕
│n                                                          │
╞═══════════════════════════════════════════════════════════╡
│(:Book {price: 1000,title: "Tinker, Tailor, Soldier, Spy"})│
├───────────────────────────────────────────────────────────┤
│(:Author:Person {name: "Graham Greene"})                   │
├───────────────────────────────────────────────────────────┤
│(:Author:Person {name: "John Le Carre"})                   │
├───────────────────────────────────────────────────────────┤
│(:Person {name: "Alan"})                                   │
├───────────────────────────────────────────────────────────┤
│(:Book {price: 2000,title: "Our Man in Havana"})           │
├───────────────────────────────────────────────────────────┤
│(:Person {name: "Ian"})                                    │
└───────────────────────────────────────────────────────────┘

Теперь добавим фильтрацию по типу узла. Получим все узлы с меткой Book:

MATCH (n:Book) RETURN n

╒═══════════════════════════════════════════════════════════╕
│n                                                          │
╞═══════════════════════════════════════════════════════════╡
│(:Book {price: 1000,title: "Tinker, Tailor, Soldier, Spy"})│
├───────────────────────────────────────────────────────────┤
│(:Book {price: 2000,title: "Our Man in Havana"})           │
└───────────────────────────────────────────────────────────┘

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

MATCH (n:Book)
WHERE n.price > 1500
RETURN n

╒════════════════════════════════════════════════╕
│n                                               │
╞════════════════════════════════════════════════╡
│(:Book {price: 2000,title: "Our Man in Havana"})│
└────────────────────────────────────────────────┘

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

MATCH (book:Book {title:"Our Man in Havana"}) 
RETURN book

MATCH (book:Book)
WHERE book.title = "Our Man in Havana"
RETURN book

Теперь сделаем выборку тех узлов, которые имеют отношения с книгой Tinker, Tailor, Soldier, Spy:

MATCH (n)-[]->(:Book {title:"Tinker, Tailor, Soldier, Spy"})
RETURN n

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

╒════════════════════════════════════════╕
│n                                       │
╞════════════════════════════════════════╡
│(:Person:Author {name: "John Le Carre"})│
├────────────────────────────────────────┤
│(:Person {name: "Alan"})                │
├────────────────────────────────────────┤
│(:Person {name: "Ian"})                 │
└────────────────────────────────────────┘

В Cypher есть довольно много встроенных функций. Пример ниже демонстрирует работу функции упаковки значений в список - collect:

MATCH (book:Book)<-[:PURCHASED]-(customer:Person)
RETURN book, collect(customer.name) AS customers

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

╒═══════════════════════════════════════════════════════════╤═══════════════╕
│book                                                       │customers      │
╞═══════════════════════════════════════════════════════════╪═══════════════╡
│(:Book {price: 1000,title: "Tinker, Tailor, Soldier, Spy"})│["Alan", "Ian"]│
├───────────────────────────────────────────────────────────┼───────────────┤
│(:Book {price: 2000,title: "Our Man in Havana"})           │["Ian"]        │
└───────────────────────────────────────────────────────────┴───────────────┘

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

ключевое слово MERGE, которое позволяет создавать узлы и отношения при их отсутствии или обновлять при их наличии;
работа с подзапросами и ключевое слово WITH;
поиск путей в графе по произвольному или строго заданному количеству связей определенного или неопределенного типа (например можно проверять связана ли сущность с другой через 6 отношений типа FRIEND или COLLEAGUE);
использование библиотек, которые расширяют функционал Cypher.

Neo4j Browser

Если после прочитанного, вы заинтересовались Neo4j и хотите продолжить изучение, то можете самостоятельно развернуть СУБД с помощью Docker одной командой:

docker run 
 --publish=7474:7474 --publish=7687:7687 
 --volume=$HOME/neo4j/data:/data 
 --env=NEO4J_AUTH=none 
 neo4j

После запуска откройте в веб-браузере урл localhost:7474, по которому будет доступен Neo4j Browser - инструменту для взаимодействия с графами по средствам выполнения Cypher-запросов.

Что дальше?

Если вы хотите освоить Neo4j, то есть официальные бесплатные курсы на GraphAcademy. Могу посоветовать прочитать книгу, с которой я начинал сам, - "Графовые базы данных. Новые возможности для работы со связанными данными" (Ян Робинсон, Джим Вебер, Эмиль Эифрем).

Для разработки приложений с использованием Neo4j можно использовать официальные библиотеки для разных языков программирования.

Если вы как и я разрабатываете на Python и хотите уменьшить количество сырых запросов без изобретения велосипедов, рекомендую обратить внимание на ORM neomodel (которая на самом деле OGM - Object Graph Mapper). Она довольно сырая и не очень хорошо задокументирована, но если потратить немного времени, то во всем разберетесь.

В случае возникновения вопросов, можете связаться со мной лично в Telegram - profatsky

База по графовой СУБД Neo4j