9.1. User roles in graphs

Prev		Next

9.1.1. Get the admins
9.1.2. Get the group memberships of a user
9.1.3. Get all groups
9.1.4. Get all members of all groups

This is an example showing a hierarchy of roles. What’s interesting is that a tree is not sufficient for storing this 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 any 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 8.2, “Traversal Framework Java API”), the queries are done using Cypher.

9.1.1. Get the admins

Node admins = getNodeByName( "Admins" );
Traverser traverser = admins.traverse(
        Traverser.Order.BREADTH_FIRST,
        StopEvaluator.END_OF_GRAPH,
        ReturnableEvaluator.ALL_BUT_START_NODE,
        RoleRels.PART_OF, Direction.INCOMING,
        RoleRels.MEMBER_OF, Direction.INCOMING );

resulting in the output

Found: Ali at depth: 0
Found: HelpDesk 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 ( Node node : traverser )
{
    output += "Found: " + node.getProperty( NAME ) + " at depth: "
              + ( traverser.currentPosition().depth() - 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, 37 ms
`"Ali"`	`"Admins"`
`"Engin"`	`"HelpDesk"`
`"Demet"`	`"HelpDesk"`

9.1.2. Get the group memberships of a user

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

Node jale = getNodeByName( "Jale" );
traverser = jale.traverse(
        Traverser.Order.DEPTH_FIRST,
        StopEvaluator.END_OF_GRAPH,
        ReturnableEvaluator.ALL_BUT_START_NODE,
        RoleRels.MEMBER_OF, Direction.OUTGOING,
        RoleRels.PART_OF, Direction.OUTGOING );

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, 3 ms
`"ABCTechnicians"`
`"Technicians"`
`"Users"`

9.1.3. Get all groups

In Java:

Node referenceNode = getNodeByName( "Reference_Node") ;
traverser = referenceNode.traverse(
        Traverser.Order.BREADTH_FIRST,
        StopEvaluator.END_OF_GRAPH,
        ReturnableEvaluator.ALL_BUT_START_NODE,
        RoleRels.ROOT, Direction.INCOMING,
        RoleRels.PART_OF, Direction.INCOMING );

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, 5 ms
`"Admins"`
`"HelpDesk"`
`"Users"`
`"Managers"`
`"Technicians"`
`"ABCTechnicians"`

9.1.4. Get all members of all groups

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

in Java:

traverser = referenceNode.traverse(
        Traverser.Order.BREADTH_FIRST,
        StopEvaluator.END_OF_GRAPH,
        new ReturnableEvaluator()
        {
            @Override
            public boolean isReturnableNode(
                    TraversalPosition currentPos )
            {
                if ( currentPos.isStartNode() )
                {
                    return false;
                }
                Relationship rel = currentPos.lastRelationshipTraversed();
                return rel.isType( RoleRels.MEMBER_OF );
            }
        },
        RoleRels.ROOT, Direction.INCOMING,
        RoleRels.PART_OF, Direction.INCOMING,
        RoleRels.MEMBER_OF, Direction.INCOMING );

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, 43 ms
`"Ali"`	`1`
`"Burcu"`	`1`
`"Can"`	`1`
`"Engin"`	`1`
`"Demet"`	`2`
`"Fuat"`	`2`
`"Gul"`	`2`
`"Hakan"`	`2`
`"Irmak"`	`2`
`"Jale"`	`3`

As seen above, querying even more complex scenarios can be done using comparatively short constructs in Java and other query mechanisms.