Many-to-many on same table

Question

Funny that I've never come across this yet!

It never occurred to me that one could have a "many to many" relationship on one table- until I started working on a system where users can "friend" each other (social networking).

A standard lookup table, at least in the way that I'm used to using it, isn't appropriate here. Lets keep it simple:

User table has "id" and "name" column.

User_relationship table has "uid1" and "uid2", representing users that are "friends" or "buds" or "pals" or "whatever else".

It becomes apparent pretty quick what the problem here is- uid1 and uid2 are the same data type from the same column of the same table, meaning that unique keys become flawed.

E.g.: uid1 = 1 uid2 = 2

Is the same as:

uid1 = 2 uid2 = 1

And therefore could return 2 records, or 0 records if the query is performed wrong.

In the spirit of designing a table well, I don't want to have to scan the entire table twice to check for existing values.

Is there some sort of trick for handling this? This is a design question that has never occurred to me, and it irks me because I know that there's some simple trick to make it work.

Before you ask, I haven't tried anything yet, because I already see that my favorite way of relating things (lookup tables) is insufficient for my needs here, and I need some help- I can't find anything on SO or Google :(

Thanks in advance.

Answer 1

If the relationship you're describing is symmetrical, as in "Bob is a friend of Joe" means "Joe is also a friend of Bob", then you can make sure in your code that the smaller of the 2 user IDs goes on the first column, and the larger one goes on the second column. This constraint pretty much ensures that the records in your lookup table will be unique. It also means that when you're performing a lookup, you usually have to search both columns.

For example, if you were trying to get all of Bob's friends, you would have to query for records that have Bob's ID in either column. This leads to a bit more code and possibly an impact on performance.

If the relationship can be asymmetrical, as in "Bob is a friend of Joe" does not necessarily mean "Joe is also a friend of Bob", then you need 2 entries for every pair of users: Bob - Joe and Joe - Bob. This means that your lookup table will contain twice as many entries and also that your site is very stalker-friendly :D Of course, you can still choose to apply this system even though your relationship is symmetrical.

Using this method, if you want to get all of Bob's friends you just have to select the records with Bob's ID in the first column. It is possible that this might mean faster lookups and less code for you to write, but again, it means you're taking up more room in your database.