---
title: 'Relationship-Based Access Control'
source: 'https://academia.sh/en/courses/authentication-and-authorization/relationship-based-access-control'
course: 'Authentication and Authorization'
language: en
updated: '2026-08-19T05:19:32+00:00'
license: 'CC BY-SA 4.0'
---

# Relationship-Based Access Control

Turning the links between subjects and objects into first-class data, the access question becoming a reachability query over a graph, transitive access, and the cost difference between checking a single object and listing accessible ones.

In the previous two lessons, S7 was decided wrong. U-1001 had shared reading list number
nine with U-1002; U-1002 should have been able to see that list. Neither the role-based
model nor the attribute-based model could express this, because sharing is a property
of neither the subject nor the object — it is the link between the two.

**Relationship-based access control** turns these links into first-class data. The
subjects and objects in the system become the nodes of a graph, and the links between
them become named edges. The access question turns into a reachability query over this
graph: can the subject reach the object by following a specific sequence of edges?

## The Graph, Edges, and Path Patterns

The library loan service's relationships can be written with a small number of edge
types. `owner` links a member to their own record. `belongsTo` links a record to its
branch. `worksAt` and `manages` link staff to their branch. `sharedWith` links a list to
the person or group it is shared with. `memberOf` links a person to a group.

An access rule is a **path pattern** made of these edges. The rule "can view its own
loan record" is a one-step pattern: `owner`. The rule "branch staff can view their
branch's records" is a two-step pattern, and the second step follows the edge in
reverse: from staff to branch via `worksAt`, from branch to record via the reverse of
`belongsTo`.

The evaluator below runs these patterns. At each step it moves from one set of nodes to
the neighboring set; this is the edge-type-filtered form of the breadth-first search
from the Data Structures course.

```bash
cat > rebac.mjs <<'EOF'
const EDGES = [                         // [source, relation, target]
  ["U-1001", "owner", "loan:501"], ["U-1002", "owner", "loan:502"],
  ["U-1005", "owner", "loan:503"], ["U-1001", "owner", "list:9"],
  ["loan:501", "belongsTo", "S-02"], ["loan:502", "belongsTo", "S-02"],
  ["loan:503", "belongsTo", "S-01"], ["fine:77", "belongsTo", "S-02"],
  ["P-2001", "worksAt", "S-02"], ["Y-3001", "manages", "S-02"],
  ["list:9", "sharedWith", "U-1002"], ["list:9", "sharedWith", "group:reading-club"],
  ["U-1006", "memberOf", "group:reading-club"],
];

// A "~relation" in a pattern means the edge is followed in reverse.
const PATTERNS = {
  "view:loan":   [["owner"], ["worksAt", "~belongsTo"], ["manages", "~belongsTo"]],
  "update:loan": [["worksAt", "~belongsTo"], ["manages", "~belongsTo"]],
  "create:loan": [["worksAt", "~belongsTo"], ["manages", "~belongsTo"]],
  "delete:loan": [["manages", "~belongsTo"]],
  "delete:fine": [["manages", "~belongsTo"]],
  "view:list":   [["owner"], ["~sharedWith"], ["memberOf", "~sharedWith"]],
};

function step(nodes, relation) {
  const reversed = relation.startsWith("~");
  const name = reversed ? relation.slice(1) : relation;
  const result = new Set();
  for (const [s, r, t] of EDGES) {
    if (r !== name) continue;
    if (!reversed && nodes.has(s)) result.add(t);
    if (reversed && nodes.has(t)) result.add(s);
  }
  return result;
}

function rebac(subject, action, object) {
  for (const pattern of PATTERNS[`${action}:${object.split(":")[0]}`] ?? []) {
    let frontier = new Set([subject]);
    for (const relation of pattern) frontier = step(frontier, relation);
    if (frontier.has(object)) return [true, pattern.join(" -> ")];
  }
  return [false, "no reachable path"];
}

const SCENARIOS = [
  ["S1", "U-1001", "view",   "loan:501", true],
  ["S2", "U-1001", "view",   "loan:502", false],
  ["S3", "P-2001", "view",   "loan:502", true],
  ["S4", "P-2001", "view",   "loan:503", false],
  ["S5", "P-2001", "update", "loan:502", false],
  ["S6", "Y-3001", "delete", "fine:77",  true],
  ["S7", "U-1002", "view",   "list:9",   true],
  ["S8", "U-1005", "view",   "list:9",   false],
];

console.log("scenario | ReBAC | expect | match | path found");
console.log("---------|-------|--------|-------|--------------------------");
let matched = 0;
for (const [name, subject, action, object, expected] of SCENARIOS) {
  const [decision, path] = rebac(subject, action, object);
  if (decision === expected) matched++;
  console.log(`${name}       | ${(decision ? "allow" : "deny").padEnd(5)} | ` +
    `${(expected ? "allow" : "deny").padEnd(6)} | ${(decision === expected ? "+" : "-").padEnd(5)} | ${path}`);
}
console.log(`\nReBAC correct decisions: ${matched}/${SCENARIOS.length}`);

console.log("\ntransitive access (outside the common set):");
for (const code of ["U-1006", "U-1005"]) {
  const [decision, path] = rebac(code, "view", "list:9");
  console.log(`  ${code} -> list:9 : ${decision ? "allow" : "deny"}  (${path})`);
}
EOF
node rebac.mjs
```

