Графовая база данных что это

Что такое графовая БД?

Графовые базы данных предназначены для хранения взаимосвязей и навигации в них. Взаимосвязи в графовых базах данных являются объектами высшего порядка, в которых заключается основная ценность этих баз данных. В графовых базах данных используются узлы для хранения сущностей данных и ребра для хранения взаимосвязей между сущностями. Ребро всегда имеет начальный узел, конечный узел, тип и направление. Ребра могут описывать взаимосвязи типа «родитель‑потомок», действия, права владения и т. п. Ограничения на количество и тип взаимосвязей, которые может иметь узел, отсутствуют.

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

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

Примеры использования

Выявление мошенничества

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

Сервисы рекомендаций

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

Графовые базы данных на AWS

Amazon Neptune

В основе Amazon Neptune лежит специально созданное высокопроизводительное ядро графовой базы данных, оптимизированное для хранения миллиардов взаимосвязей и выполнения запросов к графу с задержками на уровне миллисекунд. Neptune поддерживает популярные модели графов Property Graph и Resource Description Framework (RDF) консорциума W3C, а также соответствующие языки запросов – Apache TinkerPop Gremlin и SPARQL, что позволяет просто создавать запросы для эффективной навигации по наборам сложносвязанных данных.

В целях обеспечения высокой доступности в сервисе Neptune используются реплики чтения, возможность восстановления на момент времени, постоянное резервное копирование в Amazon S3 и репликация в разных зонах доступности. Сервис Neptune безопасен благодаря поддержке шифрования хранимых данных. Сервис Neptune полностью управляем, поэтому при работе с базами данных больше не требуется заниматься такими административными задачами, как выделение оборудования, установка исправлений ПО, установка и настройка самой базы данных, а также ее резервное копирование.

Источник

Графовые базы данных: хранение связанных данных

Андрей Волков

Системное, сетевое администрирование +DBA. И немного программист!)) Профиль автора.

Графовые базы данных — белые вороны в стае баз данных NoSQL. Причиной раз­работки большинства баз данных NoSQL стала необходимость работать на кластерах, которая привела к агрегатно-ориентированным моделям больших записей с простыми связями. Графовые базы данных появились как решение другой проблемы и поэтому имеют противоположную модель — маленькие записи со сложными связями, как по­казано на рис. 1.

В таком контексте этот граф — не диаграмма, а структура данных с узлами, соеди­ненными ребрами.

Рис. 1. Пример графовой структуры

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

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

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

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

Большую часть времени вы ищете данные, перемещаясь по ребрам сети с запро­сами вроде “назовите мне всех, кто любит Анну и Барбару”. Однако вам необходима
отправная точка, поэтому некоторые узлы могут быть индексированы атрибутом, на­пример идентификатором. Таким образом, вы можете начать с поиска идентификатора (например, найти людей с именами Анна и Барбара), а затем начать перемещение по ребрам. Как видим, графовые базы предназначены для ситуаций, в которых большую часть времени вы перемещаетесь по связям.

Акцент на связях резко отличает графовые базы данных от агрегатно­ориентированных. Это отличие имеет несколько последствий; такие базы данных чаще работают на одном сервере, а не распределены по кластерам. Транзакции ACID долж­ны охватывать несколько узлов и ребер, чтобы обеспечивать согласованность данных. Единственное, что связывает их с агрегатно-ориентированными базами данных, — от­рицание реляционной модели и повышенное внимание специалистов, объясняемое интересом к технологии NoSQL.

Источник

Графовая база данных Neo4j в PHP

В последнее время я все чаще слышу о NoSQL и о графовых базах данных в частности. Но воспользовавшись хабропоиском с удивлением обнаружил, что статей на эту тему не так и много, а по запросу «Neo4j», так вообще 4 результата, где косвенно упоминается это название в тексте статей.

Что такое Neo4j?

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

Как я докатился до этого?

Уже более года я не использовал в своих проектах SQL, с того времени, как попробовал документо-ориентированную СУБД «MongoDB». После MySQL моей радости не было предела, как все просто и удобно можно делать в MongoDB. За год, в нашей студии создания сайтов, переписали тройку CMS, использующих основные фишки Mongo c её документами, и с десяток сайтов работающих на их основе. Всё было хорошо, и я уже начал забывать, что такое писать запросы в полсотни строк на каждое действие с БД и все бы ничего пока на мою голову не свалился проект с кучей отношений, которые ну никак не укладывались в документы. Возвращаться к SQL очень не хотелось, и пару дней я потратил чисто на поиск NoSQL решения, позволяющего делать гибкие связи — на графовые СУБД. И по ряду причин мой выбор остановился на Neo4j, одна из главных причин — это то, что мой движок был написан на PHP, а для неё был написан хороший драйвер «Neo4jPHP», который охватывает почти 100% REST-интерфейса, предоставляющегося сервером Noe4j.

