Warp wrote:

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

Or, in a similar problem, if you have a table telling you parent/child 
relationships, can you find all recorded descendants of a specified person?

As far as I can tell, you can construct an SQL statement that will find 
all people X generations below a given person, but you cannot write a 
statement that will search to an unbounded depth. The search is 
recursive, and SQL doesn't seem to be able to do that. Each recursion 
requires a sub-select, so the number of sub-selects you type is the 
number of generations it searches.

On the other hand, this kind of problem is trivial (and jaw-droppingly 
inefficient) in Prolog...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message