How to verify that specific paths do not exist in cypher query

Question

I would like to get nodes, which do no have a specific relation (a relation with specific properties).

The graph contains entity nodes (the n's), which occur at specific lines (line_nr) in files (the f).

The current query I have is as follows:

start n=node:entities("text:*")
MATCH p=(n)-[left:OCCURS]->(f) 
    , p4=(f)<-[right4?:OCCURS]-(n4) 
    , p7=(f)<-[right7?:OCCURS]-(n7)
WHERE  (  (  
   ( n4.text? =~ "nonreachablenodestextregex" AND (p4 = null OR left.line_nr < right4.line_nr - 0 OR left.line_nr > right4.line_nr + 0 OR ID(left) = ID(right4)  )  )  )  
   AND  (  
   ( n7.text? =~ "othernonreachablenodestextregex" AND (p7 = null OR left.line_nr < right7.line_nr - 0 OR left.line_nr > right7.line_nr + 0 OR ID(left) = ID(right7)  )  )  )  )  
WITH n, left, f, count(*) as group_by_cause 
RETURN ID(left) as occ_id, 
       n.text as ent_text, 
       substring(f.text, ABS(left.file_offset-1), 2 + LENGTH(n.text) ) as occ_text, 
       f.path as file_path, 
       left.line_nr as occ_line_nr, 
       ID(f) as file_id

Instead of a new path in the MATCH clause, I thought it would also be possible to have:

NOT ( (f)<-[right4:OCCURS]-(n4) )

But, I do not want to exclude the existence of any path, but specific paths.

As an alternative solution, I thought to include additional start nodes (as I have an index on the not to be reachable node), to remove the text comparison in the WHERE clause. This however doesn't return anything if there are no nodes in neo4j matching the wildcard.

start n=node:entities("text:*")
    , n4=node:entities("text:nonreachablenodestextwildcard")
    , n7=node:entities("text:othernonreachablenodestextwildcard")
MATCH p=(n)-[left:OCCURS]->(f) 
    , p4=(f)<-[right4?:OCCURS]-(n4) 
    , p7=(f)<-[right7?:OCCURS]-(n7)
WHERE  (  (  
   ( (p4 = null 
      OR left.line_nr < right4.line_nr - 0 
      OR left.line_nr > right4.line_nr + 0 
      OR ID(left) = ID(right4)  )  )  )  
   AND  (  
   ( (p7 = null 
      OR left.line_nr < right7.line_nr - 0 
      OR left.line_nr > right7.line_nr + 0 
      OR ID(left) = ID(right7)  )  ) 
)  )

Old Update: As mentioned in the answers, I could use the predicate functions to construct an inner query. I therefore updated the query to:

start n=node:entities("text:*") 
MATCH p=(n)-[left:OCCURS]->(f) 
WHERE  (  (  
    (NONE(path in (f)<-[:OCCURS]-(n4) 
         WHERE  
           (LAST(nodes(path))).text =~ "nonreachablenodestextRegex"  
           AND FIRST(r4 in rels(p)).line_nr <= left.line_nr  
           AND FIRST(r4 in rels(p)).line_nr >= left.line_nr 
    )
    ) )  
    AND  (  
   (NONE(path in (f)<-[:OCCURS]-(n7) 
         WHERE  
           (LAST(nodes(path))).text =~ "othernonreachablenodestextRegex"  
           AND FIRST(r7 in rels(p)).line_nr <= left.line_nr   
           AND FIRST(r7 in rels(p)).line_nr >= left.line_nr 
    )
    ) ) 
    )
WITH n, left, f, count(*) as group_by_cause 
RETURN ....

This gives me an java.lang.OutOfMemoryException :

java.lang.OutOfMemoryError: Java heap space
at java.util.regex.Pattern.compile(Pattern.java:1432)
at java.util.regex.Pattern.<init>(Pattern.java:1133)
at java.util.regex.Pattern.compile(Pattern.java:823)
at scala.util.matching.Regex.<init>(Regex.scala:38)
at scala.collection.immutable.StringLike$class.r(StringLike.scala:226)
at scala.collection.immutable.StringOps.r(StringOps.scala:31)
at org.neo4j.cypher.internal.parser.v1_9.Base.ignoreCase(Base.scala:31)
at org.neo4j.cypher.internal.parser.v1_9.Base.ignoreCases(Base.scala:49)
at org.neo4j.cypher.internal.parser.v1_9.Base$$anonfun$ignoreCases$1.apply(Base.scala:49)
at org.neo4j.cypher.internal.parser.v1_9.Base$$anonfun$ignoreCases$1.apply(Base.scala:49)
at scala.util.parsing.combinator.Parsers$Parser.p$3(Parsers.scala:209)
at scala.util.parsing.combinator.Parsers$Parser$$anonfun$append$1$$anonfun$apply$1.apply(Parsers.scala:210)
at scala.util.parsing.combinator.Parsers$Parser$$anonfun$append$1$$anonfun$apply$1.apply(Parsers.scala:210)
at scala.util.parsing.combinator.Parsers$Failure.append(Parsers.scala:163)
at scala.util.parsing.combinator.Parsers$Parser$$anonfun$append$1.apply(Parsers.scala:210)
at scala.util.parsing.combinator.Parsers$Parser$$anonfun$append$1.apply(Parsers.scala:210)
at scala.util.parsing.combinator.Parsers$$anon$3.apply(Parsers.scala:183)
at scala.util.parsing.combinator.Parsers$Parser$$anonfun$append$1$$anonfun$apply$1.apply(Parsers.scala:210)
at scala.util.parsing.combinator.Parsers$Parser$$anonfun$append$1$$anonfun$apply$1.apply(Parsers.scala:210)
at scala.util.parsing.combinator.Parsers$Failure.append(Parsers.scala:163)

(The last 6 lines are repeated a few more times)

Solution The previous update probably contains a syntax error somewhere, got it fixed slightly different as follows:

start n=node:entities("text:*") 
MATCH p=(n)-[left:OCCURS]->(f) 
WHERE  (    
(NONE ( path in (f)<-[:OCCURS]-() 
    WHERE  
      ANY(n4 in nodes(path) 
        WHERE ID(n4) <> ID(n) 
          AND n4.type = 'ENTITY' 
          AND n4.text =~ "a regex expr" 
        ) 
      AND ALL(r4 in rels(path)  
        WHERE r4.line_nr <= left.line_nr + 0 
          AND r4.line_nr >= left.line_nr - 0 
        ) 
     )
  ) )
AND  
 NONE ( ......  )  
WITH n, left, f, count(*) as group_by_cause 
RETURN ...

It is however slow. Order of seconds (>10) for small graph: 4 entities-nodes and 6 :OCCURS relations in total, all to 1 single destination f node, with line_nr's between 0 and 3.

Performance Update The following is about twice as fast:

start n=node:entities("text:*") 
MATCH p=(n)-[left:OCCURS]->(f) 
, p4=(f)<-[right4?:OCCURS]-(n4) 
, p7=(f)<-[right7?:OCCURS]-(n7) 
WHERE  
 ( n4.text? =~ "regex1" 
  AND (p4 = null 
       OR left.line_nr < right4.line_nr - 0 
       OR left.line_nr > right4.line_nr + 0 
       OR ID(left) = ID(right4)  
       )
 ) 
 AND  
( n7.text? =~ "regex2" 
  AND (p7 = null .....)
)
WITH n, left, f, count(*) as group_by_cause 
RETURN ....

Michael Hunger Michael Hunger · Accepted Answer · 2013-03-26T14:25:42

I think instead of the optional relationships you should use the pattern predicates in WHERE as you noted. The pattern expressions actually return a collection of paths, so you could do collection predicates like (ALL, NONE, ANY, SINGLE)

WHERE NONE(path in (f)<-[:OCCURS]-(n4) WHERE 
           ALL(r in rels(p) : r.line_nr = 42 ))

see: http://docs.neo4j.org/chunked/milestone/query-function.html#_predicates

How to verify that specific paths do not exist in cypher query

1 Answers