Ближе к делу

Графовые базы данных, в первую очередь, предназначены для решения тех задач, где данные тесно связанные между собой в отношениях, которые могут углубляться в несколько уровней. Например, в реляционных базах данных нам не трудно выполнить запрос: «Дайте мне список всех актеров, которые были в фильме с Кевином Бэконом».

Привел пример с под запросом, вы можете переписать его в голове с использованием «JOIN».

Но предположим, что мы хотим получить имена всех актеров, которые были в кино с кем-то, кто был в кино с Кевином Бэконом. И тут у нас появляется ещё один JOIN. А теперь попробуйте добавить третью степень: «Тот, кто был в кино с кем-то, кто был в кино с кем-то, кто был в фильме с Кевином Бэконом.» Страшно звучит, но задача реальная и с каждой новой связью мы должны добавлять JOIN, а запрос будет становится все более сложным, трудоёмким, все менее производительным.

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

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

Теперь становится очень легко найти путь от Кевина Бэкона до любого другого актера.

Немного кода

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

Теперь нам нужно создать узлы для каждого актёра и фильма. Это аналогично тому, как мы делаем INSERT в традиционных реляционных СУБД:

Каждый узел имеет методы setProperty и getProperty, которые позволяют записывать произвольные данные в узел считывать их. Узел не имеет заданной структуры, это похоже на документы в документо-ориентированных СУБД, правда мы не можем делать вложенные данные и свойство может быть только одим из двух типов: строкой или числом.
На сервер данные отправляются только когда мы вызываем save() и это нужно сделать для каждого узла.

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

Как видите, все отношения называются «IN», но мы можем дать им и любое другое имя, например «ACTED IN». Так же мы можем задать обратное отношение от фильмов к актерам и сформулировать его как фильм «HAS» (имеет) актёра. Пути могут быть найдены не зависимо от того какое направление связи мы создадим, т.е. мы можем использовать любую семантику подходящую по смыслу для конкретной предметной области. В тоже время между узлами могут быть множественные отношения направленные в обе стороны.

Все отношения настроены, и теперь мы готовы найти связь между любым актером в нашей системе и Кевином Бэйконом до любой заданной глубины:

Так же мы можем выбирать не сами узлы, а связи между ними, например:

getRelationships — может вернуть все отношения для узла, необязательно ограничивать его только определенным типом отношения. Так же мы можем получить, только все входящие или исходящие из узла связи.

На этом пока закончу данный пост, и надеюсь он даст некий резонанс к написанию статей на тематику графовых баз данных и neo4j в частности.

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

Источник

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

Mar 15, 2019 · 6 min read

Содержание

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

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

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

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

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

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

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

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

Петля

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

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

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

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

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

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

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

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

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

Мультиграф

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Neo4j

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

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

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

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

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

Вершины графа в Neo4j имеют свой тип, в БД Movie у нас 2 типа вершин:
* Person (name — имя актера, born — год рождения)
* Movie (title — наименование фильма, released — год выхода)

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

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

Cypher

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

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

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

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

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

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

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

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

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

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

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

Выводы

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

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

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

Источник

Введение в графовые базы данных SQL Server 2017

В преддверии старта курса «MS SQL Server Developer» подготовили для вас еще один полезный перевод.

Графовые базы данных — это важная технология для специалистов по базам данных. Я стараюсь следить за инновациями и новыми технологиями в этой области и, после работы с реляционными и NoSQL базами данных, я вижу, что роль графовых баз данных становится все больше. В работе со сложными иерархическими данными малоэффективны не только традиционные базы данных, но и NoSQL. Часто, с увеличением количества уровней связей и размера базы, наблюдается снижение производительности. А с усложнением взаимосвязей увеличивается и количество JOIN.

Конечно, в реляционной модели есть решения для работы с иерархиями (например, с помощью рекурсивных CTE), но это все равно остается обходными путями. При этом, функционал графовых баз данных SQL Server позволяет с легкостью обрабатывать несколько уровней иерархии. Упрощаются как модель данных, так и запросы, а следовательно, увеличивается их эффективность. Значительно сокращается объем кода.

