Understanding the Problem

This is a classic graph traversal problem applied to a social network of actors. We need to design a schema that stores actor relationships, then figure out how to query the shortest path between any two actors. The key insight is that "friendship degrees" maps directly to shortest-path distance in an undirected graph, and our schema and query strategy need to support that efficiently.

Clarifying the Use Case

Before touching any table definitions, let's nail down the access patterns. A natural first question is: what counts as a "friendship" here? In actor networks, this often means co-starring in a film (like the Six Degrees of Kevin Bacon problem), but it could also mean an explicit social graph where actors "follow" or "friend" each other.

Let's assume the co-starring model, since it's richer and more interesting to model. That gives us two distinct concerns:

The base data: which actors appeared in which films together
The derived graph: the implicit friendship edges we compute from that co-appearance data

Our queries will mostly look like: "Given actor A and actor B, what is the minimum number of hops through the friendship graph to connect them?"

Entity Identification

Let's identify the core entities:

Actors: the nodes in our graph
Films: the vehicle through which friendships form
Cast memberships: the many-to-many relationship linking actors to films
Friendships (edges): derived or explicit connections between actors

This gives us a clean normalized starting point. Actors and films are distinct entity types with their own attributes, and the relationship between them is a bridge table.

Base Schema Design

Let's start with the core tables:

CREATE TABLE actors (
  actor_id    BIGINT PRIMARY KEY,
  full_name   VARCHAR(255) NOT NULL,
  birth_date  DATE,
  nationality VARCHAR(100)
);

CREATE TABLE films (
  film_id      BIGINT PRIMARY KEY,
  title        VARCHAR(500) NOT NULL,
  release_year SMALLINT,
  genre        VARCHAR(100)
);

CREATE TABLE cast_memberships (
  actor_id  BIGINT REFERENCES actors(actor_id),
  film_id   BIGINT REFERENCES films(film_id),
  role_name VARCHAR(255),
  PRIMARY KEY (actor_id, film_id)
);

The cast_memberships table is the many-to-many bridge. From this, we can derive friendship edges: two actors are friends (degree 1) if they share at least one row with the same film_id.

Modeling the Friendship Graph

We have a choice here. We could always compute friendships on the fly by joining cast_memberships to itself. But for a large network, that self-join gets expensive fast. The pragmatic approach is to materialize the friendship edges into a dedicated table:

CREATE TABLE actor_friendships (
  actor_id_1  BIGINT REFERENCES actors(actor_id),
  actor_id_2  BIGINT REFERENCES actors(actor_id),
  film_id     BIGINT REFERENCES films(film_id),
  PRIMARY KEY (actor_id_1, actor_id_2, film_id),
  CHECK (actor_id_1 < actor_id_2)  -- enforce canonical ordering, no duplicate edges
);

CREATE INDEX idx_friendships_actor1 ON actor_friendships(actor_id_1);
CREATE INDEX idx_friendships_actor2 ON actor_friendships(actor_id_2);

A few design decisions worth calling out here:

The CHECK (actor_id_1 < actor_id_2) constraint enforces that we store each undirected edge only once, preventing both (A, B) and (B, A) from existing simultaneously. This halves storage and simplifies traversal logic.
We keep film_id in the primary key because two actors may have worked together on multiple films. This lets us trace the specific film that established the connection, which is useful for explaining degree paths.
Both actor columns get individual indexes so lookups in either direction are fast. Since the graph is undirected, any traversal algorithm needs to find all neighbors of a given actor regardless of which side of the edge they fall on.

To populate this table, we run a self-join on cast_memberships:

INSERT INTO actor_friendships (actor_id_1, actor_id_2, film_id)
SELECT
  LEAST(a.actor_id, b.actor_id)    AS actor_id_1,
  GREATEST(a.actor_id, b.actor_id) AS actor_id_2,
  a.film_id
FROM cast_memberships a
JOIN cast_memberships b
  ON a.film_id = b.film_id
 AND a.actor_id != b.actor_id
ON CONFLICT DO NOTHING;

Computing the Degree of Separation

Now for the core algorithm. "Degrees of separation" is shortest-path length in an unweighted undirected graph. The right tool here is Breadth-First Search (BFS). BFS naturally finds the shortest path because it expands outward layer by layer, and the first time it reaches the target, it has found the minimum number of hops.

Conceptually, BFS from actor A works like this:

Start with a frontier set containing just actor A, at distance 0.
Expand the frontier: find all neighbors of everyone in the current frontier who haven't been visited yet. These are at distance 1.
Repeat, incrementing distance, until we find actor B or exhaust the graph.

