This is an example showing a hierarchy of roles. What’s interesting is that a tree is not sufficient for storing this kind of structure, as elaborated below.
This is an implementation of an example found in the article A Model to Represent Directed Acyclic Graphs (DAG) on SQL Databases by Kemal Erdogan. The article discusses how to store directed acyclic graphs (DAGs) in SQL based DBs. DAGs are almost trees, but with a twist: it may be possible to reach the same node through different paths. Trees are restricted from this possibility, which makes them much easier to handle. In our case it is “Ali” and “Engin”, as they are both admins and users and thus reachable through these group nodes. Reality often looks this way and can’t be captured by tree structures.
In the article an SQL Stored Procedure solution is provided. The main idea, that also have some support from scientists, is to pre-calculate all possible (transitive) paths. Pros and cons of this approach:
- decent performance on read
- low performance on insert
- wastes lots of space
- relies on stored procedures
In Neo4j storing the roles is trivial. In this case we use PART_OF (green edges) relationships
to model the group hierarchy and MEMBER_OF (blue edges) to model membership in groups.
We also connect the top level groups to the reference node by ROOT relationships.
This gives us a useful partitioning of the graph. Neo4j has no predefined relationship
types, you are free to create any relationship types and give them the semantics you want.
Lets now have a look at how to retrieve information from the graph. The Java code is using the Neo4j Traversal API (see Section 6.2, “Traversal Framework Java API”), the queries are done using Cypher.
Node admins = getNodeByName( "Admins" );
TraversalDescription traversalDescription = Traversal.description()
.breadthFirst()
.evaluator( Evaluators.excludeStartPosition() )
.relationships( RoleRels.PART_OF, Direction.INCOMING )
.relationships( RoleRels.MEMBER_OF, Direction.INCOMING );
Traverser traverser = traversalDescription.traverse( admins );
resulting in the output
Found: HelpDesk at depth: 0 Found: Ali at depth: 0 Found: Engin at depth: 1 Found: Demet at depth: 1
The result is collected from the traverser using this code:
String output = "";
for ( Path path : traverser )
{
Node node = path.endNode();
output += "Found: " + node.getProperty( NAME ) + " at depth: "
+ ( path.length() - 1 ) + "\n";
}
In Cypher, a similar query would be:
START admins=node(14) MATCH admins<-[:PART_OF*0..]-group<-[:MEMBER_OF]-user RETURN user.name, group.name
resulting in:
| user.name | group.name |
|---|---|
| 3 rows | |
|
|
|
|
|
|
Using the Neo4j Java Traversal API, this query looks like:
Node jale = getNodeByName( "Jale" );
traversalDescription = Traversal.description()
.depthFirst()
.evaluator( Evaluators.excludeStartPosition() )
.relationships( RoleRels.MEMBER_OF, Direction.OUTGOING )
.relationships( RoleRels.PART_OF, Direction.OUTGOING );
traverser = traversalDescription.traverse( jale );
resuling in:
Found: ABCTechnicians at depth: 0 Found: Technicians at depth: 1 Found: Users at depth: 2
In Cypher:
START jale=node(10) MATCH jale-[:MEMBER_OF]->()-[:PART_OF*0..]->group RETURN group.name
| group.name |
|---|
| 3 rows |
|
|
|
In Java:
Node referenceNode = getNodeByName( "Reference_Node") ;
traversalDescription = Traversal.description()
.breadthFirst()
.evaluator( Evaluators.excludeStartPosition() )
.relationships( RoleRels.ROOT, Direction.INCOMING )
.relationships( RoleRels.PART_OF, Direction.INCOMING );
traverser = traversalDescription.traverse( referenceNode );
resulting in:
Found: Admins at depth: 0 Found: Users at depth: 0 Found: HelpDesk at depth: 1 Found: Managers at depth: 1 Found: Technicians at depth: 1 Found: ABCTechnicians at depth: 2
In Cypher:
START refNode=node(16) MATCH refNode<-[:ROOT]->()<-[:PART_OF*0..]-group RETURN group.name
| group.name |
|---|
| 6 rows |
|
|
|
|
|
|
Now, let’s try to find all users in the system being part of any group.
in Java:
traversalDescription = Traversal.description()
.breadthFirst()
.evaluator(
Evaluators.includeWhereLastRelationshipTypeIs( RoleRels.MEMBER_OF ) );
traverser = traversalDescription.traverse( referenceNode );
Found: Ali at depth: 1 Found: Engin at depth: 1 Found: Burcu at depth: 1 Found: Can at depth: 1 Found: Demet at depth: 2 Found: Gul at depth: 2 Found: Fuat at depth: 2 Found: Hakan at depth: 2 Found: Irmak at depth: 2 Found: Jale at depth: 3
In Cypher, this looks like:
START refNode=node(16) MATCH refNode<-[:ROOT]->root, p=root<-[PART_OF*0..]-()<-[:MEMBER_OF]-user RETURN user.name, min(length(p)) ORDER BY min(length(p)), user.name
and results in the following output:
| user.name | min(length(p)) |
|---|---|
| 10 rows | |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
As seen above, querying even more complex scenarios can be done using comparatively short constructs in Java and other query mechanisms.