Florian Florian - 5 months ago 22
MySQL Question

Table with 3 levels of degree of separation

I'm looking for a query to create a table in MySQL with the degree of seperation between two users. I already found Degrees of Separation Query.But that will, if i understand correctly, result in a recommended friendlist with mutual friends. What i'm looking for is slightly different.

I have a table with "friends" between users (contains no duplicate relations like 1 to 2 & 2 to 1).


friends
(
id
,
initiator_user_id
,
friend_user_id
,
is_confirmed
)


What i am trying to create is a table with all relations between friends, friends of friends and FoFoF. like this:


relation_degrees
(
id
,
first_user_id
,
second_user_id
,
relation_degree
)


so the relation_degree column only contains the value 1 (friends), 2 (FoF) and 3 (FoFoF).

I was able to do it in Excel, but there my friends where stored in a matrix, which make calculations IMO a little bit easier. I hope somebody will be able to give me a hint to do the same in MySQL.

Thanks!!




edit: with the help from Fluffeh i found the following solution to my problem.


  1. i stored the relations in both directions( like 1-2 & 2-1, so without the confirmation column) in table called degree_one

  2. Then i used the query for degree one and two from fluffeh to make table with first & second degree relations. I added a WHERE user <> Friend statement to filter the relations (i guess this is one of the reasons why the query from fluffeh for the third degree relations isn't working correctly)




`Create table degree_two
select
mb.user as User,
mb.friend as Friend,
min(mb.rel) as relation_degree


from
(
select
1 as rel,
fr1.User,
fr1.Friend
from
degree_one fr1

union all

select
2 as rel,
fr2.User,
fr3.Friend
from
degree_one fr2
left outer join degree_one fr3
on fr2.Friend=fr3.User


) mb

Where user <> friend



group by
mb.User,
mb.Friend




  1. Then i used this table to do almost the same query. the select statement is on the degree_two table but the outer join is still from the degree_one table.




Create table degree_three
select
mb.user as User,
mb.friend as Friend,
min(mb.relation_degree) as relation_degree
from
(
select
fr1.relation_degree,
fr1.User,
fr1.Friend
from
degree_two fr1


union all

select
3 as rel,
fr2.User,
fr3.Friend
from
degree_two fr2
left outer join degree_one fr3
on fr2.Friend=fr3.User


) mb

Where `user` <> `friend`

group by
mb.User,
mb.Friend



It is kind of a work around but it gives me the desired output. I'm still wondering why the query from fluffeh doesn't work correctly, because i really want a single query as solution. i will continue fooling around with the query... I hope that somebody can help me merging these query into one.

Answer

This query gave me the desired solution result:

Create table degree_two
select
    mb.user as User,
    mb.friend as Friend,
    min(mb.rel)  as relation_degree
from
    (
           select
            1 as rel,
            fr1.User,
            fr1.Friend
        from
            degree_one fr1

            union all

        select
            2 as rel,
            fr2.User,
            fr3.Friend
        from
            degree_one fr2
                left outer join degree_one fr3
                    on fr2.Friend=fr3.User
                    where fr2.user <> fr3.friend

         union all       

         select 
            3 as rel, 
            fr4.user, 
            fr6.Friend
        from 
           (degree_one fr4 
                left outer join  degree_one fr5 
                    on fr4.friend=fr5.user
                    and fr4.user <> fr5.friend

                    left outer join  degree_one fr6
                    on fr5.friend = fr6.user
                   and fr5.user <> fr6.friend)
           where fr6.friend  IS NOT NULL           


                  ) mb

group by
    mb.User,
    mb.Friend

Thanks Fluffeh for your help!