Graph Traversal & Relationships

Advanced guide to graph operations, edge semantics, and complex hierarchy queries. Learn how to work with DAGs, multiple relationship types, and optimize graph traversals.

Overview

This guide covers advanced graph concepts beyond basic hierarchies:

Edge Table Structure: Understanding the underlying data model
Direction Semantics: How edges are traversed
Multiple Relationship Types: Matrix organizations and cross-functional teams
DAG Support: Nodes with multiple parents
Performance Optimization: Indexing, caching, and query strategies
Complex Queries: Multi-hop traversal, path finding, subgraph extraction

Graph Configuration

Edge Table Structure

When you enable hierarchy: true or graph.enabled: true, Taruvi automatically creates an edges table:

Table Name Format: {table_name}_edges

Example: For table employees, the edges table is employees_edges

Schema:

CREATE TABLE employees_edges (
    id SERIAL PRIMARY KEY,
    from_id INTEGER NOT NULL,      -- Source node
    to_id INTEGER NOT NULL,        -- Target node
    type VARCHAR(50) NOT NULL,     -- Relationship type
    metadata JSONB,                -- Additional edge data
    created_at TIMESTAMP DEFAULT NOW(),

    FOREIGN KEY (from_id) REFERENCES employees(id) ON DELETE CASCADE,
    FOREIGN KEY (from_id) REFERENCES employees(id) ON DELETE CASCADE
);

-- Indexes for fast lookups
CREATE INDEX idx_edges_from_type ON employees_edges(from_id, type);
CREATE INDEX idx_edges_to_type ON employees_edges(to_id, type);
CREATE INDEX idx_edges_type ON employees_edges(type);

Relationship Types Definition

Define relationship types in your table schema:

{
  "hierarchy": true,
  "graph": {
    "enabled": true,
    "types": [
      {
        "name": "manager",
        "inverse": "reports",
        "constraints": {
          "max_outgoing": 1
        },
        "description": "Primary reporting line"
      },
      {
        "name": "dotted_line",
        "inverse": "dotted_reports",
        "description": "Matrix reporting (cross-functional)"
      },
      {
        "name": "mentor",
        "inverse": "mentees",
        "description": "Mentorship relationship"
      }
    ]
  }
}

Fields:

name: Relationship type identifier (used in queries)
inverse: Label for reverse direction (e.g., "manager" → "reports")
constraints: Optional validation rules
- max_outgoing: Maximum edges from a node (e.g., 1 for single manager)
- max_incoming: Maximum edges to a node
description: Human-readable documentation

Edge Direction Semantics

Understanding edge direction is critical for correct queries.

Edge Format

Format: from_id → to_id (type: "relationship_name")

Meaning: "from_id's relationship_name is to_id"

Example:

2 → 1 (type: "manager")

This means: "Employee 2's manager is Employee 1" Or: "Employee 2 reports to Employee 1"

Direction in Traversal

When traversing the graph, direction determines which edges to follow:

Outgoing Traversal

Direction: outgoing

SQL: SELECT to_id WHERE from_id = start_node

Meaning: Follow edges FORWARD (find who this node points TO)

Use case: Finding ancestors/parents/managers

Example:

GET /data/4?include=ancestors
# Traverses OUTGOING from node 4
# Finds: 4 → 2 (manager) and 2 → 1 (manager)
# Returns: Bob (2) and Alice (1)

graph LR
    David[4: David] -->|manager| Bob[2: Bob]
    Bob -->|manager| Alice[1: Alice]

    style David fill:#e1f5ff
    style Bob fill:#fff4e6
    style Alice fill:#fff4e6

Incoming Traversal

Direction: incoming

SQL: SELECT from_id WHERE to_id = start_node

Meaning: Follow edges BACKWARD (find who points TO this node)

Use case: Finding descendants/children/reports

Example:

GET /data/1?include=descendants
# Traverses INCOMING to node 1
# Finds: 2 → 1 (manager) and 3 → 1 (manager)
# Returns: Bob (2) and Carol (3)

graph LR
    Bob[2: Bob] -->|manager| Alice[1: Alice]
    Carol[3: Carol] -->|manager| Alice

    style Alice fill:#e1f5ff
    style Bob fill:#fff4e6
    style Carol fill:#fff4e6

Quick Reference

Query Type	Direction	SQL Condition	Finds
Descendants (reports)	`incoming`	`to_id = node`	Who reports to this node
Ancestors (managers)	`outgoing`	`from_id = node`	Who this node reports to

Traversal Operations

Direct Relationships (include parameter)

Query one or two hops from a node:

GET Descendants

Query:

GET /data/1?include=descendants&depth=2

Traversal:

Start at node 1
Follow INCOMING edges (find who points to 1)
Continue for 2 levels

