Neo4j and Cypher: Match nodes that have a single relationship to a target node

Question

I'm trying to identify nodes that have only one relationship of a given type.

Imagine a graph of Route and Stop nodes. A Route may have 0 or more Stops, a Stop may be shared between multiple Routes, a Stop must always have at least 1 Route. I want to match and delete Stops that will be orphaned if a given Route is deleted.

Before anyone says anything, I know that it would be easier to just find stops without routes after the route is deleted, but that isn't an option. We're also not worried about deleting the routes here, just the stops.

Here's my query:

MATCH (r1:Route { id: {route_id} })-[rel1:HAS_STOP]->(s:Stop)
MATCH (r2:Route)-[rel2:HAS_STOP]->(s)
WITH s, COUNT(rel2) as c
WHERE c = 1
MATCH s-[rel2]-()
DELETE s, rel2

This works perfectly... but is there a better way? It feels like it could be more efficient but I'm not sure how.

Christophe Willemsen Christophe Willemsen · Accepted Answer · 2014-12-29T13:21:30

EDIT

Here a query that matches only the nodes that will be orphaned without deleting the current route :

MATCH (route:Route {id:'99e08bdf-130f-3fca-8292-27d616fa025f'})
WITH route
OPTIONAL MATCH (route)-[r:HAS_STOP]->(s)
WHERE NOT EXISTS((route)--(s)<-[:HAS_STOP]-())
DELETE r,s

and the execution plan :

neo4j-sh (?)$ PROFILE MATCH (route:Route {id:'99e08bdf-130f-3fca-8292-27d616fa025f'})
> WITH route
> OPTIONAL MATCH (route)-[r:HAS_STOP]->(s)
> WHERE NOT EXISTS((route)--(s)<-[:HAS_STOP]-())
> DELETE r,s;
+-------------------+
| No data returned. |
+-------------------+
Nodes deleted: 2
Relationships deleted: 2

EmptyResult
  |
  +UpdateGraph
    |
    +Eager
      |
      +OptionalMatch
        |
        +SchemaIndex(1)
        |
        +Filter
           |
           +SimplePatternMatcher
             |
             +SchemaIndex(1)

+----------------------+------+--------+--------------+----------------------------------------------------------------------------------------------------+
|             Operator | Rows | DbHits |  Identifiers |                                                                                              Other |
+----------------------+------+--------+--------------+----------------------------------------------------------------------------------------------------+
|          EmptyResult |    0 |      0 |              |                                                                                                    |
|          UpdateGraph |    2 |      4 |              |                                                                         DeleteEntity; DeleteEntity |
|                Eager |    2 |      0 |              |                                                                                                    |
|        OptionalMatch |    2 |      0 |              |                                                                                                    |
|       SchemaIndex(1) |    1 |      2 | route, route |                                                                        {  AUTOSTRING0}; :Route(id) |
|               Filter |    2 |      0 |              | NOT(nonEmpty(PathExpression((route)-[  UNNAMED140]-(s),(160)-[  UNNAMED145:HAS_STOP]->(s), true))) |
| SimplePatternMatcher |    2 |      0 |  route, s, r |                                                                                                    |
|       SchemaIndex(1) |    1 |      2 | route, route |                                                                        {  AUTOSTRING0}; :Route(id) |
+----------------------+------+--------+--------------+----------------------------------------------------------------------------------------------------+

Total database accesses: 8

** OLD ANSWER **

I let it here for helping maybe others :

In your query, you're not deleting the route nor the relationships to the stops that will not be orphaned. You can do all in one go.

This is what I have as query for the same use case than you, I also compared the two execution plans on a test graph, each route has about 160 stops and 2 stops that will be orphaned after the route deletion, the graph is available here : http://graphgen.neoxygen.io/?graph=JPnvQWZcQW685m

My query :

MATCH (route:Route {id:'e70ea0d4-03e2-3ca4-afc0-dfdc1754868e'})
WITH route
MATCH (route)-[r:HAS_STOP]->(s)
WITH r, collect(s) as stops
DELETE r, route
WITH filter(x in stops WHERE NOT x--()) as orphans
UNWIND orphans as orphan
DELETE orphan

Here is my profiled query :

       neo4j-sh (?)$ PROFILE MATCH (route:Route {id:'1c565ac4-b72b-37c3-be7f-a38f2a7f66a8'})
