Variable length patterns

This section uses the example of Stations and Stops used in the previous section, but with an additional property distance added to the NEXT relationships:

As the name suggests, this property represents the distance between two Stops. To return the total distance for each service connecting a pair of Stations, a variable referencing each of the relationships traversed is needed. Similarly, to extract the departs and arrives properties of each Stop, variables referencing each of the nodes traversed is required. In this example of matching services between Denmark Hill and Clapham Junction, the variables l and m are declared to match the Stops and r is declared to match the relationships. The variable origin only matches the first Stop in the path:

Variables that are declared inside quantified path patterns are known as group variables. They are so called because, when referred outside of the quantified path pattern, they are lists of the nodes or relationships they are bound to in the match. To understand how to think about the way group variables are bound to nodes or relationships, it helps to expand the quantified path pattern, and observe how the different variables match to the elements of the overall matched path. Here the three different expansions for each value in the range given by the quantifier {1,3}:

The subscript of each variable indicates which instance of the path pattern repetition they belong to. The following diagram shows the variable bindings of the path pattern with three repetitions, which matches the service that departs Denmark Hill at 17:07. It traces the node or relationship that each indexed variable is bound to. Note that the index increases from right to left as the path starts at Denmark Hill:

For this matched path, the group variables have the following bindings:

The second solution is the following path:

The following table shows the bindings for both matches, including the variable origin. In contrast to the group variables, origin is a singleton variable due to being declared outside the quantification. Singleton variables bind at most to one node or relationship.

Returning to the original goal, which was to return the sequence of depart times for the Stops and the total distance of each service, the final query exploits the compatibility of group variables with list comprehensions and list functions such as reduce():

One of the pitfalls of quantified path patterns is that, depending on the graph, they can end up matching very large numbers of paths, resulting in a slow query performance. This is especially true when searching for paths with a large maximum length or when the pattern is too general. However, by using inline predicates that specify precisely which nodes and relationships should be included in the results, unwanted results will be pruned as the graph is traversed.

Here are some examples of the types of constraints you can impose on quantified path pattern traversals:

To demonstrate the utility of predicates in quantified path patterns, this section considers an example of finding the shortest path by physical distance and compares that to the results yielded by using the SHORTEST keyword. The graph in this example continues with Station nodes, but adds both a geospatial location property to the Stations, as well as LINK relationships with a distance property representing the distance between pairs of Stations:

To recreate the graph, run the following query against an empty Neo4j database:

The following query finds the path length and total distance for ALL SHORTEST paths between London Blackfriars to North Dulwich:

ALL SHORTEST finds all shortest paths by number of hops, and as the result shows, there are two paths in the graph tied for the shortest path. Whether any of these paths corresponds to the shortest path by distance can be checked by looking at each path between the two end Stations and returning the first result after ordering by distance:

This shows that there is a route with a shorter distance than either of the paths with fewer Stations returned using ALL SHORTEST. But to get this result, the query had to first find all paths from London Blackfriars to North Dulwich before it could select the shortest one. The following query shows the number of possible paths:

For a small dataset like this, finding all the paths will be fast. But as the size of the graph grows, the execution time will increase exponentially. For a real dataset, such as the entire rail network of the UK, it might be unacceptably long.

One approach to avoid the exponential explosion in paths is to put a finite upper bound to the quantified path pattern (e.g. {,10}) to limit the amount of path iterations returned. This works fine where the solution is known to lie within some range of hops. But in cases where this is not known, one alternative would be to make the pattern more specific by, for example, adding node labels, or by specifying a relationship direction. Another alternative would be to add an inline predicate to the quantified path pattern.

In this example, an inline predicate can be added that takes advantage of the geospatial location property of the Stations: for each pair of Stations on the path, the second Station will be closer to the endpoint (not always true, but is assumed here to keep the example simple). To compose the predicate, the point.distance() function is used to compare the distance between the left-hand Station (a) and the right-hand Station (b) for each node-pair along the path to the destination North Dulwich:

This query avoids having to find all possible paths and then imposing a LIMIT 1 to find the shortest one by distance. It also shows that there is only one path to solving the query (a number that remains constant even if the data from the rest of the UK railway network was included). Using inline predicates or making quantified path patterns more specific where possible can thus greatly improve query performance.