Обход графа для иерархических отношений - PullRequest
Новая
       37

Обход графа для иерархических отношений

1 голос
/ 06 июня 2019

У меня есть график, представляющий родительскую дочернюю иерархию.Также он содержит отношения между объектами.A

У меня есть выше, как график.Где Оранжевый - моя иерархия родитель-потомок, а Зеленый - мои отношения.Поэтому, если я хочу получить отношение между E и F , я получу отношение, которое находится между B и C (какони родители E и F).Это обнаружение отношений может подойти большинству родителей.

Я могу найти родителей узла, используя запрос Gremlin, например 

g.V().has('name', 'D').repeat(out('parent')).emit().values('name')

Этот запрос вернет меня B и A.

Q.Схожим ли образом Gremlin или любой другой язык запросов графов поддерживает наследование отношений?Как должен формироваться запрос Gremlin?

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

1 Ответ

0 голосов
/ 06 июня 2019

Я предполагаю, что под наследованием вы подразумеваете способность переходить от прародителя к родителю, от ребенка к внуку и т. Д. Аранго поддерживает обходы и обладает способностью очень быстро перебирать эти типы отношений.Например, чтобы повторить приведенный выше пример, начиная с узла D и получая узлы B и A, вы можете сделать что-то вроде: 

// Find all nodes that are named d
let dNodes = (FOR test in test2
            FILTER test.name == 'd'
            RETURN test)

//Traverse outbound relationships starting at the dNodes and return up to 2 nodes up the hierarchy
FOR node in dNodes
   FOR v,e IN 1..2 OUTBOUND node
   testEdge
RETURN v

С точки зрения производительности, я пересек нерегулярные иерархии с тысячами узлов без производительностипроблемы и без необходимости что-либо кэшировать.Имейте в виду, однако, что здесь нет никакой магии, и плохая модель данных вызовет проблемы, независимо от движка БД.

Здесь есть некоторая информация о производительности, если вы хотите просмотреть и поиграть с ней здесь

Обход нескольких ребер (типов отношений) очень похож на наш предыдущий пример.Чтобы найти путь от E до F, используя иерархические (оранжевые) ребра и отношения (зеленые) ребра, мы можем сделать: 

// Find all nodes that are named E
let eNodes = (FOR test in test3
            FILTER test.name == 'E'
            RETURN test
            )

// Start in node E and go upto three steps
// Traverse the hierarchy edges in any direction (so that we can find parents and child nodes)
// Traverse the relatedto (green) edges in the outbound direction only
// Filter the traversal to items that end in vertice F and return the path (E<-B->C->F)
FOR node in eNodes
   FOR v,e,p IN 1..3 ANY node
   parentOf, OUTBOUND relatedTo 
   FILTER v.name == 'F'
RETURN p

Или, если мы просто хотим кратчайший путь между E и F, который мы можем сделать дляпример: 

let eNodes = (FOR test in test3
            FILTER test.name == 'E'
            RETURN test
            )
//Find shortest path between node E and F and return the path (E<-B->C->F)            
FOR node in eNodes
    FOR v, e IN ANY SHORTEST_PATH
      node TO 'test3/F'                 
      parentOf, OUTBOUND relatedTo
RETURN e

Обратите внимание, что я только что использовал идентификатор записи "F" в приведенном выше коде, но мы могли бы искать запись, используя имя, как мы делали для записи "E".

Также обратите внимание, что мы создали данные ребер для нашего примера как направленные ребра в БД: ребра parentOf были созданы от родителя к потомку (например, от A до B), а для ребер родственных связей мы создали их в алфавитном порядке (например,: От B до C).

...