Add support for ranked answers through flexible path querying of RPQs

[petraselmer]

CIR-2017-186

It would be useful to add the notion of query approximation to Cypher. This is particularly relevant when the underlying data is complex, and the user either is not familiar with the underlying graph, or wishes to gain further insights into the data.

A prerequisite would be the inception of Regular Path Queries (RPQs) into Cypher, as detailed in CIR-2017-179.

In this context, query approximation when applied to RPQs extends the idea of regular expression matching by including a set of edit operations - enumerated below - that may be applied to the relationship types making up the language of the regular expression.

Let R be the regular expression in the path pattern, and let A be the alphabet of all relationship types in the graph. The proposed edit operations include:

• inserting a relationship type r (taken from A) into R

• deleting a relationship type from R

• substituting a relationship type r in R with another relationship type r' (taken from A) where r <> r'

Each edit operation has an associated configurable cost, which is some integer >= 0.

Each application of an edit operation to a sequence of relationship types in the language of R increases the 'distance' from the original sequence by the cost configured for the edit operation.

Answers obtained at greater distances are ranked lower than ones exactly matching R, as well as those obtained at a smaller distance. Therefore, exact answers are returned first, followed by answers corresponding to ever-increasing distances.

It is advisable that these queries are provided with a limit, or maximum distance, in order to not return the whole graph.

Examples

Assume R = a*.b.c, and assume A = {a, b, c, d} (the set of all relationship types in the graph).

Insertion operation (assume a cost of 1)

• d can be inserted between b and c to form R' = a*.b.d.c at a cost of 1. So, all answers would be returned at a distance of 1, after the answers for R.

• b can be inserted before a in R', giving rise to R'' = b.a*.b.d.c at a cost of 1, yielding a total cost of 2. This means all answers to R'' would be returned at a distance of 2, after the answers for R' and R.

Deletion operation (assume a cost of 1)

• c can be deleted from R to give rise to R' = a*.b at a cost of 1. All answers would be returned at a distance of 1, after the answers for R.

• Note that removing a from R would have no effect owing to the presence of the Kleene operator.

Substitution operation (assume a cost of 1)

• a can be substituted with d giving rise to the following variants (owing to the Kleene operator): d.a*.b.c, a*.d.b.c, a*.d.a*.b.c, all at a cost of 1.

Insertion & substitution operations (assume a cost of 1 for insertion, and 2 for deletion)

• d is inserted between b and c to form R' = a*.b.d.c at a cost of 1

• c substituted by a in R' to form R'' = a*.b.d.a at a cost of 2

• Therefore, answers corresponding to R'' will be returned at a distance of 3

[thobe]

If we end up with the syntax proposed in CIP2017-02-06 for Regular Path Queries, we might be able to extend this syntax to mean approximate matching as described here by using ~ instead of - in the path patterns:

MATCH (a)~/:FOO :BAR :BAZ/~>(b)