Сила Далеков (и Neo4j)

Запрос данных

Данные пропеллера Dalek охватывают многие важные концепции и взаимосвязи предметной области, описанные в исследовании Dalek 6388 . После того, как мы создали набор данных, я начал задавать ему несколько хитрых вопросов. На вершине моего списка неотложных вопросов был следующий: какая самая трудная часть работы Dalek в шоу-бизнесе? То есть, какое из этих плеч и юбок появилось в большем количестве историй, чем любая другая часть?

Neo4j предлагает несколько разных способов запроса графа. Есть Core API , который позволяет вам иметь дело с узлами и отношениями, и оригинальный Traverser API , который предлагает немного более декларативный маршрут в граф. Для более сложных прохождений существует Traversal Framework , который, будучи более мощным, чем Traversal API, имеет немного более крутой кривой обучения. Для запросов к серверу есть REST API . Далее, Gremlin , мощный язык обхода графов с плагином для Neo4j, и библиотека Pattern Matching , которая похожа на язык регулярных выражений для графов. И, наконец, введенный в последние 1.4 вехи, есть Cypherновый декларативный язык сопоставления с образцом графа — SQL для графов.

В оставшейся части этого поста мы рассмотрим три различных способа выяснить, какая часть работы Dalek была самой трудной. В первом примере мы рассмотрим Traversal Framework. В следующем мы будем использовать библиотеку Pattern Matching. Наконец, мы будем использовать Cypher.

Здесь довольно много кода. Если у вас нет терпения разбираться со всем этим, сделайте только одно: посмотрите на запрос Cypher. Это вещь, похожая на далекскую точность.

Структура обхода

Вот как выглядит запрос для поиска наиболее трудолюбивой части пропуска Dalek с использованием Traversal Framework:

@Test
public void shouldFindTheHardestWorkingPropsUsingTraversalFramework() {
  Node theDaleks = database.index().forNodes("species")
    .get("species", "Dalek").getSingle();

  Traverser traverser = Traversal.description()
    .relationships(Rels.APPEARED_IN, Direction.OUTGOING)
    .relationships(Rels.USED_IN, Direction.INCOMING)
    .relationships(Rels.MEMBER_OF, Direction.INCOMING)
    .relationships(Rels.COMPOSED_OF, Direction.OUTGOING)
    .relationships(Rels.ORIGINAL_PROP, Direction.OUTGOING)
    .depthFirst()
    .evaluator(new Evaluator() {
      @Override
      public Evaluation evaluate(Path path) {
         if (path.lastRelationship() != null && 
            path.lastRelationship().isType(Rels.ORIGINAL_PROP)){
          return Evaluation.INCLUDE_AND_PRUNE;
        }
                        
        return Evaluation.EXCLUDE_AND_CONTINUE;
                        
       }
    })
    .uniqueness(Uniqueness.NONE)
    .traverse(theDaleks);
        
    assertHardestWorkingPropParts(getSortedResults(traverser),
      "Dalek 1 shoulder", 12,
      "Dalek 5 skirt", 12,
      "Dalek 6 shoulder", 12);
}

В этом примере показано идиоматическое использование Neo4j Traversal Framework. Сначала мы ищем начальный узел для обхода в индексе. В данном случае мы ищем узел видов Далеков. Затем мы создаем описание обхода и выполняем обход этого начального узла. Обход сканирует подграф ниже начального узла. С каждым узлом, который он посещает, он вызывает методvaluate для пользовательского оценщика, поставляемого с описанием. Этот метод определяет, расположен ли traverser над интересующим узлом (в данном случае, исходным узлом пропеллера). Если это так, обходчик возвращает путь к этому узлу вызывающему коду, а затем начинает новый обход дальше по поддереву. Если это не интересующий узел, путешественник продолжает углубляться в подграф.

В описании указаны типы отношений, которым мы готовы следовать, и их направление. Каждое отношение в Neo4j имеет метку типа и направление. Направление помогает обеспечить семантическую ясность при работе с асимметричными отношениями между узлами. Хотя отношение между двумя узлами всегда направлено — у него есть начальный узел, направление и конечный узел — можно запрограммировать traverser, чтобы он следовал либо за отношением INCOMING, либо за OUTGOING, и даже полностью игнорировал направление (используя Direction. ОБЕ).

