best way to store 1:1 user relationships in relational database

Question

What is the best way to store user relationships, e.g. friendships, that must be bidirectional (you're my friend, thus I'm your friend) in a rel. database, e.g. MYSql?

I can think of two ways:

1. Everytime a user friends another user, I'd add two rows to a database, row A consisting of the user id of the innitiating user followed by the UID of the accepting user in the next column. Row B would be the reverse.
2. You'd only add one row, UID(initiating user) followed by UID(accepting user); and then just search through both columns when trying to figure out whether user 1 is a friend of user 2.

Surely there is something better?

Answer 1

Using double rows, while it creates extra data, will greatly simplify your queries and allow you to index smartly. I also remember seeing info on Twitter's custom MySQL solution wherein they used an additional field (friend #, basically) to do automatic limiting and paging. It seems pretty smooth: http://engineering.twitter.com/2010/05/introducing-flockdb.html

Answer 2

I would have a link table for friends, or whatever, with 2 columns both being PK's, and both being FK's to the User table.

Both columns would be the UID, and you would have two rows per friend relationship (A,B and B,A). As long as both columns are PK's, it should still be in normal format (although others are free to correct me on this)

Its a little more complex of a query, but nothing that can't be abstracted away by a stored procedure or some business logic, and its in Normal Format, which is usually nice to have.

Answer 3

Use a key value store, such as Cassandra for example.