Neo4j

hmavani7 · ‎09-22-2020

Summary I have the following graph structure and the idea is that manager has certain permissions on given resources As seen in the picture, there are three resources and one context (manager). Further we see some inheritance on the resources. break is owned by shift . And lunch is owned by break. I want to design a query that returns all shortest paths from the manager to each resource. For example the shortest path from manager to shift will be the permission relationship seen going out from the manager where the permitted field is allowed. The question lies with finding the shortest path to break. Ideally, I want the shortest path to break to go via shift and not via lunch. In other words permissions present on the parent are to be inherited for a child without any direct permissions

What I have tried: I did manage to write the correct query but here's my problem - the result correctly eliminates a few resources

Code Here is the query I have tried so far. It correctly computes the shortest path to resources with one catch - it considers both the shortest path to break . One via lunch [should not happen] and one via shift [I want this]. Further it omits shift all together because it is purely an "ancestor" (refer to the query) and not a "child" which I understand.

MATCH (ancestors:Resource)<-[:OWNED_BY*..15]-(child:Resource)
MATCH (principal:Resource{id: "p-id"})<-[grant:GRANTED_TO]-(context:Context{id:"c-id"})-[permission:PERMISSION]->(ancestors), path = allShortestPaths((context)-[*..15]-(child))
RETURN DISTINCT path

Here's the output for the query when executed in my browser.

ut here's my problem - the result correctly eliminates a few resources

Code Here is the query I have tried so far. It correctly computes the shortest path to resources with one catch - it considers both the shortest path to break . One via lunch [should not happen] and one via shift [I want this]. Further it omits shift all together because it is purely an "ancestor" (refer to the query) and not a "child" which I understand.

MATCH (ancestors:Resource)<-[:OWNED_BY*..15]-(child:Resource)
MATCH (principal:Resource{id: "p-id"})<-[grant:GRANTED_TO]-(context:Context{id:"c-id"})-[permission:PERMISSION]->(ancestors), path = allShortestPaths((context)-[*..15]-(child))
RETURN DISTINCT path

Here's the output for the query when executed in my browser.

{
  "start": {
"identity": 22,
"labels": [
      "Context"
    ],
"properties": {
"name": "manager",
"id": "adef1b8c-3141-44bc-a1ec-1644fa6db79a"
    }
  },
  "end": {
"identity": 41,
"labels": [
      "Resource"
    ],
"properties": {
"name": "break",
"context_id": "",
"id": "b8519676-312a-4ba4-8004-404c7d782706",
"source_id": "break-guid"
    }
  },
  "segments": [
    {
      "start": {
"identity": 22,
"labels": [
          "Context"
        ],
"properties": {
"name": "manager",
"id": "adef1b8c-3141-44bc-a1ec-1644fa6db79a"
        }
      },
      "relationship": {
"identity": 4,
"start": 22,
"end": 20,
"type": "PERMISSION",
"properties": {
"permitted": "allow",
"name": "read",
"id": "dad8b6a0-b039-4105-87d4-ca151963e1a7"
        }
      },
      "end": {
"identity": 20,
"labels": [
          "Resource"
        ],
"properties": {
"name": "shift",
"context_id": "",
"id": "2ba8d928-d534-4179-9fad-c85f584ce6d5",
"source_id": "guid"
        }
      }
    },
    {
      "start": {
"identity": 20,
"labels": [
          "Resource"
        ],
"properties": {
"name": "shift",
"context_id": "",
"id": "2ba8d928-d534-4179-9fad-c85f584ce6d5",
"source_id": "guid"
        }
      },
      "relationship": {
"identity": 21,
"start": 41,
"end": 20,
"type": "OWNED_BY",
"properties": {

        }
      },
      "end": {
"identity": 41,
"labels": [
          "Resource"
        ],
"properties": {
"name": "break",
"context_id": "",
"id": "b8519676-312a-4ba4-8004-404c7d782706",
"source_id": "break-guid"
        }
      }
    }
  ],
  "length": 2.0
}