Обратите внимание, что мы указали, что сначала пройдем глубину обхода. Это означает, что из узла видов Далеков он сначала начнет глубинную охоту за оригинальной опорой, следуя первым связям APPEARED_IN с эпизодом, а затем выполняя поиск узлов ниже этого эпизода. Как только он нашел первый подходящий исходный объект, он возвращает путь к объекту к вызывающему коду (INCLUDE_AND_PRUNE), а затем последовательно перемещается обратно по этому пути, пробуя альтернативные ветви, пока не вернется обратно к видовой узел, откуда он пробует следующее отношение APPEARED_IN.

Вот маршрут, по которому путешественник идет от начального узла видов Далеков через все узлы под Силой Далеков :

• (Далек) — [: APPEARED_IN] -> (Сила далексов) <- [: USED_IN] — (Далекс) <- [: MEMBER_OF] — (Далек 7) — [: COMPOSED_OF] -> (юбка) — [ : ORIGINAL_PROP] -> (Dalek 7) INCLUDE_AND_PRUNE
• — [: COMPOSED_OF] -> (плечо) — [: ORIGINAL_PROP] -> (Dalek 7) INCLUDE_AND_PRUNE
• <- [: MEMBER_OF] — (Dalek Six-5) — [: COMPOSED_OF] -> (юбка) — [: ORIGINAL_PROP] -> (Dalek 5) INCLUDE_AND_PRUNE
• — [: COMPOSED_OF] -> (плечо) — [: ORIGINAL_PROP] -> (Dalek 6) INCLUDE_AND_PRUNE
• <- [: MEMBER_OF] — (Dalek 2) — [: COMPOSED_OF] -> (юбка) — [: ORIGINAL_PROP] -> (Dalek 2) INCLUDE_AND_PRUNE
• — [: COMPOSED_OF] -> (плечо) — [: ORIGINAL_PROP] -> (Dalek 2) INCLUDE_AND_PRUNE
• <- [: MEMBER_OF] — (Далек 1) — [: COMPOSED_OF] -> (юбка) — [: ORIGINAL_PROP] -> (Далек 1) INCLUDE_AND_PRUNE
• — [: COMPOSED_OF] -> (плечо) — [: ORIGINAL_PROP] -> (Далек 1) INCLUDE_AND_PRUNE

Теперь, когда traverser вернулся в узел видов Dalek, он пытается следующее отношение APPEARED_IN:

• — [: APPEARED_IN] -> (Вторжение Земли в далек) <- [: USED_IN] — (Далекс) <- [: MEMBER_OF] — (Далек 6) — [: COMPOSED_OF] -> (юбка) — [: ORIGINAL_PROP] -> (Далек 6) INCLUDE_AND_PRUNE
• — [: COMPOSED_OF] -> (плечо) — [: ORIGINAL_PROP] -> (Dalek 6) INCLUDE_AND_PRUNE

И так далее.

Когда он запустится, наш traverser вернет все пути от узла видов Dalek к исходным узлам реквизита, связанным с каждой частью реквизита. Каждый путь содержит все детали узлов и отношений по этому пути, начиная с видом узлом Далеков и заканчивая оригинальный пропеллером узел, соответствующим эпизода и проп части узлов где-то посередине.

Сам по себе результат прохождения не говорит нам, какая часть пропеллера использовалась чаще всего; для этого нам нужно сделать некоторое накопление. Чтобы сгенерировать подсчитанные и отсортированные результаты, наш код вызывает getSortedResults (), который является просто вспомогательным методом, который делегирует экземпляр ResultsAssembler. Этот ResultsAssembler отвечает за накопление результатов для каждой части пропеллера.

Вот метод getSortedResults ():

private Map<String, Integer> getSortedResults(Traverser traverser) {
  Map<String, Integer> results = new ResultsAssembler<Path>(traverser)
    .sortResults(new PathAccessor());
  return results;
}

А вот код для ResultsAssembler:

public interface QueryResultAccessor<T> {
  String getOriginalProp(T queryResult);
  String getPart(T queryResult);
}
  
public class ResultsAssembler<T>{
  private final Iterable<T> queryResults;

  public ResultsAssembler(Iterable<T> queryResults) {
    super();
    this.queryResults = queryResults;
  }
    
