I am sure most people have heard of the limited degrees of separation one has to become connected to another person. This is much like the myspace "in your extended network" idea, though I would like my implementation to not be broken.

If person A exists in mysql, as well as persons B through Z, and some are related or known to each other, they have a relationship. Very much a family tree. While I can see how one wold start at person A, and look for the relationship to another person, thereby drilling down to other known links...

I would like to take it one step further. I think celebrities are the best example, so I would be able to enter in myself, and ask the question: "show me a tree of how I am closest to x celebrity".

Since this is not a real project, and just a hypothetical question, assume that the links are known to be valid, and there is some proven way to key one person to another that is accurate. For example, in this case, we would use an honor system where Person A logs in, and selects all the other persons that they know.

What would be the query to find out all the relationships of person A to "x celebrity"? How expensive is this query?

I am looking to build something as a real project that will use this idea as a feature, albeit in a different way, but the end result will be the same. I get the feeling this is one, that if it is a used and popular service, the database design before it is made will be highly important.

I smell a bit more recursion in this idea that I am used to, and also feel that doing most of the work in the DB layer, and not in the application layer, is going to give me the best performance.

Does anyone have suggestions, or perhaps examples of this in working use? Maybe there is a known algo of function that gets close to this already.

Thank you