Neo4j directed path through multiple relationships with property filter

Question

Being new to Cypher and Neo4j, I am having trouble constructing my query for my use-case. I am building a simple ACL (access control list) and am looking for a path through permission relationships an up a hierarchy as well. A picture may better explain it:

Key:
    Users -> Blue
    Groups -> Yellow, Green
    Resource Tree -> Red

Now I want to see if a path exists from Bob to the eVar 33 resource where Bob has update access. Because there is a direct path, I can get what I am looking for by running

MATCH p =(usr:Usr)-[:AXO {update: true}]->(aco:ACO)
WHERE usr.name = 'Bob' AND aco.name = 'eVar 33'
RETURN p

But now, Bob is also a member of the Media Mgmt group which grants him read access to the Conversion resource. And because Conversion is further up the resource tree than eVar 33, eVar 33 should inherit this permission. But when I run the same query looking for {read: true} instead, no path is found. I know this is because I am not allowing traversal through the :IN and :HAS relationships, but how can I do this?

I have tried:

MATCH p =(usr:Usr)-[:IN|:HAS|:AXO {read: true}]->(aco:ACO)
WHERE usr.name = 'Bob' AND aco.name = 'eVar 33'
RETURN p

thinking this would allow those relationships to be traversed, but it still does not find a path (because I am not allowing more than a depth of 1?).

So here are my needs:

• Unknown depth of path
• Any path(s) I get back are fine (all I really care about is "Is there a path or not?")
• Must be able to get from a user to a resource AND when an AXO relationship is being followed it must match a property filter.
• Must follow the directed graph (i.g. Bob has no permissions for Analytics)

And no, I do not work for Nike. Just an example use-case here :)

Wines

Answer 1

Does this do what you want?

MATCH (bob:User { name:"Bob" })-[:IN*0..]->(group)-[:AXO { read:true }]->(res1)-[:HAS*0..]->(res2 { name:"eVar 33" })
RETURN count(*)

I take this query to mean something like: "Give me user Bob, and any [:AXO{read:true}] relationship that he has to resource eVar 33. You may go to through zero or more [:IN] to access the resource through Bob's groups, and through zero or more [:HAS], since resources inherit permissions".

>1 means read access, 0 means not.

If your [:IN] or [:HAS] trees are very complex you may want to cap depth.

Edit
Wrt comment about optimizing by returning on first path found, it's not always obvious how to control query execution this way, sometimes you have to know when and how Cypher is lazy. Limiting result to 1 may suffice, but in this case reformulating the query slightly may be more to the point, something like: "Give me user Bob if he has any [:AXO{read:true}] relationship to resource eVar 33. You may go through..."

Now the path from Bob to resource is a predicate on which the Bobs in your MATCH clause are filtered. In Cypher, something like

MATCH (bob:User { name:"Bob" })
WHERE bob-[:IN*0..]->()-[:AXO { read:true }]->()-[:HAS*0..]->({ name:"eVar 33" })
RETURN true

This will not return anything if the path predicate evaluates false. If you want to determine permission based on what is returned rather than whether something is returned, don't use WHERE but just return a count of the predicate, or better an assertion that the count of the predicate is 1. Since the pattern is not part of the MATCH clause it will not expand your result, so counting will be 0 or 1 (if there is only one Bob).

MATCH (bob:User { name:"Bob" })
RETURN 1 = count (bob-[:IN*0..]->()-[:AXO { read:true }]->()-[:HAS*0..]->({ name:"eVar 33" }))

It may 'feel' like counting the path predicate would mean counting the paths, but it doesn't. Try removing {read:true} to get a path pattern with more than one matches in the graph–counting it as a predicate still gives 1.

MATCH (bob:User { name:"Bob" })
RETURN 1 = count (bob-[:IN*0..]->()-[:AXO]->()-[:HAS*0..]->({ name:"eVar 33" }))

Try profiling such a query and compare to the first query with a LIMIT 1 to see which execution plan makes most sense.

Technic

Yep! This seems to do it! Thanks for putting it into that console view too. I appreciate your time doing that. I will play with this a bit more and accept your answer if it continues to look good :) – Wines

I could not break this, so it must be right! Followup question for you - Is there a way to optimize this so that if it finds one path, it can break early (like a LIMIT on count)? If not, I am happy as is. Thanks! – Wines

Excellent tips for the optimization. Thank you. I raced all three and determined that I could not differentiate their performance one from another. I will do some better testing to be sure though. You have been a great help. Thanks for teaching me while answering :) – Wines

I'd love to see a graph-gist about it. A starting point could be: gist.neo4j.org/?50eaad78038e0cc2d217 – Exceptionable

Answer 2

I don't have your data, so I can't verify that this works, but here's something to play with:

MATCH path1 = (usr:Usr)-[axoRel1:AXO*1..10]->(aco1:ACO)
OPTIONAL MATCH path2 = usr-[b:IN]->(group:Group)-[axoRel2:AXO*1..10]->(aco2:ACO)
WHERE usr.name = 'Bob' AND 
      aco1.name = 'eVar 33' AND
      aco2.name = 'eVar 33' AND
      filter(y in axoRel2 WHERE y.update = true) = axoRel2
      filter(x in axoRel1 WHERE x.update = true) = axoRel1
RETURN path1, path2;

The OPTIONAL MATCH part makes it possible to match paths that go through a "Group" node like media management, without requiring that a user has to belong to a group.

The axoRel1:AXO*1..10 part matches between 1 and 10 hops of AXO relationships. Note that when you use the variable path bit, you no longer can use the { update: true } syntax, because axoRel1 is a collection of relationships, not a single relationship. To filter based on update: true that's what the filter statements in the WHERE clause are for. When the filtered set of relationships where update=true is the same as the actual set, then you know all of them have update=true.

Scagliola

Very cool! This does not quite work, but it sent me down a path to try some new things similar to this. Thank you. But, it seems like there may be several path cases to consider and could get complicated. For instance, traversing down the :HAS relations. – Wines