- 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.
Consider the following table of relation tuples:
Solid edges represent explicit relations, while dotted edges represent relations inherited through a subject set.
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.