Skip to main content

Graph of Relations

Relation tuples can be modeled or represented as an acyclic directed graph of relationships between an Object and a Subject. The graph consists of three types of nodes:

  • Object node - These represent objects in the object graph.
  • SubjectSet node - These represent intermediate relationships between two (namespace, object, relation) pairs.
  • SubjectID node - These represent an identifier that uniquely identifies an actor (e.g. an end-user or client app).

Representing relation tuples in this way helps us better understand the query time and space complexity used by the internal search algorithm.

Example#

Consider the following table of relation tuples:

namespace:objectrelationsubject
directories:dir1viewuser1
directories:dir1viewgroups:group1#member
groups:group1memberuser2
files:file1parentdirectories:dir1#...
files:file1viewdirectories:dir1#view
graph TD subgraph obj [Object nodes] A[dir1] --> |parent| B B[file1] G[group1] end subgraph subjID [SubjectID nodes] D([user1]) E([user2]) end subgraph subSets [SubjectSet nodes] I{{group1#member}} J{{dir1#view}} end A --> |view| D B --> |view| J I .-> E G --> |member| E J .-> D J --> |view| I B --> |view| I A --> |view| I

Solid edges represent explicit relations, while dotted edges represent relations inherited through a subject set.

Graph Observations#

A Check request of the form Check(namespace:object#relation@subject) will be evaluated by searching the graph starting at an object and going through it's relations in search for the matching subject. A Check request is allowed if there is such a path.

The algorithm used to traverse the graph is a concurrent breadth-first search. In the worst case this traversal has a time complexity of O(n+e) where n is the number of nodes reachable from the namespace:object#relation node through its edges e. The traversal has a space complexity of O(n). Typically, both space and time complexity are O(b^d) where b is the maximum breadth and d the maximum depth in the graph search. This means that the complexity heavily depends on the structure of the graph. If the graph contains deeply nested indirections, it will require multiple recursive calls to resolve those indirections. If there are widely nested indirections, we can resolve them more concurrently.

Edit this page