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

Яблоко :висит_в пустота.

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

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

Короче, как вы уже поняли — я запал на графы.

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

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

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

Вышеприведенный факт стоит иметь в виду. Если вы эксперт и имеете солидный опыт в этом вопросе — скорее всего, мой пост не вызовет у вас удовлетворения. Ну, а если вы такой же искатель приключений, как и я, готовый мириться с допущениями и голой теорией — добро пожаловать на палубу нашего корабля 🏴‍☠️.

Как можно понять, что вашему приложению возможно нужна графовая база данных?

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

Граф состоит из двух частей (далее я буду использовать англоязычную терминологию т.к. я незнаком с русскоязычной): vertices (nodes, entities) и edges(relationships, arcs). В русском языке я сталкивался с тем, что их называют вершины и грани.

Чтобы представить граф и понять, что вы ими пользовались всю жизнь (но, возможно, не осознавали этого), предлагаю взглянуть на примеры:

• Социальный граф — vertices это люди, а edges обозначают как люди знакомы между собой.

• Веб граф — vertices это веб-страницы, а edges обозначают то, как страницы ссылаются друг на друга.

• Сеть железных дорог — vertices это пункты остановки, а edges обозначают пути, ведущие от одних остановок к другим.

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

Пример, о котором мы все знаем — Facebook. В графе Facebook вершинами графа выступают люди, места, события, чек-ины, комментарии; гранями обозначается кто для кого друг, в какой локации происходит чек-ин, кто прокомментировал чей пост, и так далее.

Характеристики графов

Каждая нода(вершина) графа состоит из:

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

Каждая грань имеет:

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

Важные моменты, которые стоит учесть при работе с графами:

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

Query Languages для графовых баз данных

Cypher

Cypher — декларативный язык запросов, созданный для того, чтобы работать с Neo4j.

Его синтаксис напоминает SQL.

CREATE
	(Kyiv:Location {name:'Kyiv', type: 'city'}),
	(Troy:Person {name:'Troy'}),
	(Troy) -[:WITHIN]-> (Kyiv)

На сайте Neo4j есть интересный туториал о том, как с помощью Cypher построить рекомендательную систему для онлайн-кинотеатра.

С помощью Cypher можно легко отвечать на очень интересные вопросы достаточно легко (при условии наличии данных). Например, на вопрос "сколько людей эмигрировало из Украины в Европу?" было бы довольно сложно ответить, используя стандартную реляционную базу данных, но с помощью Neo4j и Cypher это делается намного легче.

SPARQL; triple-stores

В triple-store информация хранится в форме утверждения из трех частей: subject (отвечает на вопросы "кто? что?"), predicate (отвечает на вопрос "что делает?"), object (отвечает на вопрос "кого? чего?").

Например: (Troy, writes, post) → Troy это subject, writes выступает в роли predicate и post это object.

Subject — это эквивалент вершины (ноды) в графе.

Object может быть либо характеристикой, либо другой вершиной.

Например, (Troy, age, 23) — это как вершина Troy с аттрибутами { age: 23 }, или (Lucy, marriedTo, Alain) — subject и object являются вершинами, а marriedTo это подпись к грани, которая их соединяет.

На triple-store синтаксисе базируется RDF — Resource Description Framework, который был создан для того, чтобы сделать нечто под названием semantic web.

Что это такое, я, если честно, разбираться не стал.

SPARQL был изобретен до Cypher и базируется на RDF, и Cypher во многом вдохновлялся этим языком.

SELECT ?personName WHERE {
	?person :name ?personName.
  ?person :bornIn / :within* / :name "Ukraine".
  ?person :livesIn / :within* / :name "Europe".
}

Так как SPARQL базируется на triple-store синтаксисе с помощью него можно создавать запросы, которые фильтруют и по граням, и по аттрибутам.

Datalog

Datalog — очень старый декларативный логический язык запросов, активно использовался в восьмидесятые года прошлого века, наследник Prolog. На основании него сделаны Datomic и Cascalog, которые (вроде как) используются для запросов в Hadoop.

Моделирование данных в Datalog работает по такому же принципу, как в triple-store. Есть одно небольшое различие: тройка записывается не вот так — (subject, predicate, object), а вот так — predicate(subject, object).

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

Вот как выглядит синтаксис наследника Datalog — Datomic. Довольно похоже синтаксически на то, что мы видели выше.

;; query
[:find ?e
 :where [?e :artist/name "The Beatles"]]

;; query
[:find ?name ?duration
 :where [?e :artist/name "The Beatles"]
        [?track :track/artists ?e]
        [?track :track/name ?name]
        [?track :track/duration ?duration]]

Graceful shutdown

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

Хочу верить, что пост был вам полезен или хотя бы вам было весело его читать 🙂

Если вы нашли ошибку в тексте или коде, хотите предложить правки или оставить комментарии, я предлагаю открыть issue в репозитории этого блога или сделать PR с правкой в этот материал. Еще вы можете написать мне на почту — kohler.messages[собака]gmail.com

За исходный материал и превосходную подачу на английском спасибо Мартину Клеппманну. Если вы знаете английский, читайте его блог и его офигенскую книгу Designing Data-Intensive Applications.

Peace ✌️