> WITH route
> MATCH (route)-[r:HAS_STOP]->(s)
> WITH route, r, collect(s) as stops
> DELETE r, route
> WITH filter(x in stops WHERE NOT x--()) as orphans
> UNWIND orphans as orphan
> DELETE orphan;
+-------------------+
| No data returned. |
+-------------------+
Nodes deleted: 2
Relationships deleted: 157

EmptyResult
  |
  +UpdateGraph(0)
    |
    +UNWIND
      |
      +ColumnFilter(0)
        |
        +Eager
          |
          +Extract
            |
            +UpdateGraph(1)
              |
              +ColumnFilter(1)
                |
                +EagerAggregation
                  |
                  +SimplePatternMatcher
                    |
                    +SchemaIndex

+----------------------+------+--------+--------------+------------------------------+
|             Operator | Rows | DbHits |  Identifiers |                        Other |
+----------------------+------+--------+--------------+------------------------------+
|          EmptyResult |    0 |      0 |              |                              |
|       UpdateGraph(0) |    1 |      1 |              |                 DeleteEntity |
|               UNWIND |    1 |      0 |              |                              |
|      ColumnFilter(0) |  157 |      0 |              |         keep columns orphans |
|                Eager |  157 |      0 |              |                              |
|              Extract |  157 |      0 |              |                      orphans |
|       UpdateGraph(1) |  157 |    158 |              |   DeleteEntity; DeleteEntity |
|      ColumnFilter(1) |  157 |      0 |              | keep columns route, r, stops |
|     EagerAggregation |  157 |      0 |              |                     route, r |
| SimplePatternMatcher |  157 |      0 |  route, s, r |                              |
|          SchemaIndex |    1 |      2 | route, route |  {  AUTOSTRING0}; :Route(id) |
+----------------------+------+--------+--------------+------------------------------+

Total database accesses: 161

With your query :

I slightly modified your query to make use of schema indexes

And this is the Execution plan with your query, the difference in db accesses is quite high

PROFILE MATCH (r1:Route { id: '1c565ac4-b72b-37c3-be7f-a38f2a7f66a8' })
> WITH r1
> MATCH (r1)-[rel1:HAS_STOP]->(s:Stop)
> MATCH (r2:Route)-[rel2:HAS_STOP]->(s)
> WITH s, COUNT(rel2) as c
> WHERE c = 1
> MATCH s-[rel2]-()
> DELETE s, rel2;
+-------------------+
| No data returned. |
+-------------------+
Nodes deleted: 1
Relationships deleted: 1

EmptyResult
  |
  +UpdateGraph
    |
    +Eager
      |
      +SimplePatternMatcher(0)
        |
        +Filter(0)
          |
          +ColumnFilter
            |
            +EagerAggregation
              |
              +Filter(1)
                |
                +SimplePatternMatcher(1)
                  |
                  +Filter(2)
                    |
                    +SimplePatternMatcher(2)
                      |
                      +SchemaIndex

+-------------------------+------+--------+-----------------------+-----------------------------+
|                Operator | Rows | DbHits |           Identifiers |                       Other |
+-------------------------+------+--------+-----------------------+-----------------------------+
|             EmptyResult |    0 |      0 |                       |                             |
|             UpdateGraph |    1 |      2 |                       |  DeleteEntity; DeleteEntity |
|                   Eager |    1 |      0 |                       |                             |
| SimplePatternMatcher(0) |    1 |      0 |   UNNAMED200, s, rel2 |                             |
|               Filter(0) |    1 |      0 |                       |           c == {  AUTOINT1} |
|            ColumnFilter |  157 |      0 |                       |           keep columns s, c |
|        EagerAggregation |  157 |      0 |                       |                           s |
|               Filter(1) | 4797 |   4797 |                       |       hasLabel(r2:Route(4)) |
| SimplePatternMatcher(1) | 4797 |   4797 |           r2, s, rel2 |                             |
|               Filter(2) |  157 |    157 |                       |         hasLabel(s:Stop(3)) |
| SimplePatternMatcher(2) |  157 |    157 |           r1, s, rel1 |                             |
|             SchemaIndex |    1 |      2 |                r1, r1 | {  AUTOSTRING0}; :Route(id) |
+-------------------------+------+--------+-----------------------+-----------------------------+

Total database accesses: 9912

Neo4j and Cypher: Match nodes that have a single relationship to a target node

1 Answers