  public Map<String, Integer> sortResults(QueryResultAccessor<T> accessor){
    Map<String, Integer> unsortedResults = new HashMap<String, Integer>();
      
    for (T queryResult : queryResults){
      String originalProp = accessor.getOriginalProp(queryResult);
      String part = accessor.getPart(queryResult);
            
      String key = originalProp + " " + part;
      if (!unsortedResults.containsKey(key)){
        unsortedResults.put(key, 0);
      }
      unsortedResults.put(key, unsortedResults.get(key) + 1);
    }
      
    Comparator<String> valueComparator = Ordering.natural()
      .onResultOf(Functions.forMap(unsortedResults))
      .reverse().compound(Ordering.natural());
    return ImmutableSortedMap.copyOf(unsortedResults, valueComparator);
  }
    
}

ResultsAssembler строит карту ключей частей реквизита и значений количества эпизодов. Ассемблер использует QueryResultAccessor для извлечения исходного имени проп и части проп из результата запроса. Здесь результатом запроса является путь, но когда мы возвращаемся к следующему примеру, в котором используется библиотека сопоставления с образцом, это объект сопоставления с образцом. Отсюда общие параметры.

Вот PathAccessor, который мы используем для доступа к исходному имени проп и части проп с пути. Исходные детали реквизита хранятся в последнем узле пути, а детали реквизита — в предпоследнем узле. Метод getOriginalProp () может довольно легко получить исходные реквизиты из свойства endNode () пути. Чтобы получить имя детали ( плечи или юбку ), метод getPath () использует итератор path () и вспомогательную функцию итератора для доступа к последнему, но одному узлу.

private class PathAccessor implements QueryResultAccessor<Path>{

  @Override
  public String getOriginalProp(Path queryResult) {
    Node originalPropNode = queryResult.endNode();
    return getPropertyValueOrNull(originalPropNode, "prop");
  }

  @Override
  public String getPart(Path queryResult) {
    Iterable<Node> pathNodes = IteratorUtil.asIterable(
      queryResult.nodes().iterator());
    Node partNode = IteratorUtil.fromEnd(pathNodes, 1);
    return getPropertyValueOrNull(partNode, "part");
  }
    
  private String getPropertyValueOrNull(Node node, String property){
    if (!node.hasProperty(property)){
      return null;
    }
    return node.getProperty(property).toString();
  }
    
}

Накопив и сортируются результаты, наш блок тест может затем утверждать , что результаты содержат первую тройку наиболее часто используемых гребной винт частей: Далек- «ы плечи, Далек 5 юбки с, и Далеками 6 плечами«ы. Каждая из этих частей появилась в 12 рассказах.

Как выглядят плечи Dalek 1 сегодня, спустя почти 50 лет после того, как они впервые появились на телевидении? Далек 6388, конечно, имеет ответ .

Сопоставление с образцом

Система Traversal Framework помогла нам найти наиболее трудолюбивые детали Dalek в шоу-бизнесе, но нам все еще пришлось проделать немало работы, чтобы получить результаты. Хотя само описание обхода было относительно тривиальным, необходимость итерации узлов в каждом из возвращаемых путей оказалась довольно утомительной. С библиотекой Pattern Matching мы можем избежать некоторого беспорядочного итеративного кода, который возник в PathAccessor.

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

@Test
public void shouldFindTheHardestWorkingPropsUsingPatternMatchers(){
  Node theDaleksNode = database.index().forNodes("species")
    .get("species", "Dalek").getSingle();
      
  final PatternNode theDaleks = new PatternNode();    
  final PatternNode episode = new PatternNode();
  final PatternNode props = new PatternNode();
  final PatternNode prop = new PatternNode();
  final PatternNode part = new PatternNode();
  final PatternNode originalProp = new PatternNode();

  theDaleks.setAssociation(theDaleksNode);
  theDaleks.createRelationshipTo(episode, Rels.APPEARED_IN);
  props.createRelationshipTo(episode, Rels.USED_IN);
  prop.createRelationshipTo(props, Rels.MEMBER_OF);
  prop.createRelationshipTo(part, Rels.COMPOSED_OF);
  part.createRelationshipTo(originalProp, Rels.ORIGINAL_PROP);
        
  PatternMatcher pm = PatternMatcher.getMatcher();
  final Iterable<PatternMatch> matches = pm.match(theDaleks, theDaleksNode);
        
  assertHardestWorkingPropParts(getSortedResults(matches, originalProp, part),
    "Dalek 1 shoulder", 12,
    "Dalek 5 skirt", 12,
    "Dalek 6 shoulder", 12); 
}

