Path Search

The set of paths matching a pattern can be restricted using some path search prefix. For example, consider the graph example from LDBC: the path pattern (:Forum) →+ (:Tag) can match paths connecting a forum directly to a tag via the hasTag relation; other paths via a person entity through relations hasModerator and hasInterest are also returned. When the graph structure is not known, a path search prefix can help limit what paths get returned by a query.

Currently, the graph API only supports the following path search:

ALL SHORTEST: This returns all paths matching a pattern that have the smallest length in terms of number of edges.

For the example pattern (:Forum) →+ (:Tag) this would return only paths connecting those two entities directly, if such entities do exist in the graph. Otherwise, the graph API will try finding paths with increasing length until one is found, and then return all that have that same length.

Usage

Each path pattern of the GQL query can specify a path search.

SELECT p
FROM "ldbc-snb"
MATCH p = ALL SHORTEST (:Forum) ->+ (:Tag) (1)

1	This matches only the shortest paths — with length in terms of number of edges — between a forum to a tag. Longer possible paths that can be matched due to the quantifier `+` are not returned if a shorter pattern is found.

Known Limitations

Contrary to the ISO standard, our ALL SHORTEST implementation does not return pairwise shortest paths. The key word is pariwise: we do not check all pairs of entities for the shortest path connecting them, but only return the shortest paths from all pairs.

Consider the following entities based on the graph data model of the LDBC SNB example. Executing the query would return only the path from Tolkien to Fantasy (with length 1) — even if a shortest path for the pair Pohl and Horror was not found.

┌──────────────┐               ┌─────────────┐
│  Forum       │               │  Tag        │
│id: 1         ├──hasTag──────►│id: 1        │
│title: Tolkien│               │name: Fantasy│
└──────────────┘               └─────────────┘

 ┌───────────┐                  ┌────────────────┐                 ┌────────────┐
 │  Forum    │                  │  Person        │                 │  Tag       │
 │id: 2      ├───hasModerator──►│id: 1           ├───hasInterest──►│id: 2       │
 │title: Pohl│                  │firstName: Alice│                 │name: Horror│
 └───────────┘                  └────────────────┘                 └────────────┘