Discovering Relationships in Context

Six Degrees of Kevin Bacon

For example, "Six Degrees of Kevin Bacon" is a popular game that started at Albright College (www.albright.edu). The idea is that Kevin Bacon can be linked with any other actor in the world via movie appearances. Jack Nicholson was in A Few Good Men with Kevin Bacon. Michelle Pfeiffer was in Wolf with Jack Nicholson. Tab Hunter was in Grease 2 with Michelle Pfeiffer. The number of links is your "Bacon Number," which cannot be greater than six—Bacon (Nicholson) = 1, Bacon (Pfeiffer) = 2, and Bacon (Hunter) = 3.

In fact, there is a web site at the University of Virginia (www.cs.virginia.edu/oracle/) that does nothing but maintain an in-memory graph database for just this single problem. It downloads current data from the Internet Movie Database (www.imdb.com), which contains more than 800,000 actors, 375,000 movies, and 70,000 aliases. It's a cute piece of work for a single—and silly—purpose, but it is not a general tool.

The most common—and best—way to model a graph in SQL is an adjacency-list model. Example 1 is a typical adjacency-list model of a general graph with one kind of edge that is understood from context. Structure goes in one table and the nodes in a separate table, because they are separate kinds of things (entities and relationships).

CREATE TABLE Actors -- nodes
(actor_id INTEGER NOT NULL PRIMARY KEY
 actor_name CHAR(25) NOT NULL);

CREATE TABLE MovieCasts -- edges
(relationship_name  VARCHAR(50) NOT NULL, 
 begin_actor_id INTEGER NOT NULL
         REFERENCES Actors (actor_id)
         ON UPDATE CASCADE
         ON DELETE CASCADE, 
 end_actor_id INTEGER NOT NULL 
          REFERENCES Actors (actor_id)
         ON UPDATE CASCADE
         ON DELETE CASCADE, 
 PRIMARY KEY (relationship_name, begin_actor_id, end_actor_id), 
 CHECK (begin_actor_id <> end_actor_id));