another SQL question

[TechBoyJK]

I need to build a query that will determine if a user is a 'friend' of a friend.

Basically, a query to determine the relationship between two accounts.

The friend's list table is designed as followed

id (int-pk)
member_a
member_b

*member_b is the person who requested the friendship
*member_a is the person who accepted the friendship

I think the quick and dirty way to do it would be to fetch a user's entire friend list, and loop through it seeing if there are any matches. However, this would require potentially thousands of small queries and I'd like to avoid that. I have that working, and the code is below. I'm hoping to find out if there is a way to do this all within a single query.

I think the best way to explain how I need this to work is to just post the code I have that gets the job done. In the example below, I use a situation where two accounts are not 'friends' but they share a friend so they would considered 'friends of friends'.

<cfset is_friend = 0>
<cfset is_friend_of_friend = 0>

<cfquery name="check_if_friend" datasource="members">

Select list_id

FROM tbl_member_friend_list

Where (member_id_a = #session.myid# and member_id_b = 530) or (member_id_b = #session.myid# and member_id_a = 530)

</cfquery>

<cfif check_if_friend.recordcount gte 1>

<cfset is_friend = 1>

We friends!

</cfif>

<cfif is_friend neq 1>

<cfquery name="get_user_friend_list" datasource="members">

SELECT member_id_b as friend

FROM tbl_member_friend_list

WHERE member_id_a = '530'

UNION ALL

SELECT member_id_a as friend

FROM tbl_member_friend_list

WHERE member_id_b = '530'

</cfquery>

<cfloop query="get_user_friend_list">

<cfquery name="check_if_friend_of_friend" datasource="members">

select list_id

FROM tbl_member_friend_list

where ((member_id_a = #session.myid# and member_id_b = #get_user_friend_list.friend#)
or (member_id_b = #session.myid# and member_id_a = #get_user_friend_list.friend#))

</cfquery>


<cfif check_if_friend_of_friend.recordcount eq 1>
<cfset is_friend_of_friend = 1>
We friends of friends
<cfbreak>
</cfif>

</cfloop>

</cfif>

 

[uclabachelor]

I need to build a query that will determine if a user is a 'friend' of a friend.

Basically, a query to determine the relationship between two accounts.

The friend's list table is designed as followed

id (int-pk)
member_a
member_b

*member_b is the person who requested the friendship
*member_a is the person who accepted the friendship

I think the quick and dirty way to do it would be to fetch a user's entire friend list, and loop through it seeing if there are any matches. However, this would require potentially thousands of small queries and I'd like to avoid that. I have that working, and the code is below. I'm hoping to find out if there is a way to do this all within a single query.

I think the best way to explain how I need this to work is to just post the code I have that gets the job done. In the example below, I use a situation where two accounts are not 'friends' but they share a friend so they would considered 'friends of friends'.

This is not really an sql question as it pertains more to data structure. What you've described there is called a tree. In your case, you would need two trees, one for friends that send requests, and one for friends that accept the request.

Once you've understand the tree data structure, then you'd have to figure how to store the structure of the tree in the database.

Hint: If you store the structure of the tree properly in the database, then writing queries to answer your original question is trivial.

 

[Markbnj]

I think the quick and dirty way to do it would be to fetch a user's entire friend list, and loop through it seeing if there are any matches. However, this would require potentially thousands of small queries and I'd like to avoid that. I have that working, and the code is below. I'm hoping to find out if there is a way to do this all within a single query.

Some thoughts on this. First, I don't really care for asking the database a boolean question (i.e. is A a friend of B?), although I have done it myself a few times. Second, why would it take thousands of small queries to get the friends list? Unless I'm missing something I think you can get the full friends list for a given member with a single call to the DB. Something like two subqueries that join friends to members, and a union.

This is not really an sql question as it pertains more to data structure. What you've described there is called a tree. In your case, you would need two trees, one for friends that send requests, and one for friends that accept the request.

Interesting. I'm struggling to see these relationships as a tree. Seems to me it is a simple many-to-many self-relation of the friends table, implemented with a mapping table in the usual manner.

 

[TechBoyJK]

This is not really an sql question as it pertains more to data structure. What you've described there is called a tree. In your case, you would need two trees, one for friends that send requests, and one for friends that accept the request.

Once you've understand the tree data structure, then you'd have to figure how to store the structure of the tree in the database.

Hint: If you store the structure of the tree properly in the database, then writing queries to answer your original question is trivial.

The table is what it is.

Can you look at my query question?

 

[BoberFett]

select f2.friendid
from members m
join friends f1 on m.memberid = f1.memberid
join friends f2 on f1.friendid = f2.userid

Fix up the logic for your database and you've got an entire list of the friends of friends. If you just want to know if a particular user is a friend, just add WHERE clause and look for the memberid in the f2 table. A result means it's there, a NULL means it's not.

Also, just curious, why have a separate ID for a primary key on the relationship table? Why not use both member IDs as a composite primary key? Assuming you don't want duplicate relationships, using a separate ID as the key you either have to set up a second unique index on the two columns anyway, or you have to enforce integrity in software which almost always makes life difficult in the future.

 

[uclabachelor]

Some thoughts on this. First, I don't really care for asking the database a boolean question (i.e. is A a friend of B?), although I have done it myself a few times. Second, why would it take thousands of small queries to get the friends list? Unless I'm missing something I think you can get the full friends list for a given member with a single call to the DB. Something like two subqueries that join friends to members, and a union.



Interesting. I'm struggling to see these relationships as a tree. Seems to me it is a simple many-to-many self-relation of the friends table, implemented with a mapping table in the usual manner.

It's not a matter of many to many as the original post mentioned "a friend of a friend". That, to me, is a linked list of 3 items. A -> B -> C. Because of that nested nature, you cannot assume that the linked list has a max. of 3 items as it could potentially contain many items. To complicate matters more, A can have multiple links.

The reason why it is troublesome in the database is because a many to many relationship does not support the linked list data structure very well without using nested queries. If A1 links to A100 through A2, A3, A4, etc, how are you going to select it using sql language? One naive approach would be to do something like :

while(friend_id exists) {
friend_id = get_friend_id_from_database(this_id)
friends_array.push(friend_id);
this_id=friend_id;
}

After running that code, you'd have a friends_array containing what you need, but like I mentioned, you could be querying 1000s of times before that while loop finishes. Using nested queries just pushes that while loop into sql.

For small datasets, this wouldn't be an issue but scalability is going to be a problem.

As for the OP's problem, the "table is what it is", so to deal with the issue at hand, you would have to use a nested query to get a "friend of a friend", ie:

SELECT member_a AS id FROM friends_list_table WHERE member_id=my_id UNION ALL SELECT member_b AS id FROM friends_list_table WHERE member_id=my_id

Gets you a list of id's who are your direct friends. Running the same query again, except replacing the WHERE clause with IN() gives you a list of id's containing the 2nd level friends.

You can either run the query as one nested query or two queries consecutively. To speed things up, make sure you have an index covering member_a, member_id and an index covering member_b, member_id.

 

[Markbnj]

It's not a matter of many to many as the original post mentioned "a friend of a friend". That, to me, is a linked list of 3 items. A -> B -> C. Because of that nested nature, you cannot assume that the linked list has a max. of 3 items as it could potentially contain many items. To complicate matters more, A can have multiple links.

Yeah, missed that. I need to stop replying to messages I don't have time to read carefully .

I see your point now about a tree, where (I assume) the first layer is friends, and the second layer is friends of friends. Seems like it's really a graph, although you can snip a portion of it out and look at it as a tree.

 

[TechBoyJK]

Ok thanks guys for the discussion. Just got into the office, going to read over this.

The reason I said 'it is what it is' wasn't to be snotty, I was just in a rush.

I had a discussion about the best way to keep a friends list and this table design was it. Anything else required a 2nd table or something more drastic and I decided against for the same reason mentioned about dropping the id column.. not really necessary.

Yes, I considered removing the 'id' field and just using the two member columns as a hybrid key. I still can because nothing really banks on the id. I just haven't yet because I wanted to research the benefits of having the key because it noted order in which the relationships were created.

 

[TechBoyJK]

Here's the forum thread about the friends list table design

http://forums.anandtech.com/showthread.php?t=2156499

Was planning on just using the a/b column setup, and doing an index on each column.