Graph Queries in PostgreSQL: Recursive Traversal, Shortest Path, and Social Graphs

Graph databases like Neo4j are purpose-built for connected data — but most teams already have PostgreSQL, and PostgreSQL handles a surprising range of graph queries well with WITH RECURSIVE. Social graphs, org charts, permission inheritance, dependency graphs, route finding — all achievable without adding another database.

This guide covers the patterns: tree traversal, graph BFS/DFS, shortest path, cycle detection, and the performance techniques that keep recursive queries from blowing up on large datasets.

Foundational Schema: Adjacency List

The adjacency list — a table of edges — is the universal representation for graphs in SQL:

-- Generic directed graph: nodes + edges
CREATE TABLE nodes (
  id          UUID PRIMARY KEY DEFAULT gen_random_uuid(),
  type        TEXT NOT NULL,    -- 'user', 'team', 'project', etc.
  label       TEXT NOT NULL,
  properties  JSONB NOT NULL DEFAULT '{}',
  created_at  TIMESTAMPTZ NOT NULL DEFAULT NOW()
);

CREATE TABLE edges (
  id          UUID PRIMARY KEY DEFAULT gen_random_uuid(),
  from_node   UUID NOT NULL REFERENCES nodes(id) ON DELETE CASCADE,
  to_node     UUID NOT NULL REFERENCES nodes(id) ON DELETE CASCADE,
  edge_type   TEXT NOT NULL,    -- 'FOLLOWS', 'MANAGES', 'MEMBER_OF', 'DEPENDS_ON'
  weight      NUMERIC,          -- For weighted graphs (distances, costs)
  properties  JSONB NOT NULL DEFAULT '{}',
  created_at  TIMESTAMPTZ NOT NULL DEFAULT NOW(),

  UNIQUE(from_node, to_node, edge_type)
);

-- Indexes for traversal performance
CREATE INDEX idx_edges_from  ON edges(from_node, edge_type);
CREATE INDEX idx_edges_to    ON edges(to_node, edge_type);
CREATE INDEX idx_edges_type  ON edges(edge_type);

For domain-specific graphs, specialised tables are cleaner:

-- Social graph: who follows whom
CREATE TABLE user_follows (
  follower_id UUID NOT NULL REFERENCES users(id),
  followee_id UUID NOT NULL REFERENCES users(id),
  followed_at TIMESTAMPTZ NOT NULL DEFAULT NOW(),
  PRIMARY KEY (follower_id, followee_id),
  CHECK (follower_id <> followee_id)
);

CREATE INDEX idx_follows_follower ON user_follows(follower_id);
CREATE INDEX idx_follows_followee ON user_follows(followee_id);

-- Org chart: reports_to hierarchy
CREATE TABLE org_structure (
  user_id     UUID PRIMARY KEY REFERENCES users(id),
  manager_id  UUID REFERENCES users(id),
  department  TEXT NOT NULL,
  title       TEXT NOT NULL
);

CREATE INDEX idx_org_manager ON org_structure(manager_id);

Tree Traversal: All Descendants

Find all users reporting (directly or indirectly) to a given manager:

WITH RECURSIVE subordinates AS (
  -- Base case: direct reports
  SELECT
    u.id,
    u.name,
    u.email,
    o.title,
    o.manager_id,
    1 AS depth,
    ARRAY[u.id] AS path  -- Track path to detect cycles
  FROM org_structure o
  JOIN users u ON u.id = o.user_id
  WHERE o.manager_id = $1  -- Root manager ID

  UNION ALL

  -- Recursive case: their reports
  SELECT
    u.id,
    u.name,
    u.email,
    o.title,
    o.manager_id,
    s.depth + 1,
    s.path || u.id
  FROM org_structure o
  JOIN users u ON u.id = o.user_id
  JOIN subordinates s ON o.manager_id = s.id
  WHERE
    u.id <> ALL(s.path)  -- Cycle guard
    AND s.depth < 10     -- Depth limit
)
SELECT
  id,
  name,
  email,
  title,
  depth,
  path
FROM subordinates
ORDER BY depth, name;

All Ancestors (Upward Traversal)

Find the full reporting chain above a given employee:

WITH RECURSIVE managers AS (
  -- Base: the employee themselves
  SELECT
    u.id,
    u.name,
    o.title,
    o.manager_id,
    0 AS depth
  FROM org_structure o
  JOIN users u ON u.id = o.user_id
  WHERE u.id = $1  -- Employee ID

  UNION ALL

  -- Recursive: walk up the tree
  SELECT
    u.id,
    u.name,
    o.title,
    o.manager_id,
    m.depth - 1
  FROM org_structure o
  JOIN users u ON u.id = o.user_id
  JOIN managers m ON o.user_id = m.manager_id
  WHERE o.manager_id IS NOT NULL
)
SELECT id, name, title, depth
FROM managers
WHERE depth < 0  -- Exclude the employee themselves
ORDER BY depth DESC;  -- Root manager first

Shortest Path: BFS

Find the shortest connection path between two users in a social graph:

