Graph traversal for hierarchical relations

Question

I have graph represents the parent child hierarchy. Also it holds the relationship between objects.

I have above as graph. Where Orange are my parent-child hierarchy and Green are my relations. So if i want to get relation between E and F, i will get the relation which is in between B and C (as they are parents of E and F). This relation finding can go up to top most parents.

I can find the parents of a node using Gremlin query like

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

This query will return me B and A.

Q. On similar lines does Gremlin or any other graph query language supports the relation inheritance ? How Gremlin query should be formed ?

Note : Graph can be very huge containing many unique nodes and many unique relations. I want to get the inherited relations in quick time so that i wont have to pre-calculate and cached it or make duplicates for quick reference.

camba1 camba1 · Accepted Answer · 2019-06-06T19:36:38

I assume that by inheritance you mean the ability to traverse from grandparent to parent to child to grand child ,etc... Arango support traversals and has the ability to traverse these type of relationships very fast. For example, to duplicate your example above of starting at node D and getting node B and A you could do something like :

// 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

In terms of performance, I have traversed irregular hierarchies with thousands of nodes without performance issues and without having to cache anything. Keep in mind however that there is no magic here and a bad data model will cause trouble no matter the db engine.

There is some performance information here if you want to review and play with it here

Traversing multiple edges (relationship types) is very similar to our earlier example. To find the path from E to F using hierarchy (orange) edges and relationship (green) edges, we can do :

// 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

Or if we just want the shortest path between E and F we can do for example:

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

Note that I just used the id of the "F" record in the code above, but we could have searched fo the record using the name just like we did for the "E" record.

Also note we created the edge data for our example as directed edges in the DB: parentOf edges were created from parent to child (ex: A to B) and for green relationships edges we created them alphabetically (ex: B to C).

Graph traversal for hierarchical relations

1 Answers