```text
scenario | ReBAC | expect | match | path found
---------|-------|--------|-------|--------------------------
S1       | allow | allow  | +     | owner
S2       | deny  | deny   | +     | no reachable path
S3       | allow | allow  | +     | worksAt -> ~belongsTo
S4       | deny  | deny   | +     | no reachable path
S5       | allow | deny   | -     | worksAt -> ~belongsTo
S6       | allow | allow  | +     | manages -> ~belongsTo
S7       | allow | allow  | +     | ~sharedWith
S8       | deny  | deny   | +     | no reachable path

ReBAC correct decisions: 7/8

transitive access (outside the common set):
  U-1006 -> list:9 : allow  (memberOf -> ~sharedWith)
  U-1005 -> list:9 : deny  (no reachable path)
```

S7 is solved for the correct reason for the first time in three lessons: a `sharedWith`
edge runs to the list from U-1002. S8 is denied by the same pattern, because no edge
runs to U-1005.

The last two lines show the model's real strength. U-1006 is not directly linked to the
list; it is a member of the reading club group, and the list is shared with that group.
The two-step path establishes this link. In the attribute-based model, reaching the same
result would have required copying every member of the group into the object's attribute
field and updating that copy every time the group changes. In the graph, group
membership is a single edge, and adding the edge affects every list at once.

## Where the Model Falls Short

S5 is wrong in this model. Loan records not being updated outside business hours is a
context constraint, and the graph has no counterpart for it — time is not an edge
between two nodes.

This is the mirror image of the previous lesson. The attribute-based model could see
context but not relationships; the relationship-based model can see relationships but
not context. The two models' gaps do not overlap — they complement each other. This
observation is the starting point for the next lesson.

## Two Separate Questions, and Their Costs

Two different questions are asked in the relationship-based model, and their costs are
not the same.

The first is a **check**: "can this subject reach this object?" The moment an answer is
found, the search stops. The second is a **listing**: "which objects can this subject
reach?" This question is needed to render a list page, and it requires running every
pattern to completion.

```bash
cat > rebac-cost.mjs <<'EOF'
const EDGES = [
  ["U-1001", "owner", "loan:501"], ["U-1002", "owner", "loan:502"],
  ["U-1005", "owner", "loan:503"], ["U-1001", "owner", "list:9"],
  ["loan:501", "belongsTo", "S-02"], ["loan:502", "belongsTo", "S-02"],
  ["loan:503", "belongsTo", "S-01"], ["fine:77", "belongsTo", "S-02"],
  ["P-2001", "worksAt", "S-02"], ["Y-3001", "manages", "S-02"],
  ["list:9", "sharedWith", "U-1002"], ["list:9", "sharedWith", "group:reading-club"],
  ["U-1006", "memberOf", "group:reading-club"],
];
const PATTERNS = {
  "view:loan": [["owner"], ["worksAt", "~belongsTo"], ["manages", "~belongsTo"]],
  "view:list": [["owner"], ["~sharedWith"], ["memberOf", "~sharedWith"]],
};

let edgeReads = 0;
function step(nodes, relation) {
  const reversed = relation.startsWith("~"), name = reversed ? relation.slice(1) : relation;
  const result = new Set();
  for (const [s, r, t] of EDGES) {
    edgeReads++;
    if (r !== name) continue;
    if (!reversed && nodes.has(s)) result.add(t);
    if (reversed && nodes.has(t)) result.add(s);
  }
  return result;
}

const walk = (subject, pattern) => {
  let frontier = new Set([subject]);
  for (const relation of pattern) frontier = step(frontier, relation);
  return frontier;
};

function check(subject, permission, object) {     // stops at the first matching pattern
  for (const pattern of PATTERNS[permission] ?? []) if (walk(subject, pattern).has(object)) return true;
  return false;
}

function accessible(subject, permission) {         // all patterns are walked
  const all = new Set();
  for (const pattern of PATTERNS[permission] ?? []) for (const d of walk(subject, pattern)) all.add(d);
  const type = permission.split(":")[1] + ":";
  return [...all].filter((d) => d.startsWith(type)).sort();
}

console.log("single-object check (stops at the first matching pattern):");
for (const [subject, object] of [["P-2001", "loan:502"], ["U-1001", "loan:501"],
                             ["U-1005", "loan:502"]]) {
  edgeReads = 0;
  const k = check(subject, "view:loan", object);
  console.log(`  ${subject} -> ${object} : ${(k ? "allow" : "deny").padEnd(5)} ` +
    `(${String(edgeReads).padStart(2)} edge reads)`);
}

console.log("\nlist of accessible objects (all patterns are walked):");
for (const [subject, permission] of [["P-2001", "view:loan"], ["U-1001", "view:loan"],
                            ["U-1006", "view:list"], ["U-1005", "view:list"]]) {
  edgeReads = 0;
  const list = accessible(subject, permission);
  console.log(`  ${subject} ${permission.padEnd(16)} -> [${(list.join(", ") || "empty").padEnd(22)}]` +
    ` (${edgeReads} edge reads)`);
}
EOF
node rebac-cost.mjs
```