Response Structure:

{
  "data": {
    "id": 1,
    "name": "Alice Chen"
  },
  "reports": [
    {"id": 2, "name": "Bob Smith", "_depth": 1},
    {"id": 3, "name": "Carol White", "_depth": 1},
    {"id": 4, "name": "David Lee", "_depth": 2}
  ]
}

GET Ancestors

Query:

GET /data/4?include=ancestors

Traversal:

Start at node 4
Follow OUTGOING edges (find who 4 points to)
Continue until no more edges

Response Structure:

{
  "data": {
    "id": 4,
    "name": "David Lee"
  },
  "manager": [
    {"id": 2, "name": "Bob Smith", "_depth": 1},
    {"id": 1, "name": "Alice Chen", "_depth": 2}
  ]
}

GET Both Directions

Query:

GET /data/2?include=both&depth=1

Traversal:

Follow INCOMING edges (find descendants)
Follow OUTGOING edges (find ancestors)
Depth 1 for both

Response Structure:

{
  "data": {
    "id": 2,
    "name": "Bob Smith"
  },
  "reports": [
    {"id": 4, "name": "David Lee", "_depth": 1}
  ],
  "manager": [
    {"id": 1, "name": "Alice Chen", "_depth": 1}
  ]
}

Tree Traversal (format=tree)

Nested structure showing parent-child relationships:

Query:

GET /data/1?format=tree&depth=3

Traversal:

Build tree from node 1 (or all roots if no ID specified)
Follow INCOMING edges for children
Follow OUTGOING edges for ancestors (to show full context)
Nest children within parents
Limit to depth 3

Response Structure:

{
  "data": [{
    "id": 1,
    "name": "Alice Chen",
    "_depth": 0,
    "children": [
      {
        "id": 2,
        "name": "Bob Smith",
        "_depth": 1,
        "_relationship_type": "manager",
        "children": [
          {
            "id": 4,
            "name": "David Lee",
            "_depth": 2,
            "_relationship_type": "manager",
            "children": []
          }
        ]
      },
      {
        "id": 3,
        "name": "Carol White",
        "_depth": 1,
        "_relationship_type": "manager",
        "children": []
      }
    ]
  }],
  "total": 4
}

Use Cases:

Org chart visualization
Category tree display
File system browser
Department hierarchy

Graph Traversal (format=graph)

Returns complete subgraph as nodes + edges:

Query:

GET /data/?format=graph&graph_types=manager

Traversal:

Get all nodes in result set
Query edges table for edges connecting those nodes
Filter by relationship type if specified

Response Structure:

{
  "data": {
    "nodes": [
      {
        "id": 1,
        "name": "Alice Chen",
        "title": "CEO"
      },
      {
        "id": 2,
        "name": "Bob Smith",
        "title": "VP Engineering"
      }
    ],
    "edges": [
      {
        "id": 9,
        "from": 2,
        "to": 1,
        "type": "manager",
        "metadata": {"primary": true}
      }
    ]
  },
  "total": 4
}

Use Cases:

Network visualization
Relationship analysis
Graph databases integration
Custom graph algorithms

Advanced Queries

Multi-hop Traversal

Find all nodes within N hops:

3-hop traversal:

GET /data/1?include=descendants&depth=3

Returns:

Depth 1: Direct reports
Depth 2: Reports' reports
Depth 3: Third level down

Performance: O(V + E) where V=nodes, E=edges within depth

Path Finding

Find all paths between two nodes:

Query:

# Find path from David (4) to CEO (1)
GET /data/4?include=ancestors

Response shows complete path:

{
  "data": {"id": 4, "name": "David Lee"},
  "manager": [
    {"id": 2, "name": "Bob Smith", "_depth": 1},
    {"id": 1, "name": "Alice Chen", "_depth": 2}
  ]
}

Path: David → Bob → Alice

Filtering by Type

Query specific relationship types:

Single type:

GET /data/?format=graph&graph_types=manager

Multiple types:

GET /data/?format=graph&graph_types=manager,dotted_line

Response includes only specified types:

{
  "data": {
    "edges": [
      {"from": 2, "to": 1, "type": "manager"},
      {"from": 5, "to": 3, "type": "dotted_line"}
    ]
  }
}

Cross-functional Teams

Matrix organizations with multiple reporting lines:

Schema:

{
  "graph": {
    "types": [
      {
        "name": "manager",
        "inverse": "reports",
        "description": "Primary reporting line"
      },
      {
        "name": "dotted_line",
        "inverse": "dotted_reports",
        "description": "Matrix reporting"
      }
    ]
  }
}

Example:

Alice (CEO)
├── Bob (VP Eng) [primary]
│   └── Emma (PM) [primary]
└── Carol (VP Sales) [primary]
    └── Emma (PM) [dotted_line]  # Emma has two managers!

