Le 24/06/2010 21:48, Warp nous fit lire :
>   Completely unrelated to what you wrote, but it reminded me of something
> I wondered some time ago:
> 
>   Assume you have a table with movie names and another with actor names,
> and a relationship between the two telling which actors have acted in which
> movies.
> 
>   Problem: Can you write an SQL statement which solves the "six degrees of
> Kevin Bacon" relationship between any two given actors?
> 
>   In other words, you give it two actor names and it tells you how many
> steps apart they are from each other, via common movies they have acted in.
> (Ie. if they have acted in the same movie, their degree of separation is 1,
> if they haven't acted in the same movie but have acted with the same third
> person, their degree of separation is 2, and so on.)
> 
That's a graph exploration.

With 2 actor's names and wanting the minimal distance between them is
best solved with dijkstra SPF, not SQL. (double the distance, it's one
actor-one movie-one actor... path)

SQL would be better at generating view of increasing distance, sort of a
breadth first flooding.
First view would be the set of actors that have a distance of 1.

pseudo SQL:
Select distinct(actor.*),1 as hop from actor, relationship as a,
relationship as b where actor.id = a.actor_id and b.actor_id =
id_of_Kevin_Bacon and b.film_id = a.film_id order by actor.id ;

You can continue with a recursive:

Select distinct(actor.*),2 as hop from actor, relatiionship as a,
relationship as b where actor.id = a.actor_id and b.actor_id in (select
x.actor_id from relationship as x, relationship as y where y.actor_id =
id_of_Kevin_Bacon and x.film_id = y.film_id) and b.film_id = y.film_id ;

If you want to avoid seeing people at multiple ranges, an additional
filter is needed ( and a.actor_id not in (select .... ))

you can continue like that, using union select to make a single big huge
query. (but it's going deeper & deeper, better done with a graphical
editor of query)

(So far, it does not give you the movie/actor path... it might just be a
concat() construct from the movie table with the previous level query)

Even with a starting Actor, it would be simpler to use the database as
the source of vertex & edge and use a classical dijkstra SPF to generate
a full tree.

If you allow populating intermediate tables (with insert statements),
you can have a representation of the SPF tree for any starting point.
(but replacing Kevin Bacon with Michael Jackson would force to drop the
tables and restart the filling): you fill the level 1 table, then the
level 2 table,... and so on, each filling being restricted to not add an
entry already in a lower table.

Post a reply to this message