MySQL Performance: MySQL => Degree of Separation Calculation

Degree of Separation Calculation [message #480]

Tue, 19 December 2006 11:11

Skeptical
Messages: 4
Registered: December 2006

Junior Member

I'm looking to do permission calculation based on degrees of separation. This would include things like granting permissions based on if the viewing user is your friend, your friend's friend, or your friend's friend's friend.

A friend would be 1 degree away.
A friend's friend would be 2 degrees away.
A friend's friend's friend would be 3 degrees away.

In order to calculate the degree of separation user B is away from user A, the most basic logic would mean the traversal of all of A's friends, and their friends, and so on, until the shortest link is found that connects A and B.

However, this is very database consuming, as each degree of separation can result in an exponential increase in the amount of queries.

A shorter way would be to store on a cache table all second-degree level friendships for all users. Then another table for all third-degree friendships. However, this will obviously lead to a HUGE database, and I'm not sure if this is the best way to go about it. Every time a friendship is added/editted/removed, it could mean the updating of thousands+ of records in the cache table.

Is there a better way to go about doing this?

[Updated on: Tue, 19 December 2006 11:14]

Report message to a moderator