Query Emma's all managers:

GET /data/5?include=ancestors

Response:

{
  "data": {"id": 5, "name": "Emma Davis"},
  "manager": [
    {"id": 2, "name": "Bob Smith", "_depth": 1, "_relationship_type": "manager"},
    {"id": 3, "name": "Carol White", "_depth": 1, "_relationship_type": "dotted_line"},
    {"id": 1, "name": "Alice Chen", "_depth": 2, "_relationship_type": "manager"}
  ]
}

Performance Optimization

Index Usage

Edges table has composite indexes for fast lookups:

-- Descendant queries (incoming direction)
CREATE INDEX idx_edges_to_type ON employees_edges(to_id, type);

-- Ancestor queries (outgoing direction)
CREATE INDEX idx_edges_from_type ON employees_edges(from_id, type);

-- Type filtering
CREATE INDEX idx_edges_type ON employees_edges(type);

Query Plan:

EXPLAIN SELECT from_id FROM employees_edges WHERE to_id = 1 AND type = 'manager';

-- Uses index scan (fast!)
Index Scan using idx_edges_to_type on employees_edges
  Index Cond: ((to_id = 1) AND (type = 'manager'))

Query Complexity

Time Complexity:

Operation	Complexity	Notes
Direct relationships	O(1)	Indexed lookup
BFS traversal	O(V + E)	V=vertices, E=edges in subgraph
Depth-limited	O(k * b)	k=depth, b=branching factor
Full graph	O(V + E)	All nodes and edges

Space Complexity:

Include format: O(V) - flat list
Tree format: O(V) - nested structure
Graph format: O(V + E) - nodes + edges

Depth Limits

Prevent excessive recursion:

Settings:

# settings.py
DATA_SERVICE_GRAPH_MAX_DEPTH = 10  # Default

Request:

GET /data/1?include=descendants&depth=999

Response:

{
  "error": "Validation failed",
  "detail": "depth exceeds maximum allowed (10)"
}

Recommendations:

Small org (<100): depth=10 is fine
Medium org (100-1000): depth=7
Large org (>1000): depth=5

Caching Strategies

When to cache:

✅ Static org charts (updated infrequently)
✅ Department hierarchies (stable structure)
✅ Category trees (rarely change)

When NOT to cache:

❌ Real-time team updates
❌ Dynamic permission checks
❌ Frequently changing relationships

Cache key strategy:

cache_key = f"hierarchy:{table_name}:{node_id}:{include}:{depth}:{types}"

TTL recommendations:

Org chart: 1 hour
Permissions: 5 minutes
Categories: 24 hours

Real-world Examples

Finding All Reports (3 levels)

Scenario: CEO wants to see entire organization 3 levels deep

Query:

GET /api/apps/hr/datatables/employees/data/1?include=descendants&depth=3

Expected Response:

{
  "data": {
    "id": 1,
    "name": "Alice Chen",
    "title": "CEO"
  },
  "reports": [
    {"id": 2, "name": "Bob Smith", "title": "VP Engineering", "_depth": 1},
    {"id": 3, "name": "Carol White", "title": "VP Sales", "_depth": 1},
    {"id": 4, "name": "David Lee", "title": "Senior Engineer", "_depth": 2},
    {"id": 5, "name": "Emma Davis", "title": "Product Manager", "_depth": 2},
    {"id": 6, "name": "Frank Wilson", "title": "Sales Engineer", "_depth": 2},
    {"id": 7, "name": "Grace Lee", "title": "Junior Engineer", "_depth": 3}
  ]
}

Use case: Executive dashboard showing organizational reach

Manager Chain to CEO

Scenario: Employee profile showing reporting path to top

Query:

GET /api/apps/hr/datatables/employees/data/7?include=ancestors

Expected Response:

{
  "data": {
    "id": 7,
    "name": "Grace Lee",
    "title": "Junior Engineer"
  },
  "manager": [
    {"id": 4, "name": "David Lee", "title": "Senior Engineer", "_depth": 1},
    {"id": 2, "name": "Bob Smith", "title": "VP Engineering", "_depth": 2},
    {"id": 1, "name": "Alice Chen", "title": "CEO", "_depth": 3}
  ]
}

Use case: "Reports to" section on employee profile page

Cross-department Collaboration

Scenario: Product Manager with dotted line to Sales

Setup:

-- Emma (5) reports primarily to Bob (2)
INSERT INTO employees_edges (from_id, to_id, type, metadata)
VALUES (5, 2, 'manager', '{"primary": true}'::jsonb);

-- Emma also has dotted line to Carol (3)
INSERT INTO employees_edges (from_id, to_id, type, metadata)
VALUES (5, 3, 'dotted_line', '{"percentage": 30}'::jsonb);

