Non-linear patterns

An equijoin is an operation on paths that requires more than one of the nodes or relationships of the paths to be the same. The equality between the nodes or relationships is specified by declaring the same variable in multiple node patterns or relationship patterns. An equijoin allows cycles to be specified in a path pattern.

This section uses the following graph:

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

To illustrate how equijoins work, we will use the problem of finding a round trip between two Stations.

In this example scenario, a passenger starts their outbound journey at London Euston Station and ends at Coventry Station. The return journey will be the reverse order of those Stations.

The graph has three different services, two of which would compose the desired round trip, and a third which would send the passenger to Birmingham International.

The solution is the following path with a cycle:

If unique properties exist on the node where the cycle "join" occurs in the path, then it is possible to repeat the node pattern with a predicate matching on the unique property. The following motif demonstrates how that can be achieved, repeating a Station node pattern with the name London Euston:

The path pattern equivalent is:

There may be cases where a unique predicate is not available. In this case, an equijoin can be used to define the desired cycle by using a repeated node variable. In the current example, if you declare the same node variable n in both the first and last node patterns, then the node patterns must match the same node:

Putting this path pattern with an equijoin in a query, the times of the outbound and return journeys can be returned:

In addition to the single path patterns, multiple path patterns can be combined in a comma-separated list to form a graph pattern. In a graph pattern, each path pattern is matched separately, and where node variables are repeated in the separate path patterns, the solutions are reduced via equijoins. If there are no equijoins between the path patterns, the result is a Cartesian product between the separate solutions.

The benefit of joining multiple path patterns in this way is that it allows the specification of more complex patterns than the linear paths allowed by a single path pattern. To illustrate this, another example drawn from the railway model will be used. In this example, a passenger is traveling from Starbeck to Huddersfield, changing trains at Leeds. To get to Leeds from Starbeck, the passenger can take a direct service that stops at all stations on the way. However, there is an opportunity to change at one of the stations (Harrogate) on the way to Leeds, and catch an express train, which may enable the passenger to catch an earlier train leaving from Leeds, reducing the overall journey time.

This section uses the following graph, showing the train services the passenger can use:

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

The solution to the problem assembles a set of path patterns matching the following three parts: the stopping service; the express service; and the final leg of the journey from Leeds to Huddersfield. Each changeover, from stopping to express service and from express to onward service, has to respect the fact that the arrival time of a previous leg has to be before the departure time of the next leg. This will be encoded in a single WHERE clause.

The following visualizes the three legs with different colors, and identifies the node variables used to create the equijoins and anchoring:

For the stopping service, it is assumed that the station the passenger needs to change at is unknown. As a result, the pattern needs to match a variable number of stops before and after the Stop b, the Stop that calls at the changeover station l. This is achieved by placing the quantified relationship -[:NEXT]->* on each side of node b. The ends of the path also needs to be anchored at a Stop departing from Starbeck at 11:11, as well as at a Stop calling at Leeds:

For the express service, the ends of the path are anchored at the stop b and Leeds station, which lds will be bound to by the first leg. Although in this particular case there are only two stops on the service, a more general pattern that can match any number of stops is used:

Note that as Cypher only allows a relationship to be traversed once in a given match for a graph pattern, the first and second legs are guaranteed to be different train services. (See relationship uniqueness for more details.) Similarly, another quantified relationship that bridges the stops calling at Leeds station and Huddersfield station is added:

The other node variables are for the WHERE clause or for returning data. Putting this together, the resulting query returns the earliest arrival time achieved by switching to an express service: