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

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

Новые возможНости  
для работы со связаННыми даННыми

Второе издание

Ян Робинсон, Джим Вебер, Эмиль Эифрем

Graph Databases

NEW OPPORTUNITIES FOR CONNECTED DATA

Second Edition

Ian Robinson, Jim Webber & Emil Eifrem

Beijing · Cambridge · Farnham · Ko..ln · Sebastopol · Tokyo

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

Новые возможНости для работы  
со связаННыми даННыми

Второе издание

Ян Робинсон, Джим Вебер, Эмиль Эифрем

Москва, 2016

УДК 004.6
ББК 32.972
 
Р58

 
 
Робинсон Ян, Вебер Джим, Эифрем Эмиль

Р58 
Графовые базы данных: новые возможности для работы со
связанными данными / пер. с англ. Р. Н. Рагимова; науч. ред.
А. Н. Кисилев. – 2-е изд. – М.: ДМК Пресс, 2016. – 256 с.: ил.

ISBN 978-5-97060-201-0

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

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

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

 
УДК 004.6 
 
ББК 32.972

Authorized Russian translation of the English edition of Graph Databases, 2nd

Edition. This translation is published and sold by permission of O’Reilly Media, Inc.,
which owns or controls all rights to publish and sell the same.

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

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

ISBN 978-1-491-93089-2 (анг.) © 2015 Neo Technology, Inc.
ISBN 978-5-97060-201-0 (рус.) © Оформление, перевод, ДМК Пресс, 2016

содержание

Пролог.....................................................................10

Предисловие............................................................13

Глава.1..Введение......................................................17
Что такое граф? ...................................................................................................17
Обзор областей применения графов ............................................................19
Графовые базы данных .................................................................................20
Механизмы вычисления графов ...............................................................22
Преимущества графовых баз данных ..........................................................23
Производительность .....................................................................................24
Гибкость .............................................................................................................24
Оперативность ................................................................................................25
Итоги .......................................................................................................................25

Глава.2..Варианты.хранения.взаимосвязанных..
данных.....................................................................26
Недостатки NOSQL-баз данных при работе со взаимосвязями.........30
Взаимосвязи в графовых базах данных .......................................................35
Итоги .......................................................................................................................41

Глава.3..Моделирование.данных.графами.....................42
Модели и задачи ..................................................................................................42
Графовая модель со свойствами и метками ...............................................43
Графовые запросы: введение в Cypher .........................................................44
Философия языка Cypher ...........................................................................45
MATCH .............................................................................................................47
RETURN ...........................................................................................................48
Другие фразы языка Cypher .......................................................................48
Сравнение реляционного и графового моделирования ........................49
Реляционная модель системы управления ...........................................51
Графовое моделирование системы управления ..................................56
Тестирование модели ....................................................................................58
Кросс-модели нескольких прикладных областей ...................................60
Создание графа творчества Шекспира ...................................................64

 Содержание

Введение в запросы .......................................................................................66
Определение шаблонов для поиска .........................................................68
Ограничение совпадений ............................................................................70
Обработка результатов .................................................................................71
Цепочки в запросах .......................................................................................72
Распространенные просчеты при моделировании ..................................73
Проблемы анализа источников электронных писем .........................73
Первый блин комом? ....................................................................................73
Со второго раза все получится ..................................................................76
Эволюция прикладной области ................................................................79
Идентификация узлов и взаимосвязей .......................................................85
Как избежать антишаблонов ...........................................................................85
Итоги .......................................................................................................................86

Глава.4..Разработка.приложений.графовых.баз.данных....88
Моделирование данных ....................................................................................88
Описание модели с учетом потребностей приложения....................89
Узлы представляют сущности, взаимосвязи формируют  
структуру ..........................................................................................................90
Подробные имена или свойства взаимосвязей ....................................91
Моделирование фактов в виде узлов ......................................................92
Работа .......................................................................................................92
Исполнение ролей ...............................................................................92
Электронная переписка .....................................................................94
Рецензии ..................................................................................................94
Представление комплексных типовых значений в виде узлов ......94
Время ..................................................................................................................95
Хронологическое древо ......................................................................95
Связанные списки ................................................................................97
Управление версиями .........................................................................98
Итеративная и поэтапная разработка .....................................................98
Архитектура приложений ............................................................................. 100
Встроенная поддержка или сервер ....................................................... 100
Встроенная поддержка Neo4j ........................................................ 100
Серверный режим ............................................................................. 102
Серверные расширения .................................................................. 103
Кластеризация ............................................................................................. 106
Репликация ......................................................................................... 106
Запись буфера с помощью очередей .......................................... 107

Содержание  7

