The Problem Statement

Our ReBAC v1 model from Post 3 works perfectly for same-object relationships. We can express "owners are editors" and "editors are viewers" on the same document. But your product manager returns with a new requirement that breaks this assumption:

"Documents should inherit viewer permissions from their parent folder. If Alice can view a folder, she should automatically be able to view all documents in that folder."

This is fundamentally different from Post 3's boolean algebra. We're no longer combining relations on the same object—we're traversing across object boundaries to find permissions on a different object.

Let's see what this means:

// Folder structure
folder:marketing/
  ├─ document:budget.pdf
  ├─ document:strategy.md
  └─ subfolder:campaigns/
       └─ document:q4-plan.md

// Alice can view the marketing folder
RelationTuple{
    Resource: &ObjectAndRelation{Namespace: "folder", ObjectID: "marketing", Relation: "viewer"},
    Subject:  &DirectSubject{Object: &ObjectRef{Namespace: "user", ObjectID: "alice"}},
}

// The human rule we need to express:
// "Documents inherit viewers from their parent folder"
// So Alice should automatically be able to view budget.pdf, strategy.md, etc.

The core problem: Our current model can't express "if you have relation X on object A, you automatically have relation Y on object B (which is related to A)."

Terminology Quick Reference

Before diving into the solution, let's clarify key terms:

  • ObjectRef: namespace:id (e.g., user:alice, folder:marketing)

  • ObjectAndRelation: namespace:id#relation (e.g., document:budget.pdf#viewer)

  • Edge Tuple: A tuple where Resource = object#edgeName, Subject = targetObject

    • Example: Resource = document:budget.pdf#parent, Subject = folder:marketing

    • Meaning: "document:budget.pdf has parent folder:marketing"

Why Same-Object Boolean Algebra Isn't Enough

Let's see what goes wrong if we try to solve this with Post 3's tools:

Approach 1: Explicit Enumeration

// Try to grant every user access to every document
for each document in folder {
    for each user who can view folder {
        store.Add(RelationTuple{
            Resource: document#viewer,
            Subject:  user,
        })
    }
}

Problems:

  • Maintenance nightmare: Adding a new document requires updating all folder viewers

  • Stale permissions: Removing a user from folder doesn't automatically remove them from documents

  • Doesn't scale: With 1,000 documents and 100 folder viewers, you need 100,000 tuples

Approach 2: Application-Layer Traversal


func Check(user, resource string) bool {
    // Check direct permission
    if tupleStore.Contains(user, resource) {
        return true
    }

    // Application logic: traverse parent folder
    doc := parseDocument(resource)
    parentFolder := doc.ParentFolder
    if tupleStore.Contains(user, parentFolder + "#viewer") {
        return true
    }

    return false
}

Problems:

  • Scattered logic: Traversal rules live outside the tuple store

  • Hardcoded relationships: Every new hierarchy type requires code changes

  • No schema: The relationship rules aren't declarative

The Core Insight

We need to model cross-object relationships where permissions flow from one object to another through defined edges. Instead of storing every permission explicitly, we define rules that compute permissions by traversing object relationships.

"The viewers of document X are: all users who have direct viewer relation on document X, UNION all users who have viewer relation on document X's parent folder."

This is our step into ReBAC v2 with edge traversal—where permissions are computed by following edges between objects.

Extending the Model: Edge Expressions (OP_EDGE)

The solution is to introduce edge expressions that traverse from one object to another and reuse permissions from the target object.

Step 1: Understanding Edges

An edge represents a relationship between two objects. For example:

  • A document has a "parent" edge pointing to its folder

  • A folder has a "child" edge pointing to its documents

  • An organization has a "member" edge pointing to its users

Step 2: Edge Expression Structure and Semantics (OP_EDGE)

type EdgeExpression struct {
    EdgeFrom string              // "parent" (relation on current object)
    EdgeTo   *RelationReference  // folder#viewer (target object and relation)
}

// OP_EDGE Semantics:
// For a subject S to have relation R on object O via OP_EDGE:
// 1. Query tuples keyed by (resource.namespace, resource.id, edge_from)
//    → yields Subject objects O' (the parents)
// 2. For each O' found, recursively check: Does S have EdgeTo.Relation on O'?
// 3. Return TRUE if ANY O' grants the permission (OR semantics)
// 4. If O has multiple parents, check all parents (multi-parent OR)

