1

I want to have a table with columns: id, user_id1, and user_id2.

basically this will resprsent a friend graph with the link representing that user1 is friends with user2 AND vice versa.

my setup gets a single user and then a list of their friends. given that I don't want to have extra entries in my table how shoudl I handle this?

I want to do something like: insert into friendship (user_id1, user_id2) values (<id1>, <id2>) where ...

but I'm not sure how to do conditional logic like that in SQL

2
  • Are you asking how to prevent duplicates or are you asking on how to retrieve all friends for a specific user?
    – user330315
    Nov 12, 2011 at 23:02
  • both. just trying to figure out the best architecture. Nov 12, 2011 at 23:26

4 Answers 4

4

To prevent inserting the "logically" same combination you can create a unique index:

 CREATE UNIQUE INDEX unique_pair 
      ON your_table (least(user_id1, user_id2), greatest(user_id1, user_id2));

This is standard ANSI SQL and should work on most DBMS. If your DBMS does not support least and greatest you can use a CASE statement to achieve the same, just not that compact.

How does it work?

By always putting the lower valuer first and the higher value second in the index, the tuples (2,1) and (1,2) will both be indexed as (1,2) - the UNIQUE does the rest.

6
  • interesting! so what happens if I try to insert a pair such as (13, 10)? would there be some way to catch such an error? also, if I understand correctly, this unique index is acting as a constraint on the insertions into the table? Nov 12, 2011 at 23:36
  • That's an interesting alternative to a CHECK constraint and should even work with MySQL. Nov 12, 2011 at 23:42
  • In this case, adding (13,10) isn't an error. It just adds it and creates an index for it of (10,13). Then if you later try to add (10,13) that will also have an index of (10,13) and, as such, it will be rejected. Nov 13, 2011 at 4:37
  • hmm. I should have mentioned I'm using MySQL. It throws an error #1064 - You have an error in your SQL syntax; check the manual that corresponds to your MySQL server version for the right syntax to use near 'fb_id1, fb_id2), greatest(fb_id1, fb_id2))' at line 1 when I try to use the unique_pair index solution you gave... Nov 23, 2011 at 22:13
  • No, won't work with MySQL. It does not support functional indexes like most other DBMS.
    – user330315
    Nov 23, 2011 at 22:17
3

You could force user_id1 to always be less than user_id2 with a CHECK constraint:

CHECK (user_id1 < user_id2)

Presumably people aren't allowed to be their own friends. And then make sure the IDs are in the right order before you INSERT. When extracting a list of friends, you'd still have to check both columns though:

select user_id2 from friendship where user_id1 = X
union all
select user_id1 from friendship where user_id2 = X

where X is, of course, the person you're interested in. And to see if two people are friends, just arrange their IDs in the right order and SELECT away.

8
  • how would having the lesser value id as user_id1 help? Nov 12, 2011 at 23:17
  • @lollercoaster: That avoids duplicates. Undirected means that (1,2) and (2,1) are the same edge so if you force (using the CHECK) the first node to have a lower ID than the second node, you won't get both (1,2) and (2,1) since (2,1) would violate the check constraint. Nov 12, 2011 at 23:37
  • yes unfortunately CHECKs and CONSTRAINTs don't work with MySQL. they are parsed but ignored on insert/update calls Nov 23, 2011 at 21:33
  • @lollercoaster: Your comment is the first mention of MySQL. You might be able to fake it with a trigger, switch to a better database, or assume that your code doesn't have INSERT or UPDATE bugs and hope for the best. Nov 23, 2011 at 21:55
  • 2
    @lollercoaster: Both a_horse_with_no_name and I lean towards PostgreSQL and that has a much better feature set, PostgreSQL also has recursive CTEs which might be handy for graph and tree work. If you want to stick with MySQL then the "standard" way to raise an exception from a trigger is, AFAIK, to trigger an illegal operation of some kind; something like this might work nicely without too much ugliness: blogs.oracle.com/svetasmirnova/entry/how_to_raise_error_in Nov 23, 2011 at 23:11
2

If it's properly indexed, I see no problem with storing both user1, user2 as well as user2, user1.

If you are sure you only want one row, then I suggest that you always store the lowest ID in user1 (perhaps even put a constraint on that column to enforce it), and you'll have a friend query that looks like this:

SELECT user1 FROM friendship WHERE user2 = $user_id
UNION ALL
SELECT user2 FROM friendship WHERE user1 = $user_id
3
  • It makes your query simpler. Also, if you always store the lowest value in user1, then you can't have duplicates. If user 14 friends user 18, then you store 14,18. But if user 18 friended user 14, then you would also store 14,18. Nov 12, 2011 at 23:29
  • 2
    UNION ALL might be a better call than UNION, less work for the database and duplicates shouldn't occur anyway. Nov 12, 2011 at 23:39
  • Aye, that's why I upvoted your answer over mine. That, and you also provided the actual check constraint. Nov 12, 2011 at 23:46
0
INSERT INTO friendship (user_id1, user_id2) 
SELECT <id1>,<id2> FROM <special table with only one row, contents irrelvant>
WHERE ((<id1>,<id2>) NOT IN
       ((SELECT user_id1, user_id2 FROM friendship)
        UNION 
        (SELECT user_id2, user_id1 FROM friendship)))

To explain this from bottom to top, we're first constructing the table of all pairs in either direction. Then we're finding out whether or not the pair (<id1>, <id2>) is in it. If it is, no tuples are returned by the SELECT query on line 2 and so nothing is inserted. If it is not, then one tuple is returned by the SELECT query (specifically the tuple (<id1>,<id2>)) and it is inserted.

I think that a_horse_with_no_name's answer is probably the best one in this specific case and in most similar cases, but if someone was in some situation where adding such an index either wasn't allowed or would cause problems (for example, if there were a more complex table where only some of the rows had meaningful friendship entries, but you still wanted uniqueness), then this query would do the job.

2
  • i don't understand what the special table with one row is for...? Nov 12, 2011 at 23:25
  • Let's say you're doing a SELECT query where you want just the value 1. If you do SELECT 1 FROM friendship, you'll get a 1 for every row in the friendship table. So, when you're using a SELECT to compute values, you want a table with only one row so that you get at most one copy of the value. Some RBDMS's have a special table for this purpose, but I don't know what RBDMS you're using so I don't know what to call it. But you can create any table with just one row and use that. Nov 13, 2011 at 4:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.