6.16. User roles in graphs

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.

roles.png

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 the queries are done using Cypher, the Java code is using the Neo4j Traversal API (see Section 33.2, “Traversal Framework Java API”, which is part of Advanced Usage).

Get the admins

In Cypher, we could get the admins like this:

MATCH ({ name: 'Admins' })<-[:PART_OF*0..]-(group)<-[:MEMBER_OF]-(user)
RETURN user.name, group.name

resulting in:

user.namegroup.name
3 rows

"Ali"

"Admins"

"Demet"

"HelpDesk"

"Engin"

"HelpDesk"

And here’s the code when using the Java Traversal API:

Node admins = getNodeByName( "Admins" );
TraversalDescription traversalDescription = db.traversalDescription()
        .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: Ali at depth: 0
Found: HelpDesk at depth: 0
Found: Demet at depth: 1
Found: Engin 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";
}

Get the group memberships of a user

In Cypher:

MATCH ({ name: 'Jale' })-[:MEMBER_OF]->()-[:PART_OF*0..]->(group)
RETURN group.name
group.name
3 rows

"ABCTechnicians"

"Technicians"

"Users"

Using the Neo4j Java Traversal API, this query looks like:

Node jale = getNodeByName( "Jale" );
traversalDescription = db.traversalDescription()
        .depthFirst()
        .evaluator( Evaluators.excludeStartPosition() )
        .relationships( RoleRels.MEMBER_OF, Direction.OUTGOING )
        .relationships( RoleRels.PART_OF, Direction.OUTGOING );
traverser = traversalDescription.traverse( jale );

resulting in:

Found: ABCTechnicians at depth: 0
Found: Technicians at depth: 1
Found: Users at depth: 2

Get all groups

In Cypher:

MATCH ({ name: 'Reference_Node' })<-[:ROOT]->()<-[:PART_OF*0..]-(group)
RETURN group.name
group.name
6 rows

"Users"

"Managers"

"Technicians"

"ABCTechnicians"

"Admins"

"HelpDesk"

In Java:

Node referenceNode = getNodeByName( "Reference_Node") ;
traversalDescription = db.traversalDescription()
        .breadthFirst()
        .evaluator( Evaluators.excludeStartPosition() )
        .relationships( RoleRels.ROOT, Direction.INCOMING )
        .relationships( RoleRels.PART_OF, Direction.INCOMING );
traverser = traversalDescription.traverse( referenceNode );

resulting in:

Found: Users at depth: 0
Found: Admins at depth: 0
Found: Technicians at depth: 1
Found: Managers at depth: 1
Found: HelpDesk at depth: 1
Found: ABCTechnicians at depth: 2

Get all members of all groups

Now, let’s try to find all users in the system being part of any group.

In Cypher, this looks like:

MATCH ({ name: 'Reference_Node' })<-[: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.namemin(length(p))
10 rows

"Ali"

1

"Burcu"

1

"Can"

1

"Engin"

1

"Demet"

2

"Fuat"

2

"Gul"

2

"Hakan"

2

"Irmak"

2

"Jale"

3

in Java:

traversalDescription = db.traversalDescription()
        .breadthFirst()
        .evaluator(
                Evaluators.includeWhereLastRelationshipTypeIs( RoleRels.MEMBER_OF ) );
traverser = traversalDescription.traverse( referenceNode );

Found: Can at depth: 1
Found: Burcu at depth: 1
Found: Engin at depth: 1
Found: Ali at depth: 1
Found: Irmak at depth: 2
Found: Hakan at depth: 2
Found: Fuat at depth: 2
Found: Gul at depth: 2
Found: Demet at depth: 2
Found: Jale at depth: 3

As seen above, querying even more complex scenarios can be done using comparatively short constructs in Cypher or Java.