{
  "start": {
"identity": 22,
"labels": [
      "Context"
    ],
"properties": {
"name": "manager",
"id": "adef1b8c-3141-44bc-a1ec-1644fa6db79a"
    }
  },
  "end": {
"identity": 41,
"labels": [
      "Resource"
    ],
"properties": {
"name": "break",
"context_id": "",
"id": "b8519676-312a-4ba4-8004-404c7d782706",
"source_id": "break-guid"
    }
  },
  "segments": [
    {
      "start": {
"identity": 22,
"labels": [
          "Context"
        ],
"properties": {
"name": "manager",
"id": "adef1b8c-3141-44bc-a1ec-1644fa6db79a"
        }
      },
      "relationship": {
"identity": 24,
"start": 22,
"end": 60,
"type": "PERMISSION",
"properties": {
"permitted": "deny",
"name": "read",
"id": "9b52f239-43b5-4b17-a29a-91bfeebca001"
        }
      },
      "end": {
"identity": 60,
"labels": [
          "Resource"
        ],
"properties": {
"name": "lunch",
"context_id": "",
"id": "8c96482d-517f-4421-b1e8-4f4826438cf1",
"source_id": "lunch-guid"
        }
      }
    },
    {
      "start": {
"identity": 60,
"labels": [
          "Resource"
        ],
"properties": {
"name": "lunch",
"context_id": "",
"id": "8c96482d-517f-4421-b1e8-4f4826438cf1",
"source_id": "lunch-guid"
        }
      },
      "relationship": {
"identity": 23,
"start": 60,
"end": 41,
"type": "OWNED_BY",
"properties": {

        }
      },
      "end": {
"identity": 41,
"labels": [
          "Resource"
        ],
"properties": {
"name": "break",
"context_id": "",
"id": "b8519676-312a-4ba4-8004-404c7d782706",
"source_id": "break-guid"
        }
      }
    }
  ],
  "length": 2.0
}

{
  "start": {
"identity": 22,
"labels": [
      "Context"
    ],
"properties": {
"name": "manager",
"id": "adef1b8c-3141-44bc-a1ec-1644fa6db79a"
    }
  },
  "end": {
"identity": 60,
"labels": [
      "Resource"
    ],
"properties": {
"name": "lunch",
"context_id": "",
"id": "8c96482d-517f-4421-b1e8-4f4826438cf1",
"source_id": "lunch-guid"
    }
  },
  "segments": [
    {
      "start": {
"identity": 22,
"labels": [
          "Context"
        ],
"properties": {
"name": "manager",
"id": "adef1b8c-3141-44bc-a1ec-1644fa6db79a"
        }
      },
      "relationship": {
"identity": 24,
"start": 22,
"end": 60,
"type": "PERMISSION",
"properties": {
"permitted": "deny",
"name": "read",
"id": "9b52f239-43b5-4b17-a29a-91bfeebca001"
        }
      },
      "end": {
"identity": 60,
"labels": [
          "Resource"
        ],
"properties": {
"name": "lunch",
"context_id": "",
"id": "8c96482d-517f-4421-b1e8-4f4826438cf1",
"source_id": "lunch-guid"
        }
      }
    }
  ],
  "length": 1.0
}

Is there any way to write a query that gives me shortest path (permissions) to all resources and in case there isn't a shortest path, take the permissions of the immediate parent. Any help will be appreciated. Thank you

tony_chiboucas · ‎09-22-2020

There is always the Graph Data Science: Shortest Path Algorithms, and many conversations in this forum about how to use it in similar cases.

However, you've still got a logic problem to solve:

What's the shortest path between (lunch) and (shift)? There's 2. OK, let's take permissions from the parent.... there's 2.

Graph Design Suggestions

From child to parent, from many to few.
OWNED_BY is vague, and not descriptive of the real relationship between a specific :Lunch node and a specific :Break node.
What are you looking for that PERMISSION to represent, what will it do? Give the manager permission to change or set shifts and breaks?

A Lunch is both a break, and a kind of break, but breaks are typically paid while lunch is not. What are you trying to represent with this graph? Then I might be able to help define a good pattern for you.

hmavani7 · ‎09-22-2020

Those are some really insightful questions. Pardon me for the poor example. Allow me to frame the question more correctly.

The question I am trying to ask is - what permissions does a manager have on each Resource. A permission is a relationship from the context to a resource. There are a bunch of cases that come to mind - if a resource has a direct permission from the context - that is the answer, that is the permission you return. If however there isn't a direct relationship between the context and the resource, then the permission granted to the closest parent is the answer. Let's define a parent. A parent owns a child. In other words, a child is :OWNED_BY a parent.

Now allow me to answer your questions specifically.
A shortest path from a resource to another will be only through the :OWNED_BY properties. However the shortest path from a context to a resource can be either direct or via another resource (paarent).

I am sorry for the poor representation. A better example would be a school organization - Principal owns Staff owns Computers. Or in the graphical terms, Computers -[:OWNED_BY]-> Staff - [OWNED_BY]->Principal. And then the context can be something else, like a trustee for example. The idea is to represent ownership heirarchy. And permission on the parent is inherited by the child. Unless there is an explicit permission set on the child.

Please let me know if this doesn't make sense. Thank you!

tony_chiboucas · ‎09-23-2020

IMO, you're unintentionally constraining the data to reflect what you want to do. Graph DB problems get simpler if you start with trying to represent reality, than trying to represent the solution.

If I use your school example:

(:Computers)-[:OWNED_BY]->(:Staff)-[:OWNED_BY]->(:Principal)

...might be beter represented as:

(:Computer)-[:USER]->(:Teacher:Staff)-[:WORKS_FOR]->(:Principal:Staff)
(:Computer)-[:USER]->(:Student)-[:STUDIES]->(:Subject)-[:TAUGHT_BY]->(:Teacher:Staff)

