Channels ▼
RSS

Database

Discovering Relationships in Context

Source Code Accompanies This Article. Download It Now.


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));

Example 1: Typical adjacency list.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video