In pseudocode:

from collections import deque

def degrees_of_separation(start_id, end_id, get_neighbors):
    if start_id == end_id:
        return 0

    visited = {start_id}
    queue = deque([(start_id, 0)])

    while queue:
        current_id, distance = queue.popleft()

        for neighbor_id in get_neighbors(current_id):
            if neighbor_id == end_id:
                return distance + 1
            if neighbor_id not in visited:
                visited.add(neighbor_id)
                queue.append((neighbor_id, distance + 1))

    return -1  # no connection found

The get_neighbors function queries our actor_friendships table for all actors connected to a given ID, handling both edge directions:

SELECT actor_id_2 AS neighbor_id FROM actor_friendships WHERE actor_id_1 = :actor_id
UNION
SELECT actor_id_1 AS neighbor_id FROM actor_friendships WHERE actor_id_2 = :actor_id;

In SQL-native environments that support recursive CTEs (like PostgreSQL), we can express this BFS directly:

WITH RECURSIVE bfs AS (
  -- base case: start node at distance 0
  SELECT :start_actor_id AS actor_id, 0 AS degree, ARRAY[:start_actor_id] AS path
  UNION ALL
  -- recursive case: expand frontier
  SELECT
    CASE WHEN f.actor_id_1 = bfs.actor_id THEN f.actor_id_2
         ELSE f.actor_id_1 END,
    bfs.degree + 1,
    bfs.path || CASE WHEN f.actor_id_1 = bfs.actor_id THEN f.actor_id_2
                     ELSE f.actor_id_1 END
  FROM bfs
  JOIN actor_friendships f
    ON f.actor_id_1 = bfs.actor_id OR f.actor_id_2 = bfs.actor_id
  WHERE NOT (
    CASE WHEN f.actor_id_1 = bfs.actor_id THEN f.actor_id_2
         ELSE f.actor_id_1 END = ANY(bfs.path)  -- avoid revisiting nodes
  )
)
SELECT degree, path
FROM bfs
WHERE actor_id = :end_actor_id
ORDER BY degree
LIMIT 1;

The path array serves as our visited set in the recursive CTE approach. This is elegant but can get expensive for deep searches since databases don't optimize graph traversal the way a custom BFS implementation in application code does.

Optimization: Bidirectional BFS

For large networks, a major optimization is bidirectional BFS: run BFS simultaneously from both the source and the target, and stop when the two frontiers meet. The intuition is that if each actor has an average of $k$ neighbors, a one-directional BFS at depth $d$ explores roughly $k^d$ nodes. Bidirectional BFS explores about $2 \cdot k^{d/2}$ nodes instead, which is dramatically smaller for any meaningful $k$ and $d$.

For example, if $k = 50$ and the true distance $d = 6$:

One-directional: $50^6 = 15{,}625{,}000{,}000$ nodes in the worst case
Bidirectional: $2 \cdot 50^3 = 250{,}000$ nodes in the worst case

This is why bidirectional BFS is the standard approach for degree-of-separation queries in production social graphs.

Precomputation and Caching Tradeoffs

For frequent queries between popular actors, we might consider precomputing and caching degree distances. One option is a degree_cache table:

CREATE TABLE degree_cache (
  actor_id_1 BIGINT,
  actor_id_2 BIGINT,
  degree     SMALLINT NOT NULL,
  computed_at TIMESTAMP DEFAULT NOW(),
  PRIMARY KEY (actor_id_1, actor_id_2),
  CHECK (actor_id_1 < actor_id_2)
);

The tradeoff is significant though. A full precomputation of all pairs is $O(N^2)$ in storage, which is completely infeasible for a network of even 100,000 actors (that's 10 billion rows). So caching only makes sense for hot pairs (frequently queried actor combinations) or for a landmark-based approximation approach, where we precompute distances from a small set of "hub" actors and use those as reference points to estimate distances between arbitrary pairs.

Putting It All Together

The final schema has four key components:

actors: the node registry
films: the context that generates edges
cast_memberships: the raw co-appearance data
actor_friendships: the materialized, indexed edge list for graph traversal

The computation layer uses BFS (or bidirectional BFS for scale) over the actor_friendships edge table. The core tradeoff we face throughout is between query-time computation and pre-materialization: materializing edges trades write overhead and storage for dramatically faster traversal, and caching computed degrees trades staleness risk for even faster reads on hot pairs. For most real-world actor networks in the millions-of-nodes range, the right answer is to materialize the edge list and run bidirectional BFS at query time, with selective caching layered on top for the most popular queries.

1921. Actor Friendship Degrees

Similar Questions