Skip to content

Latest commit

 

History

History
246 lines (126 loc) · 14 KB

neo4j_and_graphs.md

File metadata and controls

246 lines (126 loc) · 14 KB
Raw

Знакомство с графовой базой данных Neo4j

＼（＾○＾）人（＾○＾）／

Содержание

  • История происхождения графов

  • Что такое граф?

  • Классификация графов

  • Где используются графы

  • Графовые Базы

  • СУБД Neo4j

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

  • Где и когда использовать графовые СУБД

  • Выводы

История происхождения графов

Среди жителей Кёнигсберга (нынешний Калиниград) была распространена такая загадка: как пройти по всем городским мостам через реку, не проходя ни по одному из них дважды. Многие пытались решить эту задачу как теоретически, так и практически, во время прогулок. Впрочем, доказать или опровергнуть возможность существования такого маршрута никто не мог.

Решил задачку Леонард Эйлер, сформулировав ряд правил и доказав, что пройти по мостам, не повторяясь, невозможно.

Так и зародилась теория графов.

Что такое граф?

Граф — абстрактный математический объект, представляющий собой множество вершин (точек) и набор рёбер (линий), то есть соединений между парами вершин.

Ориентированный граф

Ориентированный граф — это граф, ребро которого имеет заданное направление между вершинами.

Петля

Если вершина графа соединена ребром сама с собой, то такое ребро называется петлей.

Классификация графов

Связанный граф

Если из любой вершины есть путь до любой другой — такой граф называется связанным.

В данном примере есть путь от вершины А до вершины D, хоть он и пролегает через другие вершины.

Сильно связанный граф

Граф называется сильно связанным, если любая его вершина соединена с любой другой ребром. Если связи ориентированные — то граф называется ориентированно связанным.

Взвешенный граф

Если к каждому ребру в соответствие поставлено некоторое число (вес ребра) — такой граф называется взвешенным.

Мультиграф

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

Где используются графы

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

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

По весам ребер можно посчитать время в пути, так же и выбрать оптимальный путь с помощью какого-либо алгоритма. Алгоритмов поиска кратчайшего пути в графе много, самый известный — алгоритм Дейкстры, вы наверняка о нем слышали.

Карту города тоже можно представить в виде графа.

Данный граф применим в системах навигации для поиска оптимального маршрута. Перекрестки — вершины графа, а дороги — ребра.

Молекулярный граф — связный неориентированный граф, соответсвует формуле химического соединения таким образом, что вершины графа — атомы молекулы, а ребра — химические связи между этими атомами.

H2SO4 — Серная кислота H2SO4 — Серная кислота

Социальный граф

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

Даже 3D-объект можно представить в виде графа:

Каждая вершина хранит координаты x, y, z.

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

Графовые базы

Первая графовая СУБД Neo4j создана в 2007 году, сейчас их уже десятки, наиболее популярные:

  • ArangoDB (мультимодельная)

  • HyperGraphDB (использует модель мультиграфа)

  • Neo4j (использует модель ориентированного графа)

  • OrientDB (позиционируется как «мультимодельная СУБД»)

Neo4j

Графовая СУБД с открытым исходным кодом, реализована на Java компанией Neo Technology.

Не уступает по производительности реляционным базам данных благодаря собственному формату хранения данных.

Приложение может взаимодействовать с БД по одному из протоколов:

  • HTTP

  • HTTPS

  • BOLT (Собственный протокол Neo Technology)

Продолжим знакомство с Neo4j на примере стандартной БД “Movie”

Пользователь может просматривать БД с помощью Neo4j Browser

Отображение графовой БД “MOVIE” в Neo4j Browser Отображение графовой БД “MOVIE” в Neo4j Browser

Вершины графа в Neo4j имеют свой тип, в БД Movie у нас 2 типа вершин:

  • Person (name — имя актера, born — год рождения)
  • Movie (title — наименование фильма, released — год выхода)

Если проводить аналогию с реляционными базами, то Person и Movie — это таблицы.

Для работы с БД используется язык запросов Cypher.

Cypher

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

Для начала найдем актера с именем Том Хэнкс

Ищем Тома Ищем Тома

MATCH - аналог WHERE, в круглых скобках мы описываем свойства вершины (условие поиска), а RETURN — аналог SELECT, в нем мы описываем, что вернуть.

А вот и он А вот и он

Теперь поищем фильмы, в которых снимался Том Хэнкс.

Запрос усложнился, в MATCH мы описали вершины обоих типов, и отношение между ними (ребро) в квадратных скобках.

Cypher запросCypher запрос

Результат в виде графаРезультат в виде графа

Теперь посмотрим, кто снимался с Томом на одной площадке, и в каком фильме:

![Cypher запрос](/images/neo4j_and_graphs:cypher_query_2.png Cypher запрос

Результат в виде таблицы Результат в виде таблицы

Текст запроса приближен к текстовому отображению графа:

От вершины типа Person с именем Tom Hanks по ребру ACTED_IN находятся все вершины Movie, в которых снимался актер, от вершин типаMovie по связи ACTED_IN идет поиск всех актеров, снявшихся в каждом найденном фильме соответственно.

Где и когда использовать графовые СУБД

Графовые базы уже нашли применение в:

  • Социальных сетях

  • Системах рекомендаций (с этим товаром часто покупают…)

  • Обработка пользовательских данных, корреляция данных из разных источников (информационный след в сети)

Если в вашем приложении планируется много сущностей и связей многие-ко-многим, то это один из признаков, что предпочтительней выбрать графовую СУБД (утверждение Martin Kleppmann’а в книге “Designing Data Intensive Applications”)

А если у вас уже есть приложение с множеством связей, и обход этих связей занимает много времени и ресурсов — стоит присмотреться в сторону графов, т.к. обход связей в них практически ничего не стоит.

Выводы

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

Например, площадка medium использует Neo4j для хранения отношений между различными сущностями (Стек, который позволил Medium обеспечить чтение на 2.6 тысячелетия), а данные хранит в NoSQL БД dynamoDB.

Преимущества:

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

  • Простой язык запросов и наглядный результат, поэтому может использоваться аналитиками;

  • Гибкая структура данных, проще вносить изменения в случае изменения требований;

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

Недостатки:

  • БД занимает заметно больше места на диске, по отношению к реляционным СУБД;

  • На простых запросах производительность ниже, чем в реляционных базах;

  • Необходимо обучать разработчиков.

P.S.

Если вас заинтересовали графовые базы, то на официальном сайте Neo4j можно скачать БЕСПЛАТНО книгу с осьминогом, в ней больше информации про внутреннее устройство Neo4j и Cypher.