Глобальные кластеры ....................................................................... 107
Балансировка нагрузки ............................................................................. 107
Отделение трафика чтения от трафика записи ...................... 107
Распределительный кэш ................................................................. 109
Чтение собственных записей ........................................................ 110
Тестирование ..................................................................................................... 111
Разработка модели данных, основанная на тестировании ........... 111
Пример: модель данных социальной сети  
и ее тестирование .............................................................................. 112
Тестирование серверных расширений ....................................... 116
Тестирование производительности ...................................................... 118
Тесты производительности запросов ......................................... 119
Тесты производительности приложений .................................. 120
Тестирование с помощью репрезентативных данных .......... 121
Планирование производственных мощностей ...................................... 123
Критерии оптимизации ............................................................................ 124
Производительность .................................................................................. 124
Калькуляция затрат на увеличение  
производительности графовой базы данных ........................... 125
Варианты оптимизации производительности ........................ 125
Избыточность ............................................................................................... 127
Нагрузка ............................................................................................... 127
Импорт и массовая загрузка данных ......................................................... 128
Первоначальный импорт .......................................................................... 128
Пакетный импорт ........................................................................................ 130
Итоги .................................................................................................................... 133

Глава.5..Графы.в.реальном.мире................................134
Почему выбирают графовые базы данных .............................................. 134
Типичные примеры использования ........................................................... 136
Социальные сети ......................................................................................... 136
Рекомендации ............................................................................................... 137
Геоинформационные системы ................................................................ 138
Управление справочными данными ..................................................... 139
Сети и управление центром обработки данных ............................... 139
Авторизация и контроль доступа (для коммуникаций) ............... 141
Реальные примеры .......................................................................................... 142
Социальные рекомендации (Профессиональная  
социальная сеть) .......................................................................................... 142

 Содержание

Модель данных Talent.net  ............................................................. 144
Выявление социальных взаимосвязей ...................................... 145
Поиск коллег с определенными интересами ........................... 149
Добавление взаимосвязей WORKED_WITH ........................ 152
Авторизация и контроль доступа .......................................................... 155
Модель данных компании TeleGraph ......................................... 156
Поиск доступных администратору ресурсов  ......................... 159
Определение доступности ресурса администратору ............ 160
Поиск администраторов по учетной записи ............................ 163
Геоинформационные системы и логистика ....................................... 165
Модель данных Global Post ........................................................... 166
Расчет маршрута ................................................................................ 169
Поиск кратчайшего маршрута с помощью Cypher ................ 172
Реализация расчета маршрутов с помощью  
фреймворка Traversal ....................................................................... 175
Итоги .................................................................................................................... 180

Глава.6..Внутреннее.устройство.графовых.баз.данных.....182
Нативная обработка графов ......................................................................... 182
Нативное хранилище графов ....................................................................... 186
Программные интерфейсы ........................................................................... 192
Программный интерфейс ядра ............................................................... 193
Базовый интерфейс .................................................................................... 193
Фреймворк Traversal .................................................................................. 194
Нефункциональные характеристики ........................................................ 196
Транзакции .................................................................................................... 197
Восстанавливаемость ................................................................................. 199
Доступность .................................................................................................. 200
Масштабирование ....................................................................................... 202
Мощность............................................................................................. 203
Задержки .............................................................................................. 203
Производительность ........................................................................ 204
Итоги .................................................................................................................... 206

Глава.7..Интеллектуальный.анализ.с.помощью..
теории.графов.........................................................207
Поиск в глубину и ширину ........................................................................... 207
Поиск маршрутов с помощью алгоритма Дейкстры ........................... 209
Алгоритм A* ........................................................................................................ 217

Содержание  9

Теория графов и прогнозное моделирование ......................................... 218
Триадические замыкания ......................................................................... 219
Структурный баланс .................................................................................. 221
Локальные перемычки ................................................................................... 226
Итоги .................................................................................................................... 228

Приложение.А..Обзор.NOSQL-баз.данных.....................229
Движение NOSQL ........................................................................................... 229
ACID или BASE ................................................................................................ 231
Секторы NOSQL .............................................................................................. 233
Хранилища документов ................................................................................. 233
Хранилища пар ключ-значение .................................................................. 236
Семейства столбцов ........................................................................................ 239
Запросы или обработка в агрегированных хранилищах .................... 242
Графовые базы данных ................................................................................... 243
Графы со свойствами ................................................................................. 244
Гиперграфы ................................................................................................... 245
Триплеты ........................................................................................................ 246

Предметный.указатель.............................................249

Об.авторах.............................................................254

Заключение............................................................255

Пролог

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

