Neo4j Wiki から

This is an example showing a hierarchy of roles. What's interesting is that a tree is not sufficient for storing this structure as you will see.


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, as working with graphs is what Neo4j was designed for. 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.

[edit] Find the admins

Suppose we want to find all admin groups and actual admins!

This code will find it for us, and tell us the number of "hops" from the Admins node:

Node admins = graphDb.getAdminsNodeSomehow();
Traverser traverser = admins.traverse(
    RoleRels.PART_OF, Direction.INCOMING,
    RoleRels.MEMBER_OF, Direction.INCOMING );
for ( Node part : traverser )
    System.out.println( part.getProperty( "name" ) + " "
        + (traverser.currentPosition().depth() - 1) );

The initialization tells the traverser to start from the admins node, go breadth-first, not to return the start node and to follow both PART_OF and MEMBER_OF relationships with an incoming direction. It almost reads as English! :-)

After initializing the traverser not much work is left. Simply iterate and print the results. Note that the traversal uses navigation to find the nodes we want in the graph, not some kind of search!

Here's how the output will look:

HelpDesk 0
Ali 0
Demet 1
Engin 1

[edit] Find the memberships

Now it's time to look in the opposite direction. In practice, this means that we have to initialize our traverser to follow outgoing relationships this time.

This is how to find the memberships of Jale:

Node jale = graphDb.getJaleNodeSomehow();
Traverser traverser = jale.traverse(
    RoleRels.MEMBER_OF, Direction.OUTGOING, 
    RoleRels.PART_OF, Direction.OUTGOING );
for ( Node membership : traverser )
    System.out.println( membership.getProperty( "name" ) + " "
        + (traverser.currentPosition().depth() - 1) );

Like before, we print out the names and the number of "hops".

This is the output we get:

ABCTechnicians 0
Technicians 1
Users 2

[edit] References

Neo4j のサイト