query to find friends of a friend

sinkorswim · #1 (**permalink**) 04-16-07, 03:28

Hi all

I'm experimenting with writing my own social network script but I'm struggling a bit with one of the queries. I have a users table, and a friendships table containing user_id and friend_id columns which are both foreign keys linking to users.id (sql dump at end of this post).

if x is a friend of y, and the friendship is approved, then y is also a friend of x. I'm using this query to retreive all the friends of x (in this example, x has an id of 99):

Code:

  SELECT 
    CASE 
      WHEN user_id=99 THEN friend_id 
      ELSE user_id 
    END
  AS fid FROM friendships
  WHERE (user_id=99 OR friend_id=99)
  AND approved = 1;

so far so good, but what I'd like to do now is extend the search to find all friends of friends of x, but I'm not making any progress.

can anyone help?
thanks

tyler

sql dump:

Code:

create database if not exists `foaf`;
USE `foaf`;

/*Table structure for table `users` */

DROP TABLE IF EXISTS `users`;

CREATE TABLE `users` (
  `id` int(11) NOT NULL auto_increment,
  `username` varchar(255) default NULL,
  PRIMARY KEY  (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1;

/*Table structure for table `friendships` */

DROP TABLE IF EXISTS `friendships`;

CREATE TABLE `friendships` (
  `id` int(11) NOT NULL auto_increment,
  `user_id` int(11) default NULL,
  `friend_id` int(11) default NULL,
  `approved` tinyint(1) default '0',
  PRIMARY KEY  (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1;

aschk · #2 (**permalink**) 04-16-07, 04:33

For anyone looking to insert some test data in these tables use the following and then change some of the approved statuses.

Code:

/* Insert some users */
INSERT INTO users(username) VALUES('Alfred')
,('Karen'),('Frank'),('Garry'),('John'),('James'),('Philip'),('Inziman'),
('Ross'),('Duncan'),('Neil');

/* Get some friends */
INSERT INTO friendships(user_id,friend_id,approved)
SELECT u1.id,u2.id,0 FROM users u1,users u2 WHERE u1.id <> u2.id;

aschk · #3 (**permalink**) 04-16-07, 04:44

These are the corresponding relationships (approved) I have set up in the database (friendship table) :

Code:

Alfred	Karen
Duncan	John
James	Alfred
James	Frank
James	Neil
James	Philip
Karen	Frank
Neil	Duncan
Neil	Frank
Neil	Karen
Philip	John
Philip	Karen
Ross	Inziman

The query below almost gives the right answer I think. Once you have changed the approved status on some of your friend relationships you need to check through the data to make sure it's giving the correct result. For the below query the user_id = 6 relates to James.

Code:

SELECT 
u1.username as person,
u2.username as friend,
u3.username as friend_of_friend 
FROM users u1
JOIN friendships f1 ON u1.id=f1.user_id
JOIN users u2 ON f1.friend_id=u2.id
JOIN friendships f2 ON u2.id=f2.user_id
JOIN users u3 ON f2.friend_id=u3.id
WHERE f1.approved=1 AND u1.id=6 AND f2.approved=1;

The results given are as follows:

Code:

person	friend	friend_of_friend
James	Alfred	Karen
James	Philip	Karen
James	Neil	Karen
James	Neil	Frank
James	Philip	John
James	Neil	Duncan

I'm sure there is a better answer to this, however i've only spent 15 minutes on it

Edit : As you can see there is a problem there with duplication of data,
i.e.
if James knows Alfred and Alfred knows Karen then James knows Karen,
however, this information is duplicated because if James knows Neil and Neil knows Karen then James knows Karen.
See what I mean?

aschk · #4 (**permalink**) 04-16-07, 05:45

I rewrote it using subselects (please note i'm using user_id=6 in WHERE clause, change this to whatever you're searching for):

Code:

SELECT
(SELECT username FROM users WHERE id=f1.user_id) as person,
(SELECT username FROM users WHERE id=f2.user_id) as friend,
(SELECT username FROM users WHERE id=f2.friend_id) as friend_of_friend
FROM friendships f1 JOIN friendships f2 ON f1.friend_id = f2.user_id
WHERE f1.approved = 1
AND f2.approved = 1
AND f1.user_id=6;

This query gives the same results as the one above.

aschk · #5 (**permalink**) 04-16-07, 05:52

In order to stop a full table scan on the friendships table I put in an unique index on (user_id,friend_id) :

Code:

ALTER TABLE `foaf`.`friendships` DROP INDEX `UNI_USER_FRIEND`,
 ADD UNIQUE INDEX UNI_USER_FRIEND(`user_id`, `friend_id`);

Instead of doing 200+ row scans it's now less than 20 (90%+ performance increase). Although bear in mind this is data dependent. If one person has a lot of friends, who has a lot of friends this amount (row scan number) will get bigger but is still efficiently found.

Internet Services

Web Development

Digital Marketing

Consumer Tech