Assembly

From NeoWiki

This is an example showing parts composed by other parts. We will have a look at how recursion can be used in this context.

This example is based off an example found in Database management Systems by Raghu Ramakrishnan and Johannes Gehrke. In chapter 25 (slides found here) on deductive databases they start out by showing how such data can be modeled using SQL-based databases. It could look like this:

SQL assembly table

Part	Subpart	Quantity
trike	wheel	3
motorcycle	wheel	2
wheel	spoke	2
wheel	tire	1
...	...	...

In relational algebra or SQL-92 there is no way to query for the parts of a trike or motorcycle, this has to be solved by using multiple dependent queries. You have to search for all parts of the trike first, then perform new such searches with every subpart until all levels were reached. From SQL-99/SQL3 and on the needed recursion can be performed directly in SQL (but it is not part of the core subset), but still at the cost of searches having to be performed at every step in the recursion. In real-world cases, the number of levels (and recursive searches) tend to become high.

With neo4j we don't squeeze the assembly data into tables, but rather represent them directly in the node space graph. From the trike and motorcycle nodes there are relationships of the type COMPOSED_BY. As seen from the image, these relationships have the property quantity. For instance, the relationship from trike to wheel has the quantity property set to 3.

This should be all we need to know about the data model to print out a list of subparts and quantities for the vehicles.

[edit] Finding the parts

Finding the parts means nothing other than navigating through the graph. In the following code, the outer loop will iterate over all nodes that are connected by an outgoing connection from the reference node in our node space. This gives the vehicle nodes as input for the inner loop.

The inner loop performs a traversal through the graph, printing name and quantity of every part. To make the output more readable, indentation according to the current traversal depth is added.

for ( Relationship vehicleRel : neo.getReferenceNode().getRelationships( Direction.OUTGOING ) )
{
    Node vehicle = vehicleRel.getEndNode();
    System.out.println( "Product: " + vehicle.getProperty( "name" ) );
    Traverser traverser = vehicle.traverse(
        Traverser.Order.DEPTH_FIRST,
        StopEvaluator.END_OF_NETWORK,
        ReturnableEvaluator.ALL_BUT_START_NODE,
        VehicleRels.COMPOSED_BY, Direction.OUTGOING );
    for ( Node part : traverser )
    {
        int depth = traverser.currentPosition().depth();
        for ( int i = 0; i < depth; i++ ) { System.out.print( "  " ); }
        System.out.print( part.getProperty( "name" ) );
        Relationship rel = traverser.currentPosition().lastRelationshipTraversed();
        if ( rel != null )
        {
            System.out.print( " " + rel.getProperty( "quantity", 1 ) );
        }
        System.out.println();
    }
}

The code getProperty( "quantity", 1 ) means that if no quantity is found, the default value 0 (zero) should be used.

The output will look like this:

Product: trike
  frame 1
    pedal 1
    seat 1
  wheel 3
    tire 1
      tube 1
      rim 1
    spoke 2
Product: motorcycle
  frame 1
    pedal 1
    seat 1
  wheel 2
    tire 1
      tube 1
      rim 1
    spoke 2

[edit] Getting the costs

To put the costs into the model, a cost property is added to the nodes. Let's take a closer look on one of the nodes, the one that represents a frame:

Through the cost property, every part keeps information on the costs added by it (costs of purchase, assembly etc). Obviously, every part has a name property as well.

To calculate the cost of a part or a vehicle we take the cost added by the part itself, and then add the cost of every subpart multiplied by the quantity needed. The cost added by the part itself is found in the cost property. The quantity is fetched from the relationship between part and subpart. The cost of the subpart is retrieved by a recursive call to getCost(). Note: the recursion doesn't add any search operations in the database, only navigation with very high performance.

The loop iterates over all outgoing relationships from a part to its subparts, to collect information about them.

private int getCost( Node part )
{
    int sum = (Integer) part.getProperty( "cost", 0 );
    for ( Relationship rel : part.getRelationships( Direction.OUTGOING ) )
    {
        Node subPart = rel.getEndNode();
        int quantity = (Integer) rel.getProperty( "quantity", 1 );
        sum += getCost( subPart ) * quantity;
    }
    return sum;
}

As in the previous code snippet, default values for the properties are given. The getProperty() method returns Object, so we have to cast the values to Integer in this case.

[edit] References

• Full source code: browser, repository.
• Neo4j node space screenshots made with Neoclipse.