|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |