Neo4J path subquery for versioned nodes

Question

example graph (sorry you need to click the image)

I have a graph with two kinds of nodes:

• identity-nodes as structural elements (blue) holding no attributes
• versioned value-nodes which hold attributes/data (orange)

There are two relation kinds:

• version-of: connects value-nodes to identity-nodes and contains a window within which the relation shall be valid (picture shows just a start date)
• parent-of: connects identity-nodes in a hierarchical fashion

Scenario:

• There is at most one valid value-node per identity-node at any given time.
• I want to keep historical values and look back any time, so copying the values that are currently valid to the respective identity-nodes will not work.
• Hierarchy can be of arbitrary depth, say 1 to 10.
• I wan't to search using fully qualified paths-strings from root to leaf using an attribute of a value-node.
• I want to find the path along ID nodes as well as the right value-of at the end of the path. (Think of a file-system directory path.)

In this example I'm searching for a path "A/CD/E" where A CD E are values of the name property of value-nodes. Basically I want to find the right 'E' node, here the one that is associated to 98. Time is ommited from the examples below to keep them short.

How do I do that? Is that even possible using only Neo4J? (It's easily done wrapping the query in another script that generates a path match including a named id node for each path entry.)

I can query for start and end of the path to limit the search space, but what about a variable number of nodes in between? In a manner of thinking ID nodes would have to be merged with their values matching the time window on the version-of relation before each query.

MATCH p=(start:value) -[:`version-of`]-> (:ID) <-[:`parent-of`*]- (:ID) <-[:`version-of`]- (end:value)
WHERE start.name = 'A' AND end.name = 'E'
RETURN p

What I would like to ask (using variable depth keys instead of the short example); the following is not valid cypher:

MATCH p=(start:value) -[:`version-of`]-> (:ID) <-[:`parent-of`*]- (:ID) <-[:`version-of`]- (end:value)
WHERE p = 'A/CD/E' // or something longer, "A/CD/E/F/X"
RETURN p, end

What I've looked at so far

I can also build the list of names along the path and compare the full paths against the query string. But it can't get the name value for the nodes between start and end:

MATCH p=(start:value) -[:`version-of`]-> (:ID) <-[:`parent-of`*]- (:ID) <-[:`version-of`]- (end:value)
WHERE start.name = 'A' AND end.name = 'E'
RETURN EXTRACT(n in nodes(p)|n['name'])

Subgraph relevant for the query in pairs, but missing the path. Can I get a path of id,val pairs here somehow?

MATCH p=(start:value) -[:`version-of`]-> (:ID) <-[:`parent-of`*]- (:ID) <-[:`version-of`]- (end:value)
WHERE start.name = 'A' AND end.name = 'E'
UNWIND nodes(p) as id
MATCH (id) <-[:`version-of`]- (val)
RETURN COLLECT([id,val])

Here's the graph

MATCH (n) DETACH DELETE n
CREATE (:value {name:'A'}) -[:`version-of` {from:'2017-01-01'}]-> (:ID {id:32})
CREATE (:value {name:'CC'}) -[:`version-of` {from:'2017-01-05'}]-> (:ID {id:21})
CREATE (:value {name:'E'}) -[:`version-of` {from:'2017-02-01'}]-> (:ID {id:98})
CREATE (:value {name:'E'}) -[:`version-of` {from:'2017-02-01'}]-> (:ID {id:48})
MATCH (n:ID {id:21}) CREATE (:value {name:'CD'}) -[:`version-of` {from:'2017-03-01'}]-> (n)
MATCH (a:ID {id:32}),(b:ID {id:21}) CREATE (a)<-[:`parent-of`]-(b)
MATCH (a:ID {id:21}),(b:ID {id:98}) CREATE (a)<-[:`parent-of`]-(b)
MATCH (a:ID {id:32}),(b:ID {id:48}) CREATE (a)<-[:`parent-of`]-(b)

Answer 1

You're very close!

Your last query, with the id/val pairs, is missing the path because you're collecting without any context:

RETURN COLLECT([id,val])

This is just asking for one single collection of id/val pairs. If you want the collection of id/val pairs for each path, you need to have the path variable p as a non-aggregation field, which will act as a grouping key for your aggregation:

WITH p, COLLECT([id,val]) as pairs  // one collection per path
RETURN pairs

As for making sure CD is in the path, we need to find CD's :ID node, and add a predicate to ensure that this node is on the path:

MATCH (:value{name:'CD'})-[:`version-of`]->(cdID:ID)
MATCH p=(start:value) -[:`version-of`]-> (:ID) <-[:`parent-of`*]- (:ID) <-[:`version-of`]- (end:value)
WHERE start.name = 'A' AND end.name = 'E' AND cdID in nodes(p)
UNWIND nodes(p)[1..-1] as id
MATCH (id) <-[:`version-of`]- (val)
WITH p, COLLECT([id,val]) as pairs
RETURN pairs

EDIT

Clarified requirements now include specifying the names of :value nodes associated with whichever :IDs should be along the path, presumably in order.

Let's see if this one will work. I'll use your existing graph (removing the duplicate E-for-id-48 line), and just for this example we'll omit the direction of the :parent-of relationship, since with the existing direction we don't have enough nodes to have more than one element in the intermediate path. Let's go from E to E, requiring the IDs for the following value nodes in order: 'E', 'A', 'CD', 'E'. With our graph we expect to get a single path of the following :IDs associated with the value names: 48, 32, 21, 98

This is going to be a complex query, as dealing with indices isn't so straight forward in Cypher. It's also a query where we filter all possible paths, as I can't see a way to filter during expansion:

WITH ['E', 'A', 'CD', 'E'] as names
UNWIND RANGE(0, SIZE(names)-1) as index
WITH index, names[index] as name
// each name with its expected index in the path

MATCH (:value{name:name})-[:`version-of`]->(id:ID)
WITH index, name, COLLECT(id) as ids
ORDER BY index ASC
WITH COLLECT({name:name, ids:ids}) as pathdef
// index-order collection of expected name and possible IDs for the name

MATCH p=(start:value) -[:`version-of`]-> (:ID) -[:`parent-of`*]- (:ID) <-[:`version-of`]- (end:value)
WHERE start.name = 'E' AND end.name = 'E' AND LENGTH(p)-1 = SIZE(pathdef)
// we have all paths from E to E of the desired length

// only interested in :ID nodes in match, leave off :value nodes at end
WITH pathdef, NODES(p)[1..-1] as nodes, RANGE(0, SIZE(pathdef)-1) as indices
// due to our match from start and end values, don't need to check start/end :ID nodes
WHERE ALL(index in indices[1..-1] WHERE nodes[index] in pathdef[index].ids)
// we've filtered to only path nodes associated with values in expected order
UNWIND indices as index
RETURN COLLECT([nodes[index], pathdef[index].name]) as pairs

Answer 2

MATCH (n) DETACH DELETE n;
CREATE (:value {name:'A'}) -[:`version-of` {from:'2017-01-01'}]-> (:ID {id:32});
CREATE (:value {name:'CC'}) -[:`version-of` {from:'2017-01-05'}]-> (:ID {id:21});
CREATE (:value {name:'E'}) -[:`version-of` {from:'2017-02-01'}]-> (:ID {id:98});
CREATE (:value {name:'N'}) -[:`version-of` {from:'2017-02-01'}]-> (:ID {id:87});
CREATE (:value {name:'E'}) -[:`version-of` {from:'2017-02-01'}]-> (:ID {id:48});
CREATE (:value {name:'W'}) -[:`version-of` {from:'2017-02-01'}]-> (:ID {id:74});
CREATE (:value {name:'E'}) -[:`version-of` {from:'2017-01-01'}]-> (:ID {id:75});
MATCH (n:ID {id:21}) CREATE (:value {name:'CD'}) -[:`version-of` {from:'2017-03-01'}]-> (n);
MATCH (a:ID {id:32}),(b:ID {id:21}) CREATE (a)<-[:`parent-of`]-(b);
MATCH (a:ID {id:32}),(b:ID {id:23}) CREATE (a)<-[:`parent-of`]-(b);
MATCH (a:ID {id:32}),(b:ID {id:48}) CREATE (a)<-[:`parent-of`]-(b);
MATCH (a:ID {id:48}),(b:ID {id:87}) CREATE (a)<-[:`parent-of`]-(b);
MATCH (a:ID {id:87}),(b:ID {id:98}) CREATE (a)<-[:`parent-of`]-(b);
MATCH (a:ID {id:21}),(b:ID {id:74}) CREATE (a)<-[:`parent-of`]-(b);
MATCH (a:ID {id:74}),(b:ID {id:75}) CREATE (a)<-[:`parent-of`]-(b);

a more exiting example-graph to test on (solution above works here, too)