This represents: "Follow the parent edge to reach another object, then check the viewer relation on that object."

Step 3: OP_EDGE in the Operation Hierarchy

Post 3 introduced five operations; Post 4 adds the sixth:

type SubjectsComputationOp int32

const (
    OP_UNION SubjectsComputationOp = iota
    OP_INTERSECTION
    OP_EXCLUSION
    OP_EDGE              // NEW: Cross-object edge traversal
    OP_COMPUTED_SUBJECTS
    OP_DIRECT
)

OP_EDGE is unique because it leaves the current object to traverse to related objects. All other operations work within a single object's relation hierarchy.

Step 4: Tuple Structure for Parent Edges

Before showing the schema, let's clarify how parent edges are stored as tuples:

// Parent edge tuple structure
RelationTuple{
    Resource: &ObjectAndRelation{
        Namespace: "document",
        ObjectID:  "budget.pdf",
        Relation:  "parent",  // The edge name
    },
    Subject: &DirectSubject{
        Object: &ObjectRef{
            Namespace: "folder",
            ObjectID:  "marketing",  // The parent object
        },
    },
}

This means: "document:budget.pdf has parent folder:marketing"

When evaluating EDGE("parent", folder#viewer) for resource=document:budget.pdf:

  1. Query tuples keyed by (document, "budget.pdf", "parent") → subjects are parent folders

  2. For each parent folder O', Check(subject, O'#viewer)

  3. If ANY parent grants permission → return TRUE (OR semantics)

Multiple parents: If a document has multiple parent edges, the query returns all of them, and OP_EDGE checks each parent (OR semantics).

Step 5: Complete Document Schema with Edges (OP_EDGE)

documentNamespace := &NamespaceDefinition{
    Name: "document",
    Relations: map[string]*NamespaceRelationDefinition{
        // Base relations (direct tuples only)
        "owner": {
            Name:                          "owner",
            SubjectsComputationExpression: &DirectExpression{},
        },

        // Inheritance chain (same-object, from Post 3)
        "editor": {
            Name:                          "editor",
            SubjectsComputationExpression: &ComputedSubjectsExpression{
                ComputedRelation: "owner",
            },
        },
        "viewer": {
            Name:                          "viewer",
            SubjectsComputationExpression: &UnionExpression{
                Children: []SubjectsComputationExpression{
                    &ComputedSubjectsExpression{ComputedRelation: "editor"},
                    // NEW: Include viewers from parent folder(s)
                    // If document has multiple parents, check all (OR semantics)
                    &EdgeExpression{
                        EdgeFrom: "parent",
                        EdgeTo: &RelationReference{
                            Namespace: "folder",
                            Relation:  "viewer",
                        },
                    },
                },
            },
        },
    },
}

folderNamespace := &NamespaceDefinition{
    Name: "folder",
    Relations: map[string]*NamespaceRelationDefinition{
        "owner": {
            Name:                          "owner",
            SubjectsComputationExpression: &DirectExpression{},
        },
        "editor": {
            Name:                          "editor",
            SubjectsComputationExpression: &ComputedSubjectsExpression{
                ComputedRelation: "owner",
            },
        },
        "viewer": {
            Name:                          "viewer",
            SubjectsComputationExpression: &ComputedSubjectsExpression{
                ComputedRelation: "editor",
            },
        },
    },
}

Multiple-Parent Semantics (OR): If a document has multiple parent edges (e.g., shared between two folders), the OP_EDGE operation checks all parents. If the subject has the target relation on any parent, the permission is granted (OR logic).

AND Semantics Across Multiple Parent Relations:

If you need to require viewer permission on ALL parents (not just ANY), use INTERSECTION with multiple edge relations:

// Require viewer on ALL parent types:
document#viewer = INTERSECTION(
  EDGE("parent", folder#viewer),      // primary parent
  EDGE("xrefParent", folder#viewer),  // cross-reference parent
)
// User must have viewer on both the primary parent AND xref parent

Note: If you have a single "parent" relation with N parent objects, expressing "ALL N parents" requires cardinality operators (out of scope for this post).

Step 6: Generic Authorization Algorithm with Edge Traversal

Authorization now requires graph traversal that follows edges. The algorithm is operation-agnostic and works for all six operations:

ALGORITHM: Check(subject, resource#relation) - Generic with Edge Traversal

Input:
  - subject: The user or subject set to check (e.g., "user:alice")
  - resource: Object reference (e.g., "document:budget.pdf")
  - relation: Relation name (e.g., "viewer")

Output:
  - TRUE if subject has the relation on resource
  - FALSE otherwise

Steps:

1. Look up the relation definition in schema:
   - Find NamespaceDefinition for resource.namespace
   - Get NamespaceRelationDefinition for relation

2. Evaluate using uniform semantics:
   FinalSubjects(relation) = DIRECT(relation) ∪ Eval(Expression(relation))

   a) Check direct tuples:
      - Query: (subject, resource#relation)
      - If found → return TRUE

   b) Evaluate the SubjectsComputationExpression recursively:
      - Expression can be any of: DIRECT, COMPUTED_SUBJECTS, UNION, INTERSECTION, EXCLUSION, EDGE
      - Each operation has its own evaluation logic (see below)

3. Return result from expression evaluation

---

OPERATION EVALUATION (Recursive):

OP_DIRECT:
  - When top-level: Direct tuples already checked in step 2a
  - When nested: Evaluates to ∅ (empty set)
  - In expression evaluation context: Return FALSE

**Guideline:** OP_DIRECT is only meaningful at the top level for a relation;
do not embed DirectExpression nodes inside UNION/INTERSECTION/EXCLUSION trees.

OP_COMPUTED_SUBJECTS(computed_relation):
  - Recursively check: Check(subject, resource#computed_relation)
  - Return result

OP_UNION(children):
  - For each child expression:
    - Evaluate child recursively
    - If ANY child returns TRUE → return TRUE
  - Return FALSE

OP_INTERSECTION(children):
  - For each child expression:
    - Evaluate child recursively
    - If ANY child returns FALSE → return FALSE
  - Return TRUE

OP_EXCLUSION(left, right):
  - Evaluate left recursively
  - If left is FALSE → return FALSE
  - Evaluate right recursively
  - If right is TRUE → return FALSE
  - Return TRUE

OP_EDGE(edge_from, edge_to):
  - Query all tuples where (Resource.Namespace, Resource.ObjectID, Resource.Relation)
    == (resource.namespace, resource.id, edge_from). Each tuple's Subject is an object O'.
  - For each O':
      Recursively Check(subject, O'#edge_to.relation)
      If any returns TRUE → return TRUE
  - Return FALSE

Key insight: All operations are recursive and composable. An expression can contain nested operations (e.g., UNION of COMPUTED_SUBJECTS and EDGE), and the algorithm handles them uniformly.

Concrete Example: Applying the Generic Algorithm

Human rule: "Documents inherit viewers from their parent folder."

Schema definition:

document#viewer = UNION(
    COMPUTED_SUBJECTS("editor"),
    EDGE("parent", folder#viewer)
)

Query: Can user:alice view document:budget.pdf?

Execution trace:


Check(user:alice, document:budget.pdf#viewer)

1. Look up schema:
   - Namespace: "document"
   - Relation: "viewer"
   - Expression: UNION(COMPUTED_SUBJECTS("editor"), EDGE("parent", folder#viewer))

2. Check direct tuples:
   - Query: (user:alice, document:budget.pdf#viewer)
   - Not found → continue to expression evaluation

3. Evaluate UNION expression:

   Child 1: COMPUTED_SUBJECTS("editor")
     → Check(user:alice, document:budget.pdf#editor)
     → Recursively evaluate document#editor = COMPUTED_SUBJECTS("owner")
     → Check(user:alice, document:budget.pdf#owner)
     → Not found → FALSE

   Child 2: EDGE("parent", folder#viewer)
     → Query tuple store for all tuples: (document:budget.pdf, O'#parent)
     → Found: O' = folder:marketing
     → Check(user:alice, folder:marketing#viewer)
     → Look up folder#viewer = COMPUTED_SUBJECTS("editor")
     → Check(user:alice, folder:marketing#editor)
     → Look up folder#editor = COMPUTED_SUBJECTS("owner")
     → Check(user:alice, folder:marketing#owner)
     → Not found → FALSE
     → Back to folder#viewer: FALSE
     → Back to EDGE: FALSE

   UNION result: FALSE ∪ FALSE = FALSE

4. Return FALSE

Note: This example shows a case where Alice doesn't have access. Let's see a successful case:

Positive Example: Successful Permission Grant

Setup:

// Alice can view the marketing folder
store.Add(RelationTuple{
    Resource: &ObjectAndRelation{Namespace: "folder", ObjectID: "marketing", Relation: "viewer"},
    Subject:  &DirectSubject{Object: &ObjectRef{Namespace: "user", ObjectID: "alice"}},
})

// budget.pdf is in marketing folder
store.Add(RelationTuple{
    Resource: &ObjectAndRelation{Namespace: "document", ObjectID: "budget.pdf", Relation: "parent"},
    Subject:  &DirectSubject{Object: &ObjectRef{Namespace: "folder", ObjectID: "marketing"}},
})

Query: Can user:alice view document:budget.pdf?

Execution trace:


Check(user:alice, document:budget.pdf#viewer)

1. Look up schema:
   - Namespace: "document"
   - Relation: "viewer"
   - Expression: UNION(COMPUTED_SUBJECTS("editor"), EDGE("parent", folder#viewer))

2. Check direct tuples:
   - Query: (user:alice, document:budget.pdf#viewer)
   - Not found → continue to expression evaluation

3. Evaluate UNION expression:

   Child 1: COMPUTED_SUBJECTS("editor")
     → Check(user:alice, document:budget.pdf#editor)
     → Not found → FALSE

   Child 2: EDGE("parent", folder#viewer)
     → Query tuple store: (document:budget.pdf, O'#parent)
     → Found: O' = folder:marketing
     → Check(user:alice, folder:marketing#viewer)
     → Direct tuple found: (user:alice, folder:marketing#viewer) ✅
     → Return TRUE

   UNION result: FALSE ∪ TRUE = TRUE

4. Return TRUE ✅

Result: Alice can view budget.pdf because she has viewer permission on the parent folder.

Step 7: Safety and State Management

The generic algorithm requires tracking state and enforcing safety limits as we traverse the graph.

EvaluationState Structure

type EvaluationState struct {
    // Cycle detection: tracks visited (namespace, objectID, relation, subject) tuples
    Visited map[VisitKey]bool

    // Current usage counters
    Depth        int32  // Current recursion depth
    NodesVisited int32  // Total nodes visited so far
    TuplesRead   int32  // Total tuples read from storage

    // Budget limits (0 = unlimited)
    MaxDepth  int32  // Maximum recursion depth allowed (typical: 50)
    MaxNodes  int32  // Maximum nodes to visit (typical: 1000)
    MaxTuples int32  // Maximum tuples to read (typical: 10000)

    // Status flag
    HitLimit bool  // Set to true if any limit exceeded
}

Key Fields:

  • Visited: Prevents infinite loops by tracking evaluated (object, relation, subject) tuples

  • Depth: Current recursion depth (incremented on entry, decremented on exit)

  • NodesVisited: Total nodes evaluated (monotonically increasing)

  • MaxDepth, MaxNodes, MaxTuples: Hard limits that trigger fail-safe denial

Fail-Safe Behavior: If any limit is exceeded, evaluation stops immediately and returns FALSE (deny access).

Two Types of Caching in Evaluation

1. Per-Path Cycle Detection (EvaluationState.Visited):

  • Purpose: Prevent infinite loops in the current evaluation path

  • Scope: Current call stack only

  • Behavior: Mark visited on entry, unmark on exit (backtracking)

  • Example: If evaluating A → B → C → A, detect the cycle at the second A

2. Cross-Path Memoization (Optional, not in EvaluationState):

  • Purpose: Avoid re-evaluating the same node multiple times in different paths

  • Scope: Entire authorization check

  • Behavior: Cache result permanently for this check, never clear

  • Example: If document has 3 parents pointing to same grandparent, evaluate grandparent once and reuse result for all 3 paths

Key Difference:

  • Visited map is for safety (prevent cycles)

  • Memo cache is for performance (avoid redundant work)

  • They serve different purposes and should not be conflated

Safety Measures for Edge Traversal

Edge traversal introduces new dangers that require active safety measures:

Problem 1: Cycles in Object Graphs

  • Example: document → folder → document (cycle!)

  • Solution: Track visited tuples in Visited map; skip re-evaluation if already visited in current path

Problem 2: Deep Hierarchies

  • Example: 100-level deep folder nesting

  • Solution: MaxDepth limit (default: 50) stops evaluation if depth exceeded

Problem 3: Multi-Parent Fan-Out

  • Example: Document with 100 parents, each with 100 parents (exponential growth)

  • Solution: MaxNodes limit (default: 1000) stops evaluation if too many nodes visited

Problem 4: Multi-Parent Loops

  • Example: Cycle between folders with multiple parents

  • Solution: VisitKey includes (namespace, objectID, relation, subject), detecting cycles even with multiple parents

How Cycle Detection Works:

  1. Before evaluating a node, check if (namespace, objectID, relation, subject) is in Visited

  2. If yes: return FALSE (cycle detected; prune this path)

  3. If no: mark as visited, evaluate, then unmark (backtrack)

  4. This ensures each node is evaluated once per call path, breaking cycles safely

Schema Validation for Production Safety

Before deploying a schema, validate:

  1. Edge Closure: All EdgeExpression.EdgeTo.Namespace references must exist

    • Example: EDGE("parent", folder#viewer) requires "folder" namespace to exist

  2. Relation Closure: All EdgeTo.Relation references must exist in target namespace

    • Example: folder#viewer must be defined in folder namespace

  3. Edge Acyclicity (Optional): Detect potential cycles in edge definitions

    • Example: If document#viewer → EDGE(parent, folder#viewer) and folder#viewer → EDGE(child, document#viewer), flag as potential cycle

    • Note: Runtime cycle detection handles this, but schema-time detection prevents deployment of obviously problematic schemas

Performance Characteristics

Understanding the cost of edge traversal is important for schema design:

Scenario

Time Complexity

Notes

Single parent

O(D)

D = depth of hierarchy; each level requires one tuple query

N parents

O(N × D)

N = number of parents; evaluates all parents (OR semantics)

Wide fan-out

O(N × D)

Stopped by MaxNodes limit if N × D > 1000

Deep hierarchy

O(D)

Stopped by MaxDepth limit if D > 50

Cycle

O(1) per encounter

Detected via on-stack visited check; path is pruned immediately

Memoization Impact

Without memoization:

  • Multi-parent scenario: O(N × D) where N = parents, D = depth

  • Example: 3 parents, depth 5 → 15 evaluations

With memoization:

  • First path: O(D) to evaluate

  • Subsequent paths: O(1) for cached nodes

  • Example: 3 parents, depth 5 → 5 evaluations (first path) + 0 (cached)

  • Amortized cost: O(D) instead of O(N × D)

When memoization helps most:

  • Diamond-shaped hierarchies (multiple paths to same ancestor)

  • Wide fan-out with shared ancestors

  • Repeated permission checks on same object graph

When memoization doesn't help:

  • Disjoint hierarchies (no shared ancestors)

  • Single-parent chains (no redundant evaluations)

Production Optimization: Indexing Strategy

Indexing for Fast Lookups:

  • Index tuples by (Resource.Namespace, Resource.ObjectID, Resource.Relation) for fast direct tuple lookups

  • Index tuples by (Resource.Namespace, Resource.ObjectID) for edge queries (finding all edges from an object)

  • Consider reverse index by Subject for ListObjects queries

  • With proper indexing, OP_EDGE lookups are O(1)–O(log n) per step

Memoization Strategy:

  • Cache evaluation results for (subject, resource#relation) within a single authorization check to avoid re-evaluating the same node multiple times

  • Memoization amortizes cost: First evaluation is O(D), subsequent lookups are O(1)

  • Clear memo cache after each top-level Check() call (don't cache across requests)

  • Important: Keep per-request memoization outside EvaluationState; EvaluationState handles safety/on-stack tracking only

Example: If document has 3 parents that all point to the same grandparent, memoization ensures we only evaluate the grandparent once, not 3 times.

Optimization Tips

  • Keep hierarchies shallow (depth < 20) to minimize query chains

  • Limit parents per object (typically < 10) to avoid fan-out explosion

  • Use MaxNodes and MaxDepth conservatively to catch pathological schemas early

  • Implement memoization for diamond-shaped hierarchies with shared ancestors

Testing the Extended Model (OP_EDGE)

Note: All scenarios below use the namespace definition from Step 5 (document and folder namespaces with the UNION expression for document#viewer). We'll test how the authorization algorithm evaluates different permission checks using this consistent schema.

Scenario 1: Simple Folder Inheritance

Setup:

// Alice can view the marketing folder
store.Add(RelationTuple{
    Resource: &ObjectAndRelation{Namespace: "folder", ObjectID: "marketing", Relation: "viewer"},
    Subject:  &DirectSubject{Object: &ObjectRef{Namespace: "user", ObjectID: "alice"}},
})

// budget.pdf is in the marketing folder
store.Add(RelationTuple{
    Resource: &ObjectAndRelation{Namespace: "document", ObjectID: "budget.pdf", Relation: "parent"},
    Subject:  &DirectSubject{Object: &ObjectRef{Namespace: "folder", ObjectID: "marketing"}},
})

Check: "Can Alice view budget.pdf?"

  1. Direct check: (user:alice, document:budget.pdf#viewer) → Not found

  2. Evaluate expression (UNION):

    • Child 1: COMPUTED_SUBJECTS("editor") → Check editor → Not found

    • Child 2: EDGE("parent", folder#viewer)

      • Find parent: folder:marketing

      • Check: (user:alice, folder:marketing#viewer) → Found ✅

  3. Result: TRUE

Scenario 2: Nested Folders

Setup:

// Alice can view the company folder
store.Add(RelationTuple{
    Resource: &ObjectAndRelation{Namespace: "folder", ObjectID: "company", Relation: "viewer"},
    Subject:  &DirectSubject{Object: &ObjectRef{Namespace: "user", ObjectID: "alice"}},
})

// marketing folder is in company folder
store.Add(RelationTuple{
    Resource: &ObjectAndRelation{Namespace: "folder", ObjectID: "marketing", Relation: "parent"},
    Subject:  &DirectSubject{Object: &ObjectRef{Namespace: "folder", ObjectID: "company"}},
})

// budget.pdf is in marketing folder
store.Add(RelationTuple{
    Resource: &ObjectAndRelation{Namespace: "document", ObjectID: "budget.pdf", Relation: "parent"},
    Subject:  &DirectSubject{Object: &ObjectRef{Namespace: "folder", ObjectID: "marketing"}},
})

Check: "Can Alice view budget.pdf?"

  • Traversal: document → folder:marketing → folder:company → Found viewer ✅

  • Result: TRUE (deep hierarchies work correctly)

Edge Case 1: Cycle Detection (Pruning in Action)

Setup:

// Create a cycle: folder A → folder B → folder A
store.Add(RelationTuple{
    Resource: &ObjectAndRelation{Namespace: "folder", ObjectID: "a", Relation: "parent"},
    Subject:  &DirectSubject{Object: &ObjectRef{Namespace: "folder", ObjectID: "b"}},
})
store.Add(RelationTuple{
    Resource: &ObjectAndRelation{Namespace: "folder", ObjectID: "b", Relation: "parent"},
    Subject:  &DirectSubject{Object: &ObjectRef{Namespace: "folder", ObjectID: "a"}},
})

// Alice can view folder A
store.Add(RelationTuple{
    Resource: &ObjectAndRelation{Namespace: "folder", ObjectID: "a", Relation: "viewer"},
    Subject:  &DirectSubject{Object: &ObjectRef{Namespace: "user", ObjectID: "alice"}},
})

// Document is in folder B
store.Add(RelationTuple{
    Resource: &ObjectAndRelation{Namespace: "document", ObjectID: "doc", Relation: "parent"},
    Subject:  &DirectSubject{Object: &ObjectRef{Namespace: "folder", ObjectID: "b"}},
})

Check: "Can Alice view doc?"

  • Traversal: document → folder:b → folder:a (found viewer) → folder:b (already visited, skip)

  • Result: TRUE (cycle is safely handled)

Edge Case 2: Missing Parent Edge (Disconnected Objects)

Setup:

// Document has no parent edge
// Alice can view the folder, but document isn't connected

store.Add(RelationTuple{
    Resource: &ObjectAndRelation{Namespace: "folder", ObjectID: "marketing", Relation: "viewer"},
    Subject:  &DirectSubject{Object: &ObjectRef{Namespace: "user", ObjectID: "alice"}},
})

// No parent edge for document

Check: "Can Alice view doc?"

  • Direct check: Not found

  • Evaluate EDGE("parent", folder#viewer): No parent edge found

  • Result: FALSE (missing edge means no inheritance)

Real-World Context

This pattern appears in every system with hierarchical resources:

Google Drive (Folder Inheritance)

User can view folder → automatically view all documents in folder. Nested folders inherit permissions from parents. This is the canonical example of OP_EDGE in practice.

GitHub Organizations (Team Hierarchies)

Team membership can be hierarchical; repository permissions are granted via teams/org policies and effectively "flow" through team → repo bindings.

Dropbox (Shared Folder Hierarchies)

User has access to shared folder → automatically access all nested content. Permissions flow down the folder tree via parent edges.

Enterprise File Systems (NTFS, Active Directory)

User has permission on parent directory → inherits to child objects. ACL inheritance through directory hierarchies is implemented using edge-like traversal.

Comparison: Post 3 vs. Post 4 Algorithm Complexity

Post 3's algorithm evaluated relations within a single object. Post 4 extends this to cross-object traversal:

Aspect

Post 3 (ReBAC v1)

Post 4 (ReBAC v2)

Scope

Single object

Multiple objects (graph)

Operations

5 (DIRECT, COMPUTED_SUBJECTS, UNION, INTERSECTION, EXCLUSION)

6 (adds OP_EDGE)

Recursion

Depth limited by relation chain length

Depth limited by hierarchy depth + MaxDepth

Cycle Risk

Low (same object, finite relations)

High (cycles in object graph)

Cycle Handling

Not needed

Pruning with VisitKey

State Tracking

Minimal (just recursion depth)

Comprehensive (EvaluationState with limits)

Typical Depth

3-5 levels

5-50 levels

Typical Nodes

1-10

10-1000

Key difference: Post 3 was safe by design (finite relation chains). Post 4 requires active safety measures (cycle detection, depth/node limits) because object graphs can be arbitrarily complex.

Takeaways

  1. Edge expressions enable cross-object permission inheritance: Instead of storing permissions on every object, you define edges that traverse to parent objects and reuse their permissions.

  2. Graph traversal with cycle detection keeps hierarchies safe: By tracking visited (object, relation) pairs and limiting depth, we prevent infinite loops while supporting deep hierarchies.

  3. Hierarchical permissions emerge from edge composition: Combining edges with boolean algebra from Post 3 gives you the full power of hierarchical access control.

What We've Built

We now have ReBAC v2 with Edge Traversal:

  • Direct permissions (Post 1): OP_DIRECT

  • Role-based permissions (Post 2): SubjectSet references

  • Boolean combinations (Post 3): OP_UNION, OP_INTERSECTION, OP_EXCLUSION, OP_COMPUTED_SUBJECTS

  • Cross-object inheritance (new in Post 4): OP_EDGE

The authorization check now performs graph traversal across object boundaries, enabling hierarchical permission inheritance without storing redundant tuples.

Limitations (What's Still Missing)

Our model now handles hierarchical permissions, but we still can't express:

  • Conditional access: "Alice can only access during business hours"

  • Attribute-based conditions: "Users can access if department matches document classification"

  • Time-limited permissions: "This access expires on 2025-12-31"

These require contextual evaluation that we'll tackle in the next posts.

Up next (Post 5): Conditional Access (ABAC v1) We'll add caveats so the model can say "Alice can view this document, but only during business hours." This introduces context-aware evaluation and the foundation for attribute-based access control.

Keep Reading

© 2026 Sub-Microseconds.
Report abusePrivacy policyTerms of use
beehiivPowered by beehiiv