Query all reporting lines:

GET /api/apps/hr/datatables/employees/data/5?include=ancestors

Response:

{
  "data": {
    "id": 5,
    "name": "Emma Davis",
    "title": "Product Manager"
  },
  "manager": [
    {
      "id": 2,
      "name": "Bob Smith",
      "title": "VP Engineering",
      "_depth": 1,
      "_relationship_type": "manager"
    },
    {
      "id": 3,
      "name": "Carol White",
      "title": "VP Sales",
      "_depth": 1,
      "_relationship_type": "dotted_line"
    },
    {
      "id": 1,
      "name": "Alice Chen",
      "title": "CEO",
      "_depth": 2,
      "_relationship_type": "manager"
    }
  ]
}

Use case: Matrix organization, resource allocation

Permission Inheritance

Scenario: Find all users who inherit access through manager

Query:

GET /api/apps/hr/datatables/employees/data/2?include=descendants

Response:

{
  "data": {
    "id": 2,
    "name": "Bob Smith"
  },
  "reports": [
    {"id": 4, "name": "David Lee", "_depth": 1},
    {"id": 5, "name": "Emma Davis", "_depth": 1},
    {"id": 7, "name": "Grace Lee", "_depth": 2}
  ]
}

Use case:

Permission audit: Who has access through Bob?
Security check: Revoke access for Bob's team
Notification: Broadcast message to Bob's org

Comparison with Other Approaches

vs. Foreign Keys

Hierarchy API:

GET /data/1?include=descendants&depth=3
# Returns: All descendants in single query

Foreign Key Approach:

# Multiple database queries needed
manager = Employee.objects.get(id=1)
level1 = Employee.objects.filter(manager=manager)
level2 = Employee.objects.filter(manager__in=level1)
level3 = Employee.objects.filter(manager__in=level2)

# N+1 query problem!

Advantages:

✅ Single query vs. multiple
✅ Handles any depth
✅ Supports DAGs (multiple parents)
✅ Flexible relationship types

vs. Adjacency List

Hierarchy API:

Edges stored separately in edges table
Multiple relationship types supported
Direction explicit in queries

Adjacency List:

# parent_id stored in employee table
class Employee:
    parent_id = ForeignKey('self')

# Limited to single parent
# No relationship types
# Direction implicit

vs. Closure Table

Hierarchy API:

Uses recursive CTEs for traversal
Edges table only stores direct relationships
Computed on-the-fly

Closure Table:

-- Pre-computed paths table
CREATE TABLE employee_paths (
    ancestor_id INT,
    descendant_id INT,
    depth INT
);

-- Must rebuild on every change
-- High storage overhead

Trade-offs:

Hierarchy API: Slower queries, faster writes
Closure Table: Faster queries, slower writes

Next Steps

Hierarchy API Reference - Complete API specification
Hierarchical Data & Org Charts - Basic hierarchy guide
Data Service Querying - Standard query operations

Overview​

Graph Configuration​

Edge Table Structure​

Relationship Types Definition​

Edge Direction Semantics​

Edge Format​

Direction in Traversal​

Outgoing Traversal​

Incoming Traversal​

Quick Reference​

Traversal Operations​

Direct Relationships (include parameter)​

GET Descendants​

GET Ancestors​

GET Both Directions​

Tree Traversal (format=tree)​

Graph Traversal (format=graph)​

Advanced Queries​

Multi-hop Traversal​

Path Finding​

Filtering by Type​

Cross-functional Teams​

Performance Optimization​

Index Usage​

Query Complexity​

Depth Limits​

Caching Strategies​

Real-world Examples​

Finding All Reports (3 levels)​

Manager Chain to CEO​

Cross-department Collaboration​

Permission Inheritance​

Comparison with Other Approaches​

vs. Foreign Keys​

vs. Adjacency List​

vs. Closure Table​

Next Steps​

Related Documentation​

Overview

Graph Configuration

Edge Table Structure

Relationship Types Definition

Edge Direction Semantics

Edge Format

Direction in Traversal

Outgoing Traversal

Incoming Traversal

Quick Reference

Traversal Operations

Direct Relationships (include parameter)

GET Descendants

GET Ancestors

GET Both Directions

Tree Traversal (format=tree)

Graph Traversal (format=graph)

Advanced Queries

Multi-hop Traversal

Path Finding

Filtering by Type

Cross-functional Teams

Performance Optimization

Index Usage

Query Complexity

Depth Limits

Caching Strategies

Real-world Examples

Finding All Reports (3 levels)

Manager Chain to CEO

Cross-department Collaboration

Permission Inheritance

Comparison with Other Approaches

vs. Foreign Keys

vs. Adjacency List

vs. Closure Table

Next Steps

Related Documentation