Degree of Separation Calculation

MySQL & MariaDB Other MySQL® Questions
1

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?

2

If something is not done well in the database may be you do not have to do it in the database ?

You’re really dealing with graph here which databases do not really do well.

If you expect large volume I would implement separate daemon which holds all graph in memory and is able to perform graph operations as you need them

(find shortest path between two elements, find how many people do you have in your network etc)

On medium sizes singe box should be enough to give you decent response time. For huge sizes you might need more than that.

3

So the daemon would generated all of the paths and hold them all in memory, or would it just hold all of the data in memory, and do the path calculations on the fly?

Where can I find such a daemon?

4

Demon should hold the graph. All paths become very expensive for large data sets.

You would need to write such daemon )