Results 1 to 5 of 5
  1. #1
    Join Date
    Apr 2007
    Posts
    1

    Unanswered: query to find friends of a friend

    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;

  2. #2
    Join Date
    Mar 2007
    Location
    636f6d7075746572
    Posts
    770
    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;

  3. #3
    Join Date
    Mar 2007
    Location
    636f6d7075746572
    Posts
    770
    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?
    Last edited by aschk; 04-16-07 at 05:55.

  4. #4
    Join Date
    Mar 2007
    Location
    636f6d7075746572
    Posts
    770
    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.
    Last edited by aschk; 04-16-07 at 06:53.

  5. #5
    Join Date
    Mar 2007
    Location
    636f6d7075746572
    Posts
    770
    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.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •