6.13. A multilevel indexing structure (path tree)

In this example, a multi-level tree structure is used to index event nodes (here Event1, Event2 and Event3, in this case with a YEAR-MONTH-DAY granularity, making this a timeline indexing structure. However, this approach should work for a wide range of multi-level ranges.

The structure follows a couple of rules:

  • Events can be indexed multiple times by connecting the indexing structure leafs with the events via a VALUE relationship.
  • The querying is done in a path-range fashion. That is, the start- and end path from the indexing root to the start and end leafs in the tree are calculated
  • Using Cypher, the queries following different strategies can be expressed as path sections and put together using one single query.

The graph below depicts a structure with 3 Events being attached to an index structure at different leafs.

Figure 6.15. Graph

cypher-pathtree-layout-path.svg

Return zero range

Here, only the events indexed under one leaf (2010-12-31) are returned. The query only needs one path segment rootPath (color Green) through the index.

Figure 6.16. Graph

cypher-pathtree-layout-zero-range.svg

Query  

MATCH rootPath=(root)-[:`2010`]->()-[:`12`]->()-[:`31`]->(leaf),(leaf)-[:VALUE]->(event)
WHERE root.name = 'Root'
RETURN event.name
ORDER BY event.name ASC

Returning all events on the date 2010-12-31, in this case Event1 and Event2

Result

event.name
2 rows

"Event1"

"Event2"

Try this query live create (_0 {`name`:"Y10M12D31"}) create (_1 {`name`:"Root"}) create (_2 {`name`:"Event2"}) create (_3 {`name`:"Event3"}) create (_4 {`name`:"Y11M01D01"}) create (_5 {`name`:"Y11M11D02"}) create (_6 {`name`:"Y11M12D03"}) create (_7 {`name`:"Y11"}) create (_8 {`name`:"Y10"}) create (_9 {`name`:"Event1"}) create (_10 {`name`:"Y11M01"}) create (_11 {`name`:"Y10M12"}) create (_0)-[:`VALUE`]->(_2) create (_0)-[:`VALUE`]->(_9) create (_0)-[:`NEXT`]->(_4) create (_1)-[:`2011`]->(_7) create (_1)-[:`2010`]->(_8) create (_4)-[:`VALUE`]->(_2) create (_4)-[:`NEXT`]->(_5) create (_5)-[:`NEXT`]->(_6) create (_6)-[:`VALUE`]->(_3) create (_7)-[:`01`]->(_10) create (_8)-[:`12`]->(_11) create (_10)-[:`03`]->(_6) create (_10)-[:`02`]->(_5) create (_10)-[:`01`]->(_4) create (_11)-[:`31`]->(_0) ; MATCH rootPath=(root)-[:`2010`]->()-[:`12`]->()-[:`31`]->(leaf), (leaf)-[:VALUE]->(event) WHERE root.name = 'Root'RETURN event.name ORDER BY event.name ASC

Return the full range

In this case, the range goes from the first to the last leaf of the index tree. Here, startPath (color Greenyellow) and endPath (color Green) span up the range, valuePath (color Blue) is then connecting the leafs, and the values can be read from the middle node, hanging off the values (color Red) path.

Figure 6.17. Graph

cypher-pathtree-layout-full-range-path.svg

Query  

MATCH startPath=(root)-[:`2010`]->()-[:`12`]->()-[:`31`]->(startLeaf),
  endPath=(root)-[:`2011`]->()-[:`01`]->()-[:`03`]->(endLeaf),
  valuePath=(startLeaf)-[:NEXT*0..]->(middle)-[:NEXT*0..]->(endLeaf),
  vals=(middle)-[:VALUE]->(event)
WHERE root.name = 'Root'
RETURN event.name
ORDER BY event.name ASC

Returning all events between 2010-12-31 and 2011-01-03, in this case all events.

Result

event.name
4 rows

"Event1"

"Event2"

"Event2"

"Event3"

Try this query live create (_0 {`name`:"Y10M12D31"}) create (_1 {`name`:"Root"}) create (_2 {`name`:"Event2"}) create (_3 {`name`:"Event3"}) create (_4 {`name`:"Y11M01D01"}) create (_5 {`name`:"Y11M11D02"}) create (_6 {`name`:"Y11M12D03"}) create (_7 {`name`:"Y11"}) create (_8 {`name`:"Y10"}) create (_9 {`name`:"Event1"}) create (_10 {`name`:"Y11M01"}) create (_11 {`name`:"Y10M12"}) create (_0)-[:`VALUE`]->(_2) create (_0)-[:`VALUE`]->(_9) create (_0)-[:`NEXT`]->(_4) create (_1)-[:`2011`]->(_7) create (_1)-[:`2010`]->(_8) create (_4)-[:`VALUE`]->(_2) create (_4)-[:`NEXT`]->(_5) create (_5)-[:`NEXT`]->(_6) create (_6)-[:`VALUE`]->(_3) create (_7)-[:`01`]->(_10) create (_8)-[:`12`]->(_11) create (_10)-[:`03`]->(_6) create (_10)-[:`02`]->(_5) create (_10)-[:`01`]->(_4) create (_11)-[:`31`]->(_0) ; MATCH startPath=(root)-[:`2010`]->()-[:`12`]->()-[:`31`]->(startLeaf), endPath=(root)-[:`2011`]->()-[:`01`]->()-[:`03`]->(endLeaf), valuePath=(startLeaf)-[:NEXT*0..]->(middle)-[:NEXT*0..]->(endLeaf), vals=(middle)-[:VALUE]->(event) WHERE root.name = 'Root'RETURN event.name ORDER BY event.name ASC

Return partly shared path ranges

Here, the query range results in partly shared paths when querying the index, making the introduction of and common path segment commonPath (color Black) necessary, before spanning up startPath (color Greenyellow) and endPath (color Darkgreen) . After that, valuePath (color Blue) connects the leafs and the indexed values are returned off values (color Red) path.

Figure 6.18. Graph

cypher-pathtree-layout-shared-root-path.svg

Query  

MATCH commonPath=(root)-[:`2011`]->()-[:`01`]->(commonRootEnd),
  startPath=(commonRootEnd)-[:`01`]->(startLeaf), endPath=(commonRootEnd)-[:`03`]->(endLeaf),
  valuePath=(startLeaf)-[:NEXT*0..]->(middle)-[:NEXT*0..]->(endLeaf),
  vals=(middle)-[:VALUE]->(event)
WHERE root.name = 'Root'
RETURN event.name
ORDER BY event.name ASC

Returning all events between 2011-01-01 and 2011-01-03, in this case Event2 and Event3.

Result

event.name
2 rows

"Event2"

"Event3"

Try this query live create (_0 {`name`:"Y10M12D31"}) create (_1 {`name`:"Root"}) create (_2 {`name`:"Event2"}) create (_3 {`name`:"Event3"}) create (_4 {`name`:"Y11M01D01"}) create (_5 {`name`:"Y11M11D02"}) create (_6 {`name`:"Y11M12D03"}) create (_7 {`name`:"Y11"}) create (_8 {`name`:"Y10"}) create (_9 {`name`:"Event1"}) create (_10 {`name`:"Y11M01"}) create (_11 {`name`:"Y10M12"}) create (_0)-[:`VALUE`]->(_2) create (_0)-[:`VALUE`]->(_9) create (_0)-[:`NEXT`]->(_4) create (_1)-[:`2011`]->(_7) create (_1)-[:`2010`]->(_8) create (_4)-[:`VALUE`]->(_2) create (_4)-[:`NEXT`]->(_5) create (_5)-[:`NEXT`]->(_6) create (_6)-[:`VALUE`]->(_3) create (_7)-[:`01`]->(_10) create (_8)-[:`12`]->(_11) create (_10)-[:`03`]->(_6) create (_10)-[:`02`]->(_5) create (_10)-[:`01`]->(_4) create (_11)-[:`31`]->(_0) ; MATCH commonPath=(root)-[:`2011`]->()-[:`01`]->(commonRootEnd), startPath=(commonRootEnd)-[:`01`]->(startLeaf), endPath=(commonRootEnd)-[:`03`]->(endLeaf), valuePath=(startLeaf)-[:NEXT*0..]->(middle)-[:NEXT*0..]->(endLeaf), vals=(middle)-[:VALUE]->(event) WHERE root.name = 'Root'RETURN event.name ORDER BY event.name ASC