How should I design a relationship table for friendship?

Question

If A is a friend of B, then should I store both values AB and BA, or one is enough? What are the advantages and disadvantages of both methods.

Here is my observation:

• If I keep both then I have to update both when receive a request from a friend.
• If I don't keep both, then I found it difficult when having to do multiple JOIN with this table.

Currently, I keep the relationship one way.

So what should I do in this case? Any advice?

Answer 1

I would store AB and BA. A friendship is really a two-way relationship, each entity is linked to another. Even though intuitively we think of the "friendship" as one link between two people, from a relational point of view it is more like "A has a friend B" and "B has a friend A". Two relationships, two records.

Answer 2

If friendship is intended to be symmetrical (i.e. it is not possible for A to be friends with B but not vice-versa) then I would just store the one way relationship with a check constraint ensuring that each relationship can only be represented one way.

Also I would ditch the surrogate id and have a composite PK instead (and possibly a composite unique index also on the reversed columns).

CREATE TABLE Friends
  (
     UserID1 INT NOT NULL REFERENCES Users(UserID),
     UserID2 INT NOT NULL REFERENCES Users(UserID),
     CONSTRAINT CheckOneWay CHECK (UserID1 < UserID2),
     CONSTRAINT PK_Friends_UserID1_UserID2 PRIMARY KEY (UserID1, UserID2),
     CONSTRAINT UQ_Friends_UserID2_UserID1 UNIQUE (UserID2, UserID1)
  ) 

You don't say the queries that this makes difficult but you can always create a View

CREATE VIEW Foo
AS
SELECT UserID1,UserID2 
FROM Friends
UNION ALL
SELECT UserID2,UserID1 
FROM Friends

Answer 3

Assuming a "friendship" is always two-way/mutual, I'd probably handle it something like this.

CREATE TABLE person (
    person_id int IDENTITY(1,1) PRIMARY KEY,
    ...other columns...
)

CREATE TABLE friendship (
    friendship_id int IDENTITY(1,1) PRIMARY KEY,
    ...other columns, if any...
)

CREATE TABLE person_friendship (
    person_id int NOT NULL,
    friendship_id int NOT NULL
    PRIMARY KEY (person_id, friendship_id)
)

The result is that you change it from a many-to-many join from "person" to "person", to a many-to-many join from "person" to "friendship". This will simplify joins and constraints, but has the side effect of allowing more than two people in a single "friendship" (though maybe the additional flexibility would be a potential advantage).

Answer 4

You may need to define indexes around friendships instead of doubling the number of rows:

CREATE TABLE person
(
    person_id INT NOT NULL AUTO_INCREMENT,
    ...
    PRIMARY KEY (person_id)
);
CREATE TABLE friendship
(
    friend_of INT NOT NULL,
    friend_to INT NOT NULL,
    PRIMARY KEY (friend_of,friend_to),
    UNIQUE KEY friend_to (friend_to,friend_of)
);

This way, you double the storage for indexes but not for the table data. As a result, this should be a 25% savings on diskspace. The MySQL Query Optimizer will choose perform index range scans only, which is why the concept of covering indexes works well here.

Here are some nice links on Covering Indexes:

• http://peter-zaitsev.livejournal.com/6949.html
• http://www.mysqlperformanceblog.com/2006/11/23/covering-index-and-prefix-indexes/
• http://ronaldbradford.com/blog/tag/covering-index/

CAVEAT

If friendship is not mutual, you have the basis for another type of relationship : FOLLOWER

If friend_to is not a friend of friend_of, you can simply leave that relationship out of the table.

If you want to define relationships for all types, whether they are mutual or not, you could probably use the following table layout:

CREATE TABLE person
(
    person_id INT NOT NULL AUTO_INCREMENT,
    ...
    PRIMARY KEY (person_id)
);
CREATE TABLE relationship
(
    rel_id INT NOT NULL AUTO_INCREMENT,
    person_id1 INT NOT NULL,
    person_id2 INT NOT NULL,
    reltype_id TINYINT,
    PRIMARY KEY (rel_id),
    UNIQUE KEY outer_affinity (reltype_id,person_id1,person_id2),
    UNIQUE KEY inner_affinity (reltype_id,person_id2,person_id1),
    KEY has_relationship_to (person1_id,reltype_id),
    KEY has_relationship_by (person2_id,reltype_id)
);
CREATE TABLE relation
(
    reltype_id TINYINT NOT NULL AUTO_INCREMENT,
    rel_name VARCHAR(20),
    PRIMARY KEY (reltype_id),
    UNIQUE KEY (rel_name)
);
INSERT INTO relation (relation_name) VALUES
('friend'),('follower'),('foe'),
('forgotabout'),('forsaken'),('fixed');

From the relation table, you could arrange the relationships to include the following:

• Friends should be mutual
• Foes could be mutual or not
• Followers could be mutual or not
• The other relationships would be subject to interpretation (by the forgotten or forsaken or the recipient of revenge (fixed))
• Possibie relationships can be further extended

This should be more robust for all relationships, whether the relationship is mutual or not.

Answer 5

If you can control within the application that id of A is always lower than id of B ( pre order the A,B elements ids ) you can leverage of asking without an OR ( select where id_A = a AND id_B = b, instead of asking (id_A = a AND id_B = b) OR (id_A = b AND id_B = a) ), and also maintain half of the records you'll need with the other's approximations. Then you should use another field to maintain the state of the relationship ( are-friends, a-solicited-to-b, b-solicited-to-a, exfriends-a, exfriends-b ), and you're done.

This is the way I've managed my friendship system, and this simplifies the system and uses half the rows you'll need with other systems, only saying A is equals to the lower id value in code.