-- BFS: shortest path from user A to user B
WITH RECURSIVE bfs AS (
  -- Base: start from source node
  SELECT
    follower_id AS from_node,
    followee_id AS to_node,
    ARRAY[follower_id, followee_id] AS path,
    1 AS depth
  FROM user_follows
  WHERE follower_id = $1  -- Source user

  UNION ALL

  -- Expand frontier one hop at a time
  SELECT
    bfs.to_node,
    f.followee_id,
    bfs.path || f.followee_id,
    bfs.depth + 1
  FROM bfs
  JOIN user_follows f ON f.follower_id = bfs.to_node
  WHERE
    f.followee_id <> ALL(bfs.path)  -- No revisiting
    AND bfs.depth < 6               -- 6 degrees of separation limit
    AND NOT EXISTS (                -- Stop once target found
      SELECT 1 FROM bfs b2
      WHERE b2.to_node = $2
    )
)
SELECT path, depth
FROM bfs
WHERE to_node = $2          -- Target user
ORDER BY depth ASC
LIMIT 1;                    -- Shortest path only

Degree of Connection

-- Check if two users are connected within N hops
WITH RECURSIVE reach AS (
  SELECT followee_id AS node, 1 AS hops, ARRAY[follower_id] AS visited
  FROM user_follows
  WHERE follower_id = $1

  UNION ALL

  SELECT f.followee_id, r.hops + 1, r.visited || f.follower_id
  FROM user_follows f
  JOIN reach r ON r.node = f.follower_id
  WHERE
    f.followee_id <> ALL(r.visited)
    AND r.hops < $3  -- max hops
)
SELECT
  CASE WHEN EXISTS (SELECT 1 FROM reach WHERE node = $2)
    THEN (SELECT MIN(hops) FROM reach WHERE node = $2)
    ELSE -1
  END AS degree_of_separation;

Common Connections (Friends of Friends)

-- Users followed by both $1 and $2 (mutual follows)
SELECT u.id, u.name, u.avatar_url
FROM user_follows f1
JOIN user_follows f2 ON f1.followee_id = f2.followee_id
JOIN users u ON u.id = f1.followee_id
WHERE f1.follower_id = $1
  AND f2.follower_id = $2
ORDER BY u.name;

-- People $1 might know: followed by people $1 follows (2nd degree)
SELECT
  u.id,
  u.name,
  COUNT(DISTINCT connector.id) AS mutual_connections
FROM user_follows f1                            -- $1 follows connector
JOIN user_follows f2 ON f2.follower_id = f1.followee_id  -- connector follows suggestion
JOIN users u ON u.id = f2.followee_id
JOIN users connector ON connector.id = f1.followee_id
WHERE f1.follower_id = $1
  AND f2.followee_id <> $1                      -- Not $1 themselves
  AND NOT EXISTS (                              -- $1 doesn't already follow them
    SELECT 1 FROM user_follows
    WHERE follower_id = $1 AND followee_id = f2.followee_id
  )
GROUP BY u.id, u.name
ORDER BY mutual_connections DESC
LIMIT 20;

Permission Inheritance Graph

-- Role permission graph: role inherits from parent roles
CREATE TABLE roles (
  id         UUID PRIMARY KEY DEFAULT gen_random_uuid(),
  name       TEXT NOT NULL UNIQUE,
  parent_id  UUID REFERENCES roles(id)   -- role inheritance
);

CREATE TABLE role_permissions (
  role_id       UUID NOT NULL REFERENCES roles(id),
  permission    TEXT NOT NULL,
  PRIMARY KEY (role_id, permission)
);

-- All permissions for a role (including inherited)
WITH RECURSIVE role_hierarchy AS (
  SELECT id, name, parent_id
  FROM roles
  WHERE id = $1  -- Starting role

  UNION ALL

  SELECT r.id, r.name, r.parent_id
  FROM roles r
  JOIN role_hierarchy rh ON r.id = rh.parent_id
)
SELECT DISTINCT rp.permission
FROM role_hierarchy rh
JOIN role_permissions rp ON rp.role_id = rh.id
ORDER BY rp.permission;

Cycle Detection

-- Detect cycles in a directed graph (e.g., task dependencies)
CREATE TABLE task_dependencies (
  task_id        UUID NOT NULL REFERENCES tasks(id),
  depends_on_id  UUID NOT NULL REFERENCES tasks(id),
  PRIMARY KEY (task_id, depends_on_id),
  CHECK (task_id <> depends_on_id)
);

-- Would adding edge (new_task → new_dep) create a cycle?
-- Check if new_task is reachable FROM new_dep (if so, adding new_task→new_dep creates a cycle)
WITH RECURSIVE reachable AS (
  SELECT depends_on_id AS node, ARRAY[task_id] AS visited
  FROM task_dependencies
  WHERE task_id = $2  -- new_dep

  UNION ALL

  SELECT td.depends_on_id, r.visited || td.task_id
  FROM task_dependencies td
  JOIN reachable r ON td.task_id = r.node
  WHERE td.depends_on_id <> ALL(r.visited)
)
SELECT EXISTS (
  SELECT 1 FROM reachable WHERE node = $1  -- new_task
) AS would_create_cycle;

