Эта статья представляет собой практическое введение в графовые базы данных с акцентом на экосистему Groovy. В нем рассматривается поддержка Grails GORM для Neo4j, а также сравнение запросов между языком Neo4j Cypher, SQL и DSL графа Гремлина.
Эта статья первоначально появилась в майском выпуске GroovyMag 2013 года .
Теория графов и терминология
Граф — это способ моделирования связей или отношений между узлами или вершинами. Эти отношения, или ребра, могут быть направлены (орграф в математической терминологии), как показано на рисунке 1. Родительско-дочерние отношения могут образовывать дерево; с дополнительными ассоциациями они образуют сеть.
Рисунок 1: ориентированный граф
Взвешенный график (рисунок 2) имеет вес на каждом ребре. Взвешенные сети могут быть использованы для моделирования дорожных сетей с весами, представляющими расстояния; в сочетании с алгоритмами графа кратчайшего пути, такими как алгоритм Дейкстры, они используются, например, для минимизации расстояния, пройденного грузовыми автомобилями доставки.
Рисунок 2: взвешенный график
На рисунке 3 показан цикл, который является самообращающимся ребром.
Рисунок 3: графическая петля
На рисунке 4 показан график свойств; этот тип графа допускает свойства как на узлах, так и на ребрах.
Рисунок 4: График свойств
Образец графика
Одним из основных примеров, который часто используется в текущем вводном материале, является социальный график, очень похожий на рисунок 4. Вместо этого для первого практического примера мы рассмотрим другой сценарий: отношения между проектом разработки, необходимыми навыками и членами команды. участвуют, как показано на рисунке 5 (проекты обозначены оранжевым, навыки — синим, а сотрудники — зеленым).
Рисунок 5: Пример графика навыков
Что такое графовая база данных?
Графовые базы данных используют графы свойств, где и узлы, и ребра могут иметь свойства. Одним из терминов, которые часто используются для описания баз данных графа, является «безиндексная смежность», означающая, что каждый узел знает местоположение узлов, к которым он подключен, без необходимости выполнять поиск по индексу. На самом деле, это часто является ключевым отличием между графической базой данных и неродным хранилищем.
КОГДА ВЫ ДОЛЖНЫ ИСПОЛЬЗОВАТЬ БАЗУ ДАННЫХ GRAPH?
Теперь многие люди могут прыгнуть на подножку, чтобы использовать «блестящую новую» технологию. Урок, который люди должны извлечь из движения NoSQL, заключается в том, что следует использовать наиболее подходящую технологию хранилища данных. Нефункциональные требования очень важны, так как решение необходимо будет эксплуатировать в производственной среде.
Лучше всего подходит для высокоассоциативных наборов данных, где (частично структурированные) отношения имеют решающее значение для ценности данных. Базы данных графов могут предложить существенные улучшения производительности по сравнению с реляционной моделью для данных этого типа, поскольку ребра могут проходиться в O (1), а не требовать значительного количества операций ввода-вывода для выполнения соединений.
Для практических аспектов статьи мы прежде всего будем использовать Neo4j ( http://neo4j.org ), который описан как ведущая в мире графовая база данных, прежде чем рассматривать некоторые альтернативы.
Весь код доступен на GitHub по адресу https://github.com/rbramley/GroovyMagGraphs.
Использование графической базы данных в приложении Grails
Для первого примера мы рассмотрим модель предметной области, которая включает в себя «базу данных проекта». Начнем с установки плагина на основе GORM для Neo4j ( http://www.grails.org/plugin/neo4j — руководство по плагину доступно по адресу http://springsource.github.io/grails-data-mapping/ neo4j / manual / guide / index.html ):
grails install-plugin neo4j
Затем настройте источник данных для плагина в соответствии с листингом 1, но выберите подходящее местоположение файла данных для вашей системы.
grails {
neo4j {
type = "embedded"
location = "/usr/local/Cellar/neo4j/data"
}
}
Листинг 1: Конфигурация источника данных плагина Neo4j
Мы будем использовать scaffolded контроллеры и представления для скорости, поэтому давайте определим модель домена, соответствующую рисунку 5. Требуемые классы домена — это Skill, показанный в листинге 2, Employee, показанный в листинге 3, и Project согласно листингу 4 — все они сообщают GORM, что они для Neo4j с помощью static mapWith = "neo4j".
package neo
import groovy.transform.ToString
@ToString(includes='name')
class Skill {
String name
static constraints = {}
static mapWith = "neo4j"
}
Листинг 2: простое представление Skill
package neo
import groovy.transform.ToString
@ToString(includes='name')
class Employee {
String name
String title
Date dob
static hasMany = [ workedOn : Project, knows : Skill ]
static constraints = {}
static mapWith = "neo4j"
}
Листинг 3: простое представление Employee
package neo
import groovy.transform.ToString
@ToString(includes='projectName')
class Project {
String customerName
String projectName
Date startDate
Date endDate
static hasMany = [ members : Employee, requiredSkills : Skill ]
static constraints = {}
static belongsTo = Employee
static mapWith = "neo4j"
}
Листинг 4: простое представление Project
Таким образом, очень просто создать простую модель предметной области Grails с отношениями «один ко многим» и «многие ко многим» и сопоставить их с Neo4j.
После этого вам нужно будет создать контроллеры, установить леса, запустить и заполнить данные. Рисунок 6 иллюстрирует вид графика рисунка 5, как видно из действия просмотра проекта — работа выполнена!
Рисунок 6: представление приложения графика на рисунке 5
Простая база данных проекта имела такой успех, что HR хотят расширить ее, чтобы предоставить Матрицу навыков. Это новое требование потребует более богатой модели предметной области для сбора более подробной информации об уровнях квалификации и опыте сотрудников; в мире реляционных баз данных мы можем с радостью дополнить таблицу связей «многие ко многим» между Employee и Skill — с помощью графа свойств мы можем добавить свойства к ребру.
Именно здесь мы достигли ограничений плагина GORM, который разработан для 80% случаев использования (см. Http://stackoverflow.com/questions/10647834/architecting-a-neo4j-based-application-stick-to- vanilla-api-using-plain-node ).
Таким образом, похоже, что лучший способ использовать Neo4j для использования возможностей графа с Grails — отказаться от GORM / scaffolding. Что не так уж важно для «реальных» проектов, в отличие от прототипирования.
Весенние данные на помощь
Если вы не хотите связывать свое приложение напрямую с собственными API хранилища данных, тогда Spring Data — один из вариантов. Spring Data предоставляет набор API доступа к данным с реализациями для ряда технологий NoSQL.
Поддержка Spring Data Neo4j включает @RelationshipEntity аннотации ( http://static.springsource.org/spring-data/data-neo4j/docs/2.0.0.RELEASE/reference/html/#d0e1889 ) для добавления свойств к краям графа.
Шесть градусов Кевина Бэкона
Neo4j & Cypher
Neo4j также предоставляет собственный API обхода и декларативный язык запросов под названием Cypher.
В этом примере мы будем манипулировать графиком с помощью скрипта Groovy и играть в игру «6 градусов Кевина Бэкона» ( http://en.wikipedia.org/wiki/Six_Degrees_of_Kevin_Bacon ) с небольшой сетью.
Определенная нами сеть проиллюстрирована на рисунке 7, синие оттенки обозначают фильмы, а зеленые — актеров, за исключением Кевина Бэкона, который обозначен оранжевым цветом. Более темные оттенки являются соединениями первой степени, а более светлые оттенки являются соединениями второй степени.
Рисунок 7: Небольшой график Кевина Бэкона
Сценарий вкусности
Groovy отсутствует метод мета-программирования в листинге 5, чтобы сделать установление отношений более естественным, например movie.featured(actor). Это использует исходящий край из узла фильма в узел актера.
// an enum helper
enum MyRelationshipTypes implements RelationshipType { featured }
// metaclass magic
Node.metaClass {
propertyMissing { String name, val -> delegate.setProperty(name, val) }
propertyMissing { String name -> delegate.getProperty(name) }
methodMissing { String name, args -> delegate.createRelationshipTo(args[0], MyRelationshipTypes."$name") }
}
Листинг 5: Groovy DSL метапрограммирование
Кроме того, в листинге 6 определяется вспомогательный метод, так что мы можем указать график, используя список простых троек (например, «Footloose-FEATURED-Kevin Bacon»), вместо того, чтобы писать множество шаблонного кода для создания каждого узла и определения ребер.
Альтернативой может быть использование нотации GEOFF, которая тесно связана с синтаксисом запроса Neo4j Cypher (более подробная информация позже) — однако для этого требуется дополнительный плагин.
// keep the graph creation DRY
def getOrCreateNode(db, map, key, type) {
def node
if(map.containsKey(key)) {
node = map.get(key)
} else {
node = db.createNode()
node.name = key
node.type = type
map.put(key, node)
}
node
}
// helper method to create the graph
void createGraph(db, gd) {
def movieMap = [:]
def actorMap = [:]
gd.each { str ->
def movie, actor
def parts = str.split('-')
def movieKey = parts[0]
def actorKey = parts[2]
movie = getOrCreateNode(db, movieMap, movieKey, 'Movie')
actor = getOrCreateNode(db, actorMap, actorKey, 'Actor')
// set up the edge
movie.featured(actor)
}
}
Листинг 6: Код построения графа
Настройка Neo4j
В листинге 7 показано, что сценарий использует непостоянную базу данных из модуля утилит тестирования Neo4j, чтобы упростить повторное выполнение, а не приводить в порядок каталог данных, используемый встроенным экземпляром. Это также требует индекса Lucene для узлов, чтобы мы могли искать по имени.
// Set up an impermanent test instance (this saves having to write disk clean up)
def db = new ImpermanentGraphDatabase([:], [new LuceneIndexProvider()], [], [new SoftCacheProvider()])
def nodeAutoIndexer = db.index().getNodeAutoIndexer()
nodeAutoIndexer.startAutoIndexingProperty("name")
nodeAutoIndexer.setEnabled(true)
Листинг 7: Настройка графической базы данных Neo4j
Популяция данных
С помощью вспомогательных методов из листинга 6 и данных из листинга 8 это делает создание узла главным образом демаркацией транзакции, как показано в листинге 9.
// Describe a graph as triples e.g. Movie-FEATURED-Actor
def graphDescription = [
'Footloose-FEATURED-Kevin Bacon',
'Footloose-FEATURED-John Lithgow',
'Shrek-FEATURED-Mike Myers',
'Shrek-FEATURED-John Lithgow',
'Shrek-FEATURED-Cameron Diaz',
"Charlie's Angels-FEATURED-Cameron Diaz",
"Charlie's Angels-FEATURED-Bill Murray",
'54-FEATURED-Mike Myers',
'54-FEATURED-Neve Campbell',
'Wild Things-FEATURED-Neve Campbell',
'Wild Things-FEATURED-Bill Murray',
'Wild Things-FEATURED-Kevin Bacon'
]
Листинг 8: представление графика на рисунке 7
def tx
try {
tx = db.beginTx()
db.index().forNodes("node_auto_index")
// create the nodes for the fixture data
createGraph(db, graphDescription)
tx.success()
} finally {
tx?.finish()
}
Листинг 9: Транзакция для создания индекса и графика
зашифровывать
Cypher — это декларативный язык запросов, и для получения дополнительной информации я бы порекомендовал очень хорошее справочное руководство, которое предоставляет исполняемые образцы, сгенерированные из тестов: http://docs.neo4j.org/chunked/stable/cypher-query-lang.html
Теперь все на месте, и мы заполнили данные, пришло время выполнить запрос в листинге 10, чтобы обнаружить соединения второй степени на графике и маршруты к ним, как это видно на рисунке 8. Мы сообщаем Cypher о начале узел, чтобы найти в индексе, затем, как сопоставить выходные данные, используя 4 прыжка (Movie-Actor-Movie-Actor) и какие свойства данных для вывода.
def query = '''
start k=node:node_auto_index(name = "Kevin Bacon")
match (k)--(m)--(a)--(n)--(b)
return k.name, m.name, a.name, n.name, b.name
'''
// execute the query
ExecutionEngine engine = new ExecutionEngine(db)
ExecutionResult result = engine.execute(query)
println result
Листинг 10: Построение и выполнение запроса Cypher
Рисунок 8: Результаты Cypher toString
Самая медленная часть запроса из листинга 10 — это поиск по индексу, чтобы найти начальную точку для обхода. Это можно было бы легко оптимизировать, если бы вариант использования всегда начинался с Кевина Бэкона, поскольку мы могли бы сделать его корневым узлом графа. Добавление направлений отношений (например match (k)<--(m)-->(a)<--(n)-->(b)) также полезно.
Альтернативный, но менее желательный подход заключается в использовании идентификатора узла, но это не очень хорошая практика, поскольку идентификатор является внутренним идентификатором, и вы должны знать, что идентификаторы узлов повторно используются в Neo4j.
Поиск по индексу в моих тестах с небольшим набором данных добавил ~ 4 мс по сравнению с eg start k=node(1).
Альтернативный способ задать запрос 2-й степени (который в нашем случае равен 4 прыжкам, потому что фильмы моделируются как узлы) показан в листинге 11. Этот запрос проще для написания и допускает прыжки переменной длины (согласно листингу 12 для 1-го и Актеры 2-й степени с упорядоченным выводом на рисунке 9), но требуют дополнительной работы, чтобы понять связь фильмов и актеров.
start k=node:node_auto_index(name = "Kevin Bacon")
MATCH p = (k)-[:featured*4..4]-(x)
RETURN p, x.name
Листинг 11: Сопоставить ребра переменной длины с количеством переходов
start k=node:node_auto_index(name = "Kevin Bacon")
MATCH p = (k)-[:featured*2..4]-(x)
WHERE x.type = 'Actor'
RETURN p, x.name
ORDER BY x.name
Листинг 12: Где пункт и порядок по
Рисунок 9: Результаты с траекторией на графике
Сравнение с SQL
Запрос Cypher-графа в листинге 10 значительно проще указать в Cypher, что его эквивалент SQL-запроса. В реляционной базе данных необходимая нормализованная структура таблицы, как показано на рисунке 10, вводит таблицу ссылок, чтобы разбить отношения «многие ко многим» между фильмами и актерами на две отдельные связи «один ко многим». то есть в фильме может быть много актеров, а актер может появляться во многих фильмах. Следовательно, эквивалентный SQL-запрос требует много дополнительных конструкций, как подробно описано в листинге 13, и исключения необходимы для предотвращения появления в результатах соединений Кевина Бэкона и соединений первой степени, как показано на рисунке 11, как соединений второй степени.
Рисунок 10: Диаграмма отношений сущностей
Полный DDL и DML для этого примера доступны в репозитории GitHub, протестированном с использованием MySQL.
select k.actor_name, m.movie_name, a.actor_name, n.movie_name, b.actor_name
from
actor k, actor a, actor b,
movie m, movie n,
movie_actor mk, movie_actor ma, movie_actor na, movie_actor nb
where
k.actor_name = 'Kevin Bacon'
and k.actor_id = mk.actor_id
and mk.movie_id = m.movie_id
and ma.movie_id = m.movie_id
and ma.actor_id = a.actor_id
and na.actor_id = a.actor_id
and na.movie_id = n.movie_id
and nb.movie_id = n.movie_id
and nb.actor_id = b.actor_id
and k.actor_id <> a.actor_id
and k.actor_id <> b.actor_id
and a.actor_id <> b.actor_id
and m.movie_id <> n.movie_id;
Листинг 13: SQL-запрос для получения соединений второй степени
Рисунок 11: Набор результатов
Время отклика неоптимизированного SQL-запроса в этом случае не так уж и плохо (план объяснения показан на рисунке 12), но у нас есть только минимальный набор данных — если вы действительно хотите попробовать это в масштабе и при 6 градусах Вы можете получить доступ ко всем наборам данных об актерах и актрисах IMDB с http://www.imdb.com/interfaces , хотя данные должны быть предварительно обработаны, чтобы получить их в загружаемую форму для реляционных или графических баз данных.
Рисунок 12: План объяснения MySQL
Другие сферы интересов
Neo4j обработчики событий
Пакет org.neo4j.graphDB.event определяет TransactionEventHandler<T>интерфейс, который можно использовать для запуска пользовательского поведения до или после фиксации, а также после отката. Это выходит за рамки данной статьи.
гремлин
Tinkerpop ( http://www.tinkerpop.com ) предоставляет набор графических проектов с открытым исходным кодом; Blueprints — это интерфейс модели графа свойств с предоставленными реализациями. Базы данных, которые реализуют интерфейсы Blueprints, автоматически поддерживают приложения с поддержкой Blueprints.
Tinkerpop также создал Gremlin ( https://github.com/tinkerpop/gremlin/wiki ), который является языком, специфичным для домена (см. Http://gremlindocs.com ) для обхода графиков свойств.
Gremlin предоставляет интерактивную оболочку, которая использует оболочку Groovy и которую мы сейчас будем использовать в качестве примера.
ПРИМЕР ГРЕМЛИНА
Данные для этого примера доступны в сопутствующем репозитории GitHub и представляют собой графическое представление графика на рисунке 7, поскольку это один из стандартных форматов, поддерживаемых Gremlin. Для этого примера я использовал Titan версии 0.2.0 (немного больше информации о Titan в следующем разделе).
В листинге 14 показан интерактивный примерный эквивалент запроса Cypher в листинге 10.
titan-0.2.0$ bin/gremlin.sh
\,,,/
(o o)
-----oOOo-(_)-oOOo-----
gremlin>g = TitanFactory.open('/tmp/titan')
==>titangraph[local:/tmp/titan]
gremlin>g.createKeyIndex('name', Vertex.class)
==>null
gremlin> g.loadGraphML('data/bacon_oracle.xml')
==>null
gremlin> kevin = g.V('name','Kevin Bacon').next()
==>v[4]
gremlin> kevin.map()
==>name=Kevin Bacon
==>type=Actor
gremlin> kevin.in('featured').map
==>{name=Footloose, type=Movie}
==>{name=Wild Things, type=Movie}
gremlin> kevin.in('featured').out('featured').except([kevin]).name
==>John Lithgow
==>Bill Murray
==>Neve Campbell
gremlin> kevin.in('featured').out('featured').dedup()
==>v[4]
==>v[12]
==>v[32]
==>v[40]
gremlin> kevin.in('featured').out('featured').in('featured').out('featured').except([g.v(4), g.v(12), g.v(32), g.v(40)]).dedup().name
==>Mike Myers
==>Cameron Diaz
Листинг 14: интерактивный сеанс Gremlin
Альтернативные магазины графиков
TITAN
Аврелий Титан ( http://thinkaurelius.github.io/titan/ ) предоставляет выбор постоянных бэкэндов, включая Cassandra и HBase. Он обеспечивает поддержку поиска с использованием ElasticSearch или Lucene. Titan использует Gremlin, а примеры начала работы используют оболочку Groovy Gremlin.
ORIENTDB
OrientDB ( http://www.orientdb.org ) предоставляет базу данных Graph + Document с полнотекстовыми индексами.
RDF, Тройки / Квадраты и SPARQL
RDF ( http://www.w3.org/TR/2004/REC-rdf-primer-20040210/ ) и SPARQL ( http://www.w3.org/TR/rdf-sparql-query/ ) являются двумя семантическими Веб-стандарты от W3C (World Wide Web Consortium).
RDF (Resource Descriptor Framework) предоставляет механизм для описания ресурса, и существуют соответствующие стандарты, такие как RDF / a для встраивания атрибутов метаданных в документ.
RDF Triple ( http://www.w3.org/TR/rdf-concepts/#section-triples ) ссылается на структуру данных Subject -Predicate-> Object, используемую для обозначения, например, того, что Алиса знает Боба. Квадрат расширяет это дополнительным контекстом, также известным как именованный граф, который можно использовать для поднабора большого графа.
SPARQL, протокол SPARQL и язык запросов RDF, предоставляет механизм для запроса многих ресурсов RDF, обычно хранящихся в Triple / Quad Store.
Проект OpenRDF создал интерфейс под названием RDF SAIL (Storage and Inference Layer) — интерфейс графа свойств Blueprints от Tinkerpop позволяет использовать GraphSail поверх графовых баз данных, таких как Neo4j, OrientDB и Titan.
Зрительные
Это довольно большая область и горячая тема, для пользователей Neo4j доступен плагин GraphViz, а следующая страница является хорошей отправной точкой http://www.neo4j.org/develop/visualize.
Примечание: инструмент визуализации Gephi был протестирован с Neo4j 1.5, мне не повезло с базой данных 1.7.2.
Дальнейшее чтение
Предстоящая книга О’Рейли «Графические базы данных» ( http://graphdatabases.com ) углубленно изучает эту тему с упором на Neo4j.
кредиты
Листинг 5 взят из работы Пола Кинга ( https://twitter.com/paulk_asert ), опубликованной в открытом доступе по адресу http://groovyconsole.appspot.com/script/245001 .