Bacon Numbers and Transitive Closure

Bacon numbers

Kevin Bacon has Bacon number 0. Any actor who has appeared in a movie with Kevin Bacon has Bacon number 1. For any other actor, their Bacon number is $k+1$ where $k$ is the smallest Bacon number among their co-actors.

More generally, this is the shortest-path distance in a graph where vertices are actors and edges connect actors who have appeared together in a film.

The co-actors view

First, build a relation of pairs of actors who have appeared in the same movie:

CREATE VIEW coactors AS
SELECT DISTINCT p1.person_id AS pid1, p2.person_id AS pid2
FROM plays_role AS p1
JOIN plays_role AS p2 ON p2.movie_id = p1.movie_id;

This relation is:

• Reflexive: every actor co-acts with themselves (they appear in the same movie as themselves). The query above includes this because $p1$ can equal $p2$ when p1.movie_id = p2.movie_id.
• Symmetric: if A co-acts with B, then B co-acts with A (achieved because the join generates both orderings).

Computing Bacon numbers in SQL (without recursion)

Without recursive SQL, we must hard-code each level. For Bacon number 1:

CREATE VIEW bacon_number_1 AS
SELECT DISTINCT pid2 AS pid
FROM coactors
WHERE pid1 = (SELECT person_id FROM people WHERE name = 'Kevin Bacon');

For Bacon number 2, join the level-1 actors with coactors, then exclude those already found:

CREATE VIEW bacon_number_2 AS
SELECT DISTINCT c.pid2 AS pid
FROM bacon_number_1 AS b1
JOIN coactors AS c ON c.pid1 = b1.pid
WHERE c.pid2 NOT IN (SELECT pid FROM bacon_number_1)
  AND c.pid2 <> (SELECT person_id FROM people WHERE name = 'Kevin Bacon');

Each subsequent level follows the same pattern: join the previous level’s actors with coactors, exclude actors already found at earlier levels (to avoid counting longer paths), and exclude Kevin Bacon.

The final view unions all levels:

CREATE VIEW bacon_numbers AS
SELECT pid, 0 AS n FROM people WHERE name = 'Kevin Bacon'
UNION
SELECT pid, 1 AS n FROM bacon_number_1
UNION
SELECT pid, 2 AS n FROM bacon_number_2
...
UNION
SELECT pid, 9 AS n FROM bacon_number_9;

Transitive closure

The transitive closure $R^+$ of a binary relation $R$ is the smallest binary relation such that:

1. $R \subseteq R^+$ (it contains $R$)
2. $R^+$ is transitive: $(x, y) \in R^+ \land (y, z) \in R^+ \implies (x, z) \in R^+$

The transitive closure can be expressed as the union of powers:

$R^+ = \bigcup_{n \in \{1,2,\ldots\}} R^n$

where $R^1 = R$ and $R^{n+1} = R^n \circ R$.

Finiteness and the limitation of RA

Since all our relations are finite, there must exist some $k$ such that:

$R^+ = R \cup R^2 \cup \cdots \cup R^k$

However, $k$ depends on the contents of $R$. The relational algebra cannot express “union up to whatever power is needed” because RA expressions have fixed, finite length. Therefore, transitive closure cannot be computed in the Relational Algebra (equivalently, in SQL without recursion).

Graph model

A directed graph $G = (V, A)$ has vertices $V$ and arcs $A \subseteq V \times V$, where $A$ is a binary relation over $V$.

The $R$-distance (hop count) from $s_0$ to $s'$ is the least $n$ such that:

$(s_0, s') \in R^n$

If no such $n$ exists, the distance is undefined (the vertices are not connected).

Bacon number is the $R$-distance from Kevin Bacon in the co-actor relation.

Summary

• Bacon number is the shortest-path distance in the co-actor graph.
• Without recursion, each Bacon level requires a separate hard-coded view.
• The transitive closure $R^+ = \bigcup_{n} R^n$ is the smallest transitive relation containing $R$.
• $k$ depends on the data; RA cannot express “enough unions,” so transitive closure is inexpressible in RA.
• Directed graphs model binary relations; $R$-distance is the least $n$ with $(s_0, s') \in R^n$.