472,126 Members | 1,544 Online
Bytes | Software Development & Data Engineering Community
Post +

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 472,126 software developers and data experts.

Representing or determining "friend of a friend of a friend" relationships

I'm working on a PHP/MySQL site with social networking and "message blast" functionality, and I'm not sure what the best method to represent multiple levels of interpersonal relationships in the database would be.

What I'd like to happen is this: A user posts a message to their page, with a "blast radius" option. The system then sends the message that many levels outward from the original person: A radius of 1 would go to their friends, a radius of 2 would go to their friends' friends, 3 goes to grand-friends, etc. I'm figuring that 3 levels would be the reasonable cut-off point-- I'm figuring that anything beyond that would involve sending the thing to the entire Internet.

(The "sending" isn't actually a duplication of the message-- merely an association of the message with the user that prompts it to be shown on the user's page.)

Now, I'm pretty green at database theory-- I'm more of a front-end and design guy-- so the only two options that come to my mind involve either a very large database or an extended hit on the database.

The first option would be to store every interpersonal relationship up to three levels deep in a table: The person's ID, The relation's ID, and the distance between the two (all integer identifiers). This would allow faster searching, since the distances are pre-calculated, and it's just a matter of getting anything relating to that particular person with a distance less than the blast radius.

The second option would be to only store immediate (distance=1) relationships, and make multiple queries, iterating through each friends' relationships, and each friends'-friends' relationships. This just sounds like a great way to choke a server, especially if it's being done often.

It sounds like the sort of problem that has been run into before, but I'm not sure what sort of terminology to search for-- is there a common solution to this problem?
Aug 24 '08 #1
1 2202
5,058 Expert 4TB

This sounds like a basic tree structure to me.
Like, say, if you had to expand a tree view in a directory browser, expanding from a give folder everything nested three directories down.

The basic thing is to create a recursive function or a nicely designed loop that iterates through the tree structure.

Like, say (in a PHP script):
Expand|Select|Wrap|Line Numbers
  1. function ScanDirectory($dirID, $depth=0, $maxdepth=3) 
  2. {
  3.   if($depth == $maxdepth) return;
  5.   $sql = "SELECT DirID FROM DirTable WHERE ParentID = $dirID";
  6.   $result = mysqli_query($sql);
  8.   while($row = mysqli_fetch_assoc($result)) {
  9.     for($i = 0; $i < $depth; $i++) echo " ";
  10.     echo $row['DirID'];
  12.     ScanDirectory($row['DirID'], $depth + 1);
  13.   }
  14. }
Which could result in something like
Expand|Select|Wrap|Line Numbers
  1. 1
  2.  4
  3.  5
  4.   10
  5. 2
  6.  6
  7.   8
  8.  7
  9.   11
  10. 3
  11.  9
Aug 25 '08 #2

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

3 posts views Thread by Erik T. Nomad | last post: by
reply views Thread by zealotcat | last post: by
4 posts views Thread by Yarco | last post: by
reply views Thread by leo001 | last post: by

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.