Объекты узла шаблона, которые мы определяем как часть нашего абстрактного подграфа, могут затем использоваться в качестве ключей в результатах сопоставления. Ниже приведен метод getSortedResults () и класс MatchAccessor для примера сопоставления с образцом. Вы заметите, что мы передаем объекты узла originalProp и части шаблона в MatchAccessor. Затем средство доступа вызывает метод getNodeFor () сопоставления с одним или другим из этих узлов шаблона, чтобы извлечь реальный сопоставленный узел.

private Map<String, Integer> getSortedResults(Iterable<PatternMatch> matches, 
    PatternNode originalProp, PatternNode part) {
  Map<String, Integer> results = new ResultsAssembler<PatternMatch>(matches)
    .getSortedResults(new MatchAccessor(originalProp, part));
  return results;
}

private class MatchAccessor implements QueryResultAccessor<PatternMatch>{

  private final PatternNode originalProp;
  private final PatternNode part;
    
  public MatchAccessor(PatternNode originalProp, PatternNode part) {
    super();
    this.originalProp = originalProp;
    this.part = part;
  }

  @Override
  public String getOriginalProp(PatternMatch queryResult) {
    return queryResult.getNodeFor(originalProp).getProperty("prop").toString();
  }

  @Override
  public String getPart(PatternMatch queryResult) {
    return queryResult.getNodeFor(part).getProperty("part").toString();
  }  
}

public void shouldFindTheHardestWorkingPropsUsingCypher() throws Exception {
  CypherParser parser = new CypherParser();
  ExecutionEngine engine = new ExecutionEngine(universe.getDatabase());
  
  String cql = "start daleks=(Species,species,'Dalek')"
    + " match (daleks)-[:APPEARED_IN]->(episode)"
    + "<-[:USED_IN]-(props)"
    + "<-[:MEMBER_OF]-(prop)"
    + "-[:COMPOSED_OF]->(part)"
    + "-[:ORIGINAL_PROP]->(originalprop)"
    + " return originalprop.prop, part.part, count(episode.title)"
    + " order by count(episode.title) desc"
    + " limit 3";

  Query query = parser.parse(cql);
   ExecutionResult result = engine.execute(query);
      
  assertHardestWorkingPropParts(result.javaIterator(),
    "Dalek 1", "shoulder", 12,
    "Dalek 5", "skirt", 12,
    "Dalek 6", "shoulder", 12);
}
  
private void assertHardestWorkingPropParts(
    Iterator<Map<String, Object>> results, Object... partsAndCounts) {
  for (int index = 0; index < partsAndCounts.length; index = index + 3){
    Map<String, Object> row = results.next();
    assertEquals(partsAndCounts[index], row.get("originalprop.prop"));
    assertEquals(partsAndCounts[index + 1], row.get("part.part"));
    assertEquals(partsAndCounts[index + 2], row.get("count(episode.title)"));
  }
  
  assertFalse(results.hasNext());
}

start daleks=(Species,species,'Dalek')
match (daleks)-[:APPEARED_IN]->(episode)<-[:USED_IN]-(props)<-[:MEMBER_OF]-
      (prop)-[:COMPOSED_OF]->(part)-[:ORIGINAL_PROP]->(originalprop)
return originalprop.prop, part.part, count(episode.title)
order by count(episode.title) desc
limit 3

Наше учебное пособие по Neo4j свободно доступно на GitHub . Загрузите его сейчас и попробуйте некоторые из упражнений. И продолжайте проверять обновления: по мере роста Neo4j будет развиваться и учебник.

Джим и я также проводим однодневные и двухдневные версии учебника на ряде конференций и других мероприятий:

• UberConf 2011 , Денвер, 15 июля
• GOTO Орхус 2011 , 13 октября
• GOTO Амстердам 2011 , 15 октября
• SkillsMatter , 3-4 ноября

(Изображение пропеллера Dalek принадлежит галерее Project Dalek Forum , другому замечательному источнику для исследователей опор Dalek и строителей Dalek.)

Источник: http://iansrobinson.com/2011/07/11/the-power-of-the-daleks- и-Neo4j /