TypeScript Query Wrappers

// lib/graph/queries.ts
import { prisma } from "@/lib/prisma";

export async function getSubordinates(
  managerId: string,
  maxDepth = 10
): Promise<Array<{ id: string; name: string; title: string; depth: number }>> {
  return prisma.$queryRaw`
    WITH RECURSIVE subordinates AS (
      SELECT u.id, u.name, o.title, 1 AS depth, ARRAY[u.id::uuid] AS path
      FROM org_structure o
      JOIN users u ON u.id = o.user_id
      WHERE o.manager_id = ${managerId}::uuid

      UNION ALL

      SELECT u.id, u.name, o.title, s.depth + 1, s.path || u.id::uuid
      FROM org_structure o
      JOIN users u ON u.id = o.user_id
      JOIN subordinates s ON o.manager_id = s.id
      WHERE u.id <> ALL(s.path) AND s.depth < ${maxDepth}
    )
    SELECT id, name, title, depth FROM subordinates ORDER BY depth, name
  `;
}

export async function getShortestPath(
  fromUserId: string,
  toUserId: string,
  maxHops = 6
): Promise<string[] | null> {
  const rows = await prisma.$queryRaw<Array<{ path: string[] }>>`
    WITH RECURSIVE bfs AS (
      SELECT
        followee_id AS to_node,
        ARRAY[follower_id, followee_id]::uuid[] AS path,
        1 AS depth
      FROM user_follows
      WHERE follower_id = ${fromUserId}::uuid

      UNION ALL

      SELECT
        f.followee_id,
        bfs.path || f.followee_id::uuid,
        bfs.depth + 1
      FROM bfs
      JOIN user_follows f ON f.follower_id = bfs.to_node
      WHERE f.followee_id <> ALL(bfs.path) AND bfs.depth < ${maxHops}
    )
    SELECT path FROM bfs WHERE to_node = ${toUserId}::uuid
    ORDER BY depth LIMIT 1
  `;

  return rows[0]?.path ?? null;
}

export async function wouldCreateCycle(
  taskId: string,
  dependsOnId: string
): Promise<boolean> {
  const rows = await prisma.$queryRaw<Array<{ would_create_cycle: boolean }>>`
    WITH RECURSIVE reachable AS (
      SELECT depends_on_id AS node, ARRAY[task_id::uuid] AS visited
      FROM task_dependencies WHERE task_id = ${dependsOnId}::uuid

      UNION ALL

      SELECT td.depends_on_id, r.visited || td.task_id::uuid
      FROM task_dependencies td
      JOIN reachable r ON td.task_id = r.node
      WHERE td.depends_on_id <> ALL(r.visited)
    )
    SELECT EXISTS (SELECT 1 FROM reachable WHERE node = ${taskId}::uuid) AS would_create_cycle
  `;

  return rows[0]?.would_create_cycle ?? false;
}

Performance Patterns

-- Always index both directions of an edge table
CREATE INDEX idx_follows_from ON user_follows(follower_id);
CREATE INDEX idx_follows_to   ON user_follows(followee_id);

-- For weighted shortest path on large graphs, use materialized reach tables
CREATE MATERIALIZED VIEW user_2nd_degree AS
SELECT DISTINCT f1.follower_id AS user_id, f2.followee_id AS connected_to
FROM user_follows f1
JOIN user_follows f2 ON f1.followee_id = f2.follower_id
WHERE f1.follower_id <> f2.followee_id;

CREATE INDEX idx_2nd_degree ON user_2nd_degree(user_id);

-- Refresh when follow graph changes significantly
REFRESH MATERIALIZED VIEW CONCURRENTLY user_2nd_degree;

When to move to a graph database:

• Graph has >10M edges and you need sub-100ms multi-hop traversal
• Complex path algorithms (all shortest paths, betweenness centrality)
• You're querying graph structure itself, not just node properties

PostgreSQL handles most social graph, org chart, and permission inheritance needs up to tens of millions of nodes efficiently.

Cost and Timeline Estimates

See Also

• PostgreSQL CTEs and Recursive Queries
• PostgreSQL Row-Level Security for Multi-Tenancy
• SaaS Role-Based Access Control
• PostgreSQL Materialized Views
• PostgreSQL Full-Text Search

---

Working With Viprasol

Graph queries in PostgreSQL unlock powerful features — permission inheritance, social graphs, recommendation systems — without adding database complexity. Our team implements recursive CTE patterns with correct cycle guards, proper indexing strategies, and materialized view caching for large graphs.

What we deliver:

• Adjacency list schema design for your domain
• Recursive CTE queries: ancestors, descendants, BFS, shortest path
• Cycle detection for dependency graphs
• Materialized views for pre-computed second-degree connections
• TypeScript query wrappers with Prisma raw queries

Talk to our team about your graph data requirements →

Or explore our cloud and database services.