Это было в 1999 году, мы работали по 23 часа в сутки. По крайней 
мере, чувствовали себя именно так. Каждый день приносил очередную новость о сумасшедшей идее, только что получившей финансирование в миллионы долларов. У наших конкурентов были сотни инженеров, а наша команда разработчиков состояла всего из 20 человек. 
Этого было явно недостаточно, причем 10 из наших инженеров большую часть времени проводили в борьбе с реляционной базой данных.
Нам потребовалось время, чтобы выяснить, почему так происходит. После тщательного анализа архитектуры данных, хранимых нашим приложением управления контентом, выяснилось, что программа должна не просто управлять массой отдельных изолированных 
дискретных элементов данных, но и учитывать связи между ними. 
Несмотря на то что наши дискретные данные легко размещались в таблицах реляционной базы данных, с хранением связей между ними 
возникли сложности, а запросы, извлекающие их, выполнялись чрезвычайно медленно.
Просто от отчаяния я вместе с Йоханом и Питером, соучредителями компании Neo, начал экспериментировать с другими моделями представления данных, в частности основанными на графах. Нас 
увлекла идея замены табличной семантической модели данных графо-ориентированной, которая должна была значительно облегчить 
навигацию по связанным данным. Мы поняли, что, вооружившись 
графовой моделью, наша команда перестанет тратить половину своего времени на борьбу с базой данных.
Конечно, мы понимали, что не являемся первопроходцами. Теория 
графов существует уже в течение почти 300 лет, и примеры ее применения в целом ряде разнообразных математических задач широко известны. Естественно, должны быть и базы данных, основанные на графах!
Ну, мы и прочесали с помощью AltaVista1 весь молодой Интернет 
и ничего не нашли. Через несколько месяцев бесплодных поисков мы 

1 Это будет шоком для молодых читателей, но в истории человечества было 
время, когда Google не существовал. В те далекие времена землей правили 
динозавры и поисковые системы AltaVista, Lycos и Excite в основном использовались для поиска электронных порталов, предлагающих через Интернет приобрести корм для домашних животных.

Пролог  11

(смело) приступили к созданию с нуля базы данных, которая изначально предназначалась для работы с графами. В нашем представлении она должна была сохранить все проверенные временем функции 
реляционной базы данных (транзакции, ACID, триггеры и т. д.), но 
при этом использовать модель данных XXI века. Так родился проект 
Neo, а вместе с ним графовые базы данных, в том виде, в котором они 
известны сегодня.
В первом десятилетии нового тысячелетия возникло несколько изменивших мир коммерческих проектов, в том числе Google, Facebook 
и Twitter. Им присуща одна общая особенность: они сделали ставку 
на графовую модель представления взаимосвязей между данными, 
сделав ее основой своего бизнеса. И вот, через 15 лет после появления, графовая модель используется повсеместно.
Facebook, например, базируется на идее, что, несмотря на значимость дискретной информации о людях, их именах, профессиях и т. д., 
еще большую ценность представляют сведения о взаимосвязях между 
ними. Основатель Facebook Марк Цукерберг (Mark Zuckerberg) построил свою империю, основываясь на понимании моделирования 
этих взаимосвязей с помощью социального графа.
Точно так же основатели компании Google – Ларри Пейдж (Larry 
Page) и Сергей Брин (Sergey Brin) – придумали, как хранить и обрабатывать не только отдельные веб-документы, но и как связать их 
между собой. Google создала граф Интернета, что и позволило ей 
стать самой впечатляющей компанией последнего десятилетия.
Сегодня графы успешно используются не только гигантами Интернета. Одна из самых больших в мире логистических компаний использует графовую базу данных для прокладки в режиме реального 
времени маршрутов отправлений, ведущая авиакомпания использует 
графы для управления метаданными медиаконтента, и финансовые 
структуры топ-уровня переводят всю свою инфраструктуру на Neo4j. 
Практически никому не известные несколько лет назад, графовые 
базы данных в настоящее время широко применяются в таких областях, как здравоохранение, розничная торговля, газонефтедобыча, 
средства массовой информации, разработка игр и др., ускоряя развитие каждой из них.
Реализация этих идей потребовала разработки инструментов нового типа, основанных на технологиях управления базами данных, 
учитывающих взаимосвязи между данными и позволяющих мыслить 
категориями графов, а это именно те инструменты, о которых мы мечтали, мучась с реляционной базой данных в 1999 году.

 Пролог

Я надеюсь, что эта книга станет вашим путеводителем по прекрасному развивающемуся миру графовых технологий и вдохновит вас на 
использование графовой базы данных в вашем следующем проекте, 
чтобы вы тоже смогли ощутить необычайную мощь графов.
Удачи!
Эмиль Эифрем (Emil Eifrem),
соучредитель Neo4j и генеральный директор Neo Technology
Менло-Парк, Калифорния
Май 2013 года

Предисловие