```text
single-object check (stops at the first matching pattern):
  P-2001 -> loan:502 : allow (39 edge reads)
  U-1001 -> loan:501 : allow (13 edge reads)
  U-1005 -> loan:502 : deny  (65 edge reads)

list of accessible objects (all patterns are walked):
  P-2001 view:loan        -> [loan:501, loan:502    ] (65 edge reads)
  U-1001 view:loan        -> [loan:501              ] (65 edge reads)
  U-1006 view:list        -> [list:9                ] (52 edge reads)
  U-1005 view:list        -> [empty                 ] (52 edge reads)
```

The edge-read counts are specific to this small graph; what matters is the ratio between
them. Two observations stand out.

First, **a deny decision is the most expensive decision**. An allow decision stops at
the first matching pattern; a deny decision requires every pattern to be exhausted.
Denying U-1005 cost sixty-five edge reads; allowing U-1001 cost thirteen. Unauthorized
request traffic loads more cost onto the check layer than authorized traffic does — this
is why rate limiting sits in front of the check layer.

Second, a listing query is not a repetition of the check query. Rendering a list page by
"fetch every record, call the check for each one" produces as many check calls as the
page has entries. The correct structure is to produce the set of accessible objects once
and limit the data query to that set. How this set is passed into the query is a
scale-dependent design decision: small sets travel as a plain list of identifiers, large
sets travel as a join condition added to the resource query.

## Maintaining the Graph

The relationship-based model's operating cost is maintaining the edges.

**An edge is written together with the source data.** When a loan record is created, its
`owner` edge is created too; if the two are written in separate transactions, requests
arriving in between are decided wrongly. Writing the edge must sit inside the same
transaction that writes the record.

**An edge is deleted together with the source data.** Edges left undeleted quietly leave
access open, and because they produce no error, they go unnoticed. Regularly scanning
for edges whose source no longer exists is the counterpart, here, of the orphan-record
audit from the Relational Database Administration course.

**Path length is bounded.** The longer a pattern is, the wider a set of nodes the search
spreads across. An inheritance chain with unbounded depth — a group's group, and that
group's group — makes the cost unpredictable and makes who has access to what impossible
to follow by eye.

## Summary

- Relationship-based access control turns links into first-class data; the access
  question turns into a reachability query over a graph.
- An access rule is a path pattern; edges can be followed forward or in reverse.
- Transitive access — a record shared with a group opening up to the group's
  members — is expressed with a single edge and requires no copying into an attribute
  field.
- The model cannot express context constraints; information like the time has no
  counterpart in the graph.
- A deny decision requires every pattern to be exhausted and so costs more than an
  allow decision; a listing query is done by producing the accessible set, not by
  calling the check one object at a time.

## Next Step

All three models fell short in different places on the same scenario set, and their
gaps complement each other. This points not to a fourth model but to a question about
where these rules are written: will all of them just sit scattered through the
application code in `if` blocks? The next lesson takes up policy-based authorization,
which separates the decision from the code, and compares all four models' decisions in
the same table.