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

[FLEB]

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?

[Atli]

Hi.

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):

function ScanDirectory($dirID, $depth=0, $maxdepth=3) 
{
  if($depth == $maxdepth) return;
 
  $sql = "SELECT DirID FROM DirTable WHERE ParentID = $dirID";
  $result = mysqli_query($sql);
 
  while($row = mysqli_fetch_assoc($result)) {
    for($i = 0; $i < $depth; $i++) echo " ";
    echo $row['DirID'];
 
    ScanDirectory($row['DirID'], $depth + 1);
  }
}
 

Which could result in something like

1
 4
 5
  10
2
 6
  8
 7
  11
3
 9