Сегодня решения, основанные на графовых базах данных, очень важны для ведения успешного бизнеса: управление, учитывающее сложные и динамичные отношения тесно связанных между собой данных, 
предоставляет преимущество в конкуренции. Везде, где требуется 
учитывать взаимосвязи между клиентами, абонентами телефонного 
центра или сети обработки данных, организаторами представлений 
и зрителями или же генами и белками, способность воспринимать 
и анализировать огромные графы тесно взаимосвязанных данных будет играть определяющую роль для компаний, которые превзойдут 
своих конкурентов в течение следующего десятилетия.
Для данных любого объема и значения графовые базы данных 
являются лучшим способом представления и извлечения взаимосвязанных данных. Взаимосвязи между данными представляют собой данные, описание и оценка которых нужны нам для понимания, 
каким образом связаны между собой составляющие элементы. Для 
достижения такого понимания потребуются идентификация и квалификация взаимосвязей между элементами данных.
Многие крупные корпорации, осознав эту необходимость некоторое время назад, начали создавать собственные запатентованные 
технологии обработки графов, но мы живем в эпоху, когда доступ 
к технологиям становится все более демократичным. Сегодня общедоступные графовые базы данных являются реальностью, позволяя основной массе пользователей испытать преимущества работы 
с взаи мосвязанными данными без необходимости инвестировать 
в разработку собственной графовой инфраструктуры.
Примечательным является возрождение интереса к отображению 
данных посредством графов, притом что теория графов сама по себе 
не нова. Теория графов была впервые описана Эйлером в XVIII веке 
и до сих пор активно исследуется и улучшается математиками, социологами, антропологами и другими специалистами-практиками. Тем 
не менее только в последние несколько лет теория графов и представление с помощью графов стали применяться к управлению информацией. Графовые базы данных помогли решению важных проблем 
в области социальных сетей, управления нормативно-справочной информацией, картографии, экспертных рекомендаций и многих других. 
Такое повышенное внимание к графовым базам данных обусловлено 
двумя факторами: огромным коммерческим успехом таких компаний, 
как Facebook, Google и Twitter, бизнес-модели которых основываются 

 Предисловие

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

о втором издании книги
Первое издание этой книги была написано, когда Neo4j 2.0 находился 
в стадии активного развития и еще не были окончательно закреплены 
формы меток, индексов и ограничений целостности. Сейчас версия 
2.x Neo4j уже просуществовала часть своего жизненного цикла (на 
момент написания книги доступна версия 2.2, и скоро выйдет версия 2.3) и мы уже с уверенностью можем включить в текст книги новые элементы графовой модели.
Для второго издания этой книги мы пересмотрели все примеры на 
языке запросов Cypher, чтобы привести их в соответствие с современным синтаксисом языка. Мы добавили метки для запросов и схем, 
включили пояснения декларативной индексации и дополнительных 
ограничений целостности Cypher. В другом месте мы добавили дополнительные правила моделирования, переработали описание внутренних свойств Neo4j в соответствии с изменениями его внутренней 
архитектуры и обновили тестовые примеры, применив в них новейшие инструменты.

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

соглашения
В этой книге приняты следующие типографские соглашения:

Курсив
Выделение новых терминов, URL-адресов, адресов электронной 
почты, имен файлов и расширений файлов.

Предисловие  15

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

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

 Так обозначаются предупреждения и предостережения.

использование примеров кода

Сопроводительные материалы (примеры кода, упражнения и т. д.) 
можно загрузить со страницы https://github.com/iansrobinson/graphdatabases-use-cases.
Данная книга призвана оказать вам помощь в решении ваших задач. Вы можете свободно использовать примеры программного кода 
из этой книги в своих приложениях и в документации. Вам не нужно 
обращаться в издательство за разрешением, если вы не собираетесь 
воспроизводить существенные части программного кода. Например, 
если вы разрабатываете программу и используете в ней несколько 
отрывков программного кода из книги, вам не нужно обращаться за 
разрешением. Однако в случае продажи или распространения компакт-дисков с примерами из этой книги вам необходимо получить 
разрешение от издательства O’Reilly. Если вы отвечаете на вопросы, 
цитируя данную книгу или примеры из нее, получения разрешения 
не требуется. Но при включении существенных объемов программного кода примеров из этой книги в вашу документацию необходимо 
получить разрешение издательства.
Мы приветствуем, но не требуем добавлять ссылку на первоисточник при цитировании. Под ссылкой на первоисточник мы подразумеваем указание авторов, издательства и ISBN. Например: «Graph 
Databases by Ian Robinson, Jim Webber, and Emil Eifrem (O’Reilly). 
Copyright 2015 Neo Technology, Inc., 978-1-491-93089-2.».