I am always thinking one question. on those SNS sites like Facebook, how are the relationships among friends stored in database. there may be millions of users registerred on the site and each user may have thousands of friends. if the relationship is considerred as a entity, a huge number of instances will be stored in the database. so I am thinking if there may be a way to represent the friendship and also less store spaces are needed.
does anyone have an idea about it

Users(user_id, name, email, etc)
Friends(user_id, friends_user_id, how_do_you_know_eachother, etc)

it makes sense. anyway I'd like to suppose a scenario. A and B are friends. thus there is a record (A, B, ...) in the table Friends which represents A has a friend B, but how about the other side B has a friend A. should I add another record like (B,A,..) to the table. if so, I think the data is duplicate

You could easily have 2 indexes on the same table

Code:

create clustered index my_main_idx on Friends ( user_id, friends_user_id )
create index my_main_idx on Friends ( friends_user_id, user_id )

Which means you wouldn't have to store the data twice but it does mean you'd have to do 2 searches of the table to get all the friends of A. The biggest problem though is that friendships aren't necessarily a two way thing: say A has declared 2 friends B & C. Then D comes along and declares A as his friend. A will suddenly now find he has 3 friends B,C & D even though he hasn't declared D as his friend. A will probably also find he won't be able to delete D from his list of friends either.

Just my 2c.

Why do you have to do two searches?

All friends of A
There's undoubtebly betteer ways, but i just knocked this up quickly to illustrate.

the only effective way I can see of identifying freindshops is to have an intersection table with both FKS to person.

the problem is how people perceive such friendships

A may think they are frends with B, but B may think they are acquaintences, or colleagues or similar. ie its possible that the realtionship type may not be the same for two people.

eg BillyNoMates is desparate to be friends with anybody
but only one or two real poeple are freinds with BillyNoMates, and most of those are probably forced to becuase they are family or employee

I wasn't refering to the number of different select statements but to how many searches of the indexes the database optimiser would need to do to get your complete list of friends. While it's easy to put these queries into one query that certainly doesn't make it any faster.

Also, was that the simplest search you could come up with for that query??? it looks a triumph of NZDF coding

you're not an active facebook user, are you

I suppose when we start to draw Venn diagrams of our friends just to find out which are the real ones then we have to realise we've hit rock bottom

I don't think so.

Here's another thought:
What's with friend-requests?

For example:
A requests to be friends with B, but needs to wait until B approves.
You want to record this status as a "possible (mutual) friendship" and then convert it into a "mutual" friendship when approved.

My first thought would be to simply add another column to the friends table as proposed above, like
Friends(user_id, friends_user_id, how_do_you_know_eachother, status),
where "status" could have values like "requested" and "approved".

Hm...

Possibly my favorite thread title ever.

if B refuses the request from A, should the record be removed then?
I found Facebook's database schema from the Internet, and there is a table named FriendRelation. property "AreFriends" should identify the relationship between two people and I guess its type is boolean

that's pretty cool

do you remember or did you save the url?

check here: Facebook database schema on Flickr - Photo Sharing!

thanks, i bookmarked the blog entry
Facebook Object-Oriented Diagram