Prev |  | Next

## 7.1. 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 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" that brake the tree pattern, as they are both admins and users. 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` (blue edges) relationships to model the group hierarchy and `MEMBER_OF` (green 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 (Section 3.5, “Traversal”), the queries are done using the Chapter 16, Cypher Query Language.

### 7.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

As Cypher, this looks like:

    START admins=node(14)
    MATCH admins<-[:PART_OF*0..]-subrole<-[:MEMBER_OF]-user
    RETURN user, subrole

resulting in:

user | subrole
--- | ---
3 rows, 43 ms
`Node[15]{name->"Ali"}` | `Node[14]{name->"Admins"}`
`Node[8]{name->"Engin"}` | `Node[4]{name->"HelpDesk"}`
`Node[7]{name->"Demet"}` | `Node[4]{name->"HelpDesk"}`

### 7.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..]->role
    RETURN jale, role

jale | role
--- | ---
3 rows, 3 ms
`Node[10]{name->"Jale"}` | `Node[3]{name->"ABCTechnicians"}`
`Node[10]{name->"Jale"}` | `Node[6]{name->"Technicians"}`
`Node[10]{name->"Jale"}` | `Node[2]{name->"Users"}`

### 7.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

group
6 rows, 5 ms
`Node[14]{name->"Admins"}`
`Node[4]{name->"HelpDesk"}`
`Node[2]{name->"Users"}`
`Node[5]{name->"Managers"}`
`Node[6]{name->"Technicians"}`
`Node[3]{name->"ABCTechnicians"}`

### 7.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 p=refNode<-[:ROOT]->parent<-[:PART_OF*0..]-group, group<-[:MEMBER_OF]-user
    RETURN group.name, user.name, LENGTH(p)
    ORDER BY LENGTH(p)

and results in the following output, listing even duplicate pathes to users, see e.g. user `Engin`.

group.name | user.name | LENGTH(p)
--- | --- | ---
12 rows, 26 ms
`Admins` | `Ali` | `1`
`Users` | `Ali` | `1`
`Users` | `Engin` | `1`
`Users` | `Burcu` | `1`
`Users` | `Can` | `1`
`HelpDesk` | `Engin` | `2`
`HelpDesk` | `Demet` | `2`
`Managers` | `Gul` | `2`
`Managers` | `Fuat` | `2`
`Technicians` | `Hakan` | `2`
`Technicians` | `Irmak` | `2`
`ABCTechnicians` | `Jale` | `3`

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

Full source code: RolesTest.java

Copyright © 2011 Neo Technology

Prev | Up | Next
| Home |