Database design: Best table structure for capturing the User/Friend relationship?

UserRelationship
====
RelatingUserID
RelatedUserID
Type[friend, block, etc]

Agree that mutuality doesn't belong as a column; breaks normalization.

To go one record per two users and avoid consuming extra memory that the proposed methods suggest (twice as much as needed, since there are two records for each user), you can do the following:

1. Table structure:

   USER_RELATIONSHIP {
       user_first_id,
       user_second_id,
       type
   
       primary key(user_first_id, user_second_id)
   }
   

2. Ensure: user_first_id < user_second_id

3. The most interesting part - type: for all of the possible states of a relationship, you create the corresponding values. For exmaple:

   pending_first_second
   pending_second_first
   friends
   block_first_second
   block_second_first
   block_both
   

What you have:

1. The user_first_id < user_second_id ensures that there is only one record of a relationship between two given users, since this and primary key constraints won't allow placing it otherwise.
2. By proper switching between the relationship states, you determine how each of two users relate to each other. If there is no relationship between two users, there is no record.

3. To find out the relationship between two users (as well as update), you simply go by a single query:

   select * from USER_RELATIONSHIP where
       user_first_id = user1_id and
       user_second_id = user2_id;
   

   without an or statement that would check this columns vice versa, which is faster.

Example scenario:

1. no record : are not in a relationship

2. pending_first_second : the first made a friend request to the second

3. friends : the second approved the friend request

4. no record : one of the users removed the other from his firends

This solution is efficient in terms of both memory and speed, because you create, store and update only one single record.

I'd do something similar to what you have, but remove the "IsMutual" flag. Simply add a second row with inverse values when it is mutual. It does add rows, but feels a lot cleaner.

I am currently building a social networking site for a client and I expressed things this way

CREATE TABLE [dbo].[PersonFriend] (
    [Id]                          INT            IDENTITY (1, 1) NOT NULL,
    [Timestamp]                   DATETIME       NOT NULL,
    [ChangeUser]                  NVARCHAR (200) NOT NULL,
    [FriendStatusId]              TINYINT        NOT NULL,
    [Person1Id]                   INT            NOT NULL,
    [Person2Id]                   INT            NOT NULL,
    [Person1RequestTimestamp]     DATETIME       NOT NULL,
    [Person2AcknowledgeTimestamp] DATETIME       NULL
);

Each person is stored in the Person table (imagine that). The Person1Id and Person2Id fields are FK to the person table. I keep a status list in the FriendStatus table for covering whether something has been request, accepted, denied, ignored etc. The Timestamp field is standard in my design to indicate record creation (it is a pattern thing that is used in by base persistence class) and its kind of duplicated in this table as the Person1RequestTimestamp contains the same data. I also capture when the Person2 saw the request and made an action (which gets indicated in FriendStatusId) on it and store that in the Person2AcknowledgeTimestamp).

One of the core assumptions of this design can be stated that Person1 requested friendship of Person2 - if that friendship is accepted then the friendship is considered mutual.