Графовые базы данных — это выразительный язык для представления сложных систем. Эта технология уже довольно широко используется в ИТ-индустрии в таких областях, как социальные сети, антифрод-системы, анализ ИТ-сетей, социальные рекомендации, рекомендации по продуктам и контенту.

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

Графовая модель данных

Граф — это множество вершин (узлов, node) и ребер (взаимосвязей, edge). Вершины представляют сущности, а ребра — связи, в атрибутах которых может содержаться информация.

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

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

В современном мире моделирование взаимосвязей требует все более сложных методик. Для моделирования связей SQL Server 2017 предлагает возможности графовых баз данных. Вершины и ребра графа представляются в виде новых типов таблиц: NODE и EDGE. Для запросов к графу используется новая функция T-SQL под названием MATCH(). Так как этот функционал встроен в SQL Server 2017, то его можно использовать в ваших существующих базах данных без необходимости какой-либо их конвертации.

Польза графовой модели

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

Судя по всему, в будущем многие приложения смогут выиграть от использования графовых баз данных.

Моделирование данных: от реляционной модели к графовой

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

Для этого примера сделаем простую модель данных. Создадим таблицу сотрудников EMP с идентификатором EMPNO и колонкой MGR, указывающей на идентификатор руководителя (менеджера) сотрудника. Вся информация об иерархии хранится в этой таблице и может быть запрошена с помощью колонок EMPNO и MGR.

На следующей диаграмме изображена так же самая модель оргструктуры с четырьмя уровнями вложенности в более привычном виде. Сотрудники — это вершины графа из таблицы EMP. Сущность «сотрудник» связана сама с собою связью «подчиняется» (ReportsTo). В терминах графа, связь — это ребро (EDGE), которое связывает узлы (NODE) сотрудников.

Давайте создадим обычную таблицу EMP и добавим туда значения в соответствии с вышеприведенной диаграммой.

На приведенном ниже рисунке показаны сотрудники:

Теперь давайте посмотрим на представление тех же данных в виде графа. Вершина EMPLOYEE имеет несколько атрибутов и связана сама с собой связью «подчиняется» (EmplReportsTo). EmplReportsTo — это название связи.

В таблице ребер (EDGE) также могут присутствовать атрибуты.

Создадим таблицу узлов EmpNode

Синтаксис создания узла довольно прост: к выражению CREATE TABLE в конец добавляется «AS NODE».

Теперь преобразуем данные из обычной таблицы в графовую. Следующий INSERT вставляет данные из реляционной таблицы EMP.

В таблице узлов в специальной колонке $node_id_* хранится идентификатор узла в виде JSON. В остальных столбцах этой таблицы находятся атрибуты узла.

Создаем ребра (EDGE)

Создание таблицы ребер очень похоже на создание таблицы узлов, за исключением того, что используется ключевое слово «AS EDGE».

Теперь определим связи между сотрудниками, используя столбцы EMPNO и MGR. По диаграмме оргструктуры хорошо видно как написать INSERT.

Таблица ребер по умолчанию состоит из трех столбцов. Первый, $edge_id — идентификатор ребра в виде JSON. Два других ( $from_id и $to_id ) представляют связь между узлами. Кроме того, ребра могут иметь дополнительные свойства. В нашем случае это Deptno.

Системные представления

В системном представлении sys.tables появилось две новые колонки:

Объекты, связанные с графами, располагаются в папке Graph Tables. Иконка таблицы узлов помечена точкой, а таблицы ребер — двумя связанными кругами (что немного похоже на очки).

Выражение MATCH

Выражение MATCH взято из CQL (Cypher Query Language). Это эффективный способ запроса к свойствам графа. CQL начинается с выражения MATCH.

Давайте посмотрим на несколько примеров.

Приведенный ниже запрос отображает сотрудников, которым подчиняется Smith и его менеджер.

Следующий запрос предназначен для поиска сотрудников и менеджеров второго уровня для Smith. Если убрать предложение WHERE, то в результате будут отображаться все сотрудники.

И, наконец, запрос для сотрудников и менеджеров третьего уровня.

Теперь давайте изменим направление, чтобы получить начальников Smith’а.

Заключение

SQL Server 2017 зарекомендовал себя как полноценное корпоративное решение для различных ИТ-задач бизнеса. Первая версия SQL Graph очень многообещающая. Даже несмотря на некоторые ограничения, уже сейчас есть достаточно функционала для изучения возможностей графов.

Функционал SQL Graph полностью интегрирован в SQL Engine. Однако, как уже было сказано, в SQL Server 2017 есть следующие ограничения:

Нет поддержки полиморфизма.

Источник