What is permission?

I'm still confused about what Permission is supposed to do. I understand that you're trying to apply permission to a relationship, but once you have a specific "permission" identified for some parent--child, what will that permission mean? Parent can edit child? Child can talk to parent? Child is visible to parent? Parent is responsible for child?

Describe reality, rather than use generic terms

When defining a label, would the label-name help someone else understand what a single such node is? Better labels will help you and others, better understand and solve the problem.

"Resource" can refer to pretty much anything, so it really doesn't help. Are we talking about people, employees, assignments, schedules, etc.?
- It looks like you're dealing with managers, employees, shifts, breaks, and lunches... so why not use those as labels?
"Owned by" similarly tells little or nothing about what that relationship actually represents.
- In a relational db we are forced into these terms, but in a graph we can represent reality more closely. A break isn't "owned by" a shift, a break is part of a shift, or in a shift.

If I assume you're trying to define a method of determining if a specific :Manager:Employee can edit a :TimePeriod, and we adjust your model, the problem is simplified:

Node Labels
:Employee - person
:Manager - an Employee which will be granted permission to edit TimePeriods
:TimePeriod - any node which represents a period of time
:Shift - TimePeriod for an Employee to work
:Break - TimePeriod in a Shift where an Employee is off
:Lunch - Unpaid Break, usually 30m or 1h
:Rest - Short Paid Break usually 10m or 15m

We could then get a graph that looks more like the following:

Then, edit permissions become as simple as finding the :REPORTS_TO parent of any :TimePeriod.

MATCH (t:TimePeriod)-[*1..2]->()-[:REPORTS_TO]->(m)
RETURN m.name, t.name

I don't think that's really what you're asking.

I suspect you're oversimplifying your problem into these employee/shift terms. Since I don't have any clarity into your real graph or problem, all I can advise is this:

Options:

Fix your Graph Model Design, seriously, it'll make your life much easier.
- Don't be afraid to mutate your graph. Clone it just in case if you want. Mutate in several commands, then revert your changes when you have the data you want. GraphDBs are meant to be easily movable.
Run two separate queries, combine the results. You can get all shortest paths. You can get all :Resources with their closest parent with a permission. Any :Resources not in the shortest paths result can instead pull the perms from the second query result.
WITH resource, COLLECT(path) as best ... MATCH (resource)-[:OWNED_BY]->(target) ...UNWIND best ... CASE WHEN ... , but that will be tricky to write, and trickier to debug.

apoc.do.when can allow you to select from different data sets if a specific variable is NULL:

MATCH p=(child:Resource)-[:OWNED_BY*..15]->(ancestors:Resource)
MATCH (principal:Resource{id: "p-id"})<-[grant:GRANTED_TO]-(context:Context{id:"c-id"})-[permission:PERMISSION]->(ancestors), path = allShortestPaths((context)-[*..15]-(child))

CALL apoc.when(
  principal IS NOT NULL,
  'RETURN c as child, p as permNode',
  'RETURN c as child, nodes(t)[1] as permNode',
  {c:child, p:principal, t:p})
YIELD value

RETURN value.child as c, value.permNode as perm

... but that is gonna take some serious experimentation to find the best plan.

hmavani7 · ‎09-23-2020

Thanks for the detailed analysis, @tony.chiboucas. I really appreciate your time and efforts in helping me with this problem. I sense that the discussion is going to take a turn as I widen my horizons with this answer.

I believe you are correct that I am unintentionally constraining the data to reflect what I want to do. Infact, I'd go ahead and say that I am doing this intentionally.

What is a permission?
Let me take a step back and explain what the database is set out to do. I am building an API that answers questions like "Does a manager has read permissions on lunch? ", "List out all permissions that a manager has?" The answer to this is dependent on the permission relationship that is previously stored by a user of the API. I define the model such that a permission from a context to resource denotes what access does the context has on the resource. And this is just a way of storing data. I am using a graph database as compared to a relational one to do so. So a resource can be anything generic. You might ask why have the heirarchy at all. Well, if I am to create separate resource and assign them the same permissions, I might have to create numerous edges (permission) to newly created resources. So instead I wish to inherit permissions. Permissions on a resource is inherited by the parent or the closes grant parent that has an incoming permission edge. I hope that makes sense

Reality
Users of the API will make calls and store the permission models in the graph DB. They will tell the API that create a "manager" and give it "read" permissions on lunch.

As you might have guessed this is meant to be domain agnostic. Someone might want to create a manager while others might want to create a teacher. And I want to limit the number of knobs a user has to turn to use the API. The graph is abstracted away. The graph acts as a ledger of sorts to keep track of who has what permission to whom.

Please feel free to propose a better model. I am very new to graphs and I am super keen on learning. Thanks again. Really appreciate the feedback

Neo4j

How to use Predicates correctly in cypher allShortestPaths

Graph Design Suggestions

What is permission?

Describe reality, rather than use generic terms

I don't think that's really what you're asking.