0

So there is a friendship_request table:

+--------+----------+
| sender | receiver |
+--------+----------+
|      1 |        2 |
|      2 |        1 |
+--------+----------+

Two users are friends if both have sent each other a request.

I'm using PHP's array_intersect with arrays containing all the friends of each user to determine if they are connected through friends of friends.

i.e. 

1 <--> 2 <--> 3

What is the most efficient way to find if two users have friends that have friends that are friends with each other. i.e. 

+--------+----------+
| sender | receiver |
+--------+----------+
|      1 |        2 |
|      2 |        1 |
|      2 |        3 |
|      3 |        2 |
|      3 |        4 |
|      4 |        3 |
+--------+----------+


1 <--> 2 <--> 3 <--> 4

User 1 should know of his relationship with User 4.

PS: It's ok with PHP/pseudocode or MySQL

Edit: I do not want to create another table or views. I want to get the best solution using the resources described above.

Marius S
  • 267
  • 3
  • 21
  • Possible duplicate of [What are the options for storing hierarchical data in a relational database?](https://stackoverflow.com/questions/4048151/what-are-the-options-for-storing-hierarchical-data-in-a-relational-database) – philipxy Jun 11 '17 at 00:53
  • 2
    This is a faq. Google re relational/SQL data/tables/queries for hierarchies/trees. Please always before you ask google stackoverflow for many concise clear statements of your question. (Make one your title.) PS "Efficient" means nothing. Or put another way, you used it, what does do you mean by it, *exactly*, without us expecting to tell you. – philipxy Jun 11 '17 at 00:55
  • I do not want a table with nodes... – Marius S Jun 11 '17 at 01:52
  • "Node" is a general term for a thing that has a (possibly "directed") "edge" to another thing/node. Ie they (the nodes) are related/associated in a certain way (the edge). Like a friend (node) has-befriended (directed edge) a friend (node). Read more. I told you, this is a faq. And it is basic. You are looking for the "transitive closure" of your relationship/association (as represented by a table). – philipxy Jun 11 '17 at 01:55
  • I do not want another table at all. I am looking for the best results with my current schema – Marius S Jun 11 '17 at 02:00
  • You do not need another table, you *gave* a table representing your relationship/association. ("Relationship" as assocaition, which is what a table represents, is a different use of the word from "relationship" meaning FK.) PS "Best" means nothing. You need to learn some basics. Good luck. – philipxy Jun 11 '17 at 02:02
  • @philipxy If he's here asking a question that obviously means he's trying to learn. Even if you think it's a dumb question you can be nice about responding instead of being a jerk. – FrenchMajesty Jun 11 '17 at 02:35
  • 2
    @FrenchMajesty It's not a dumb question. (Although it is faq and a duplicate). I am not being a jerk. I gave some helpful facts, questions and actions. The OP has multiple times told me (once after reading for all of 5 minutes) that my comments are inapplicable, without asking for an explanation, and even though I have told them otherwise, & that their question is a faq, & a canonical SO answer, & how they should educate themselves, & what their problem is called. [PS](http://guilhembichot.blogspot.ca/2013/11/with-recursive-and-mysql.html) – philipxy Jun 11 '17 at 03:57

2 Answers2

1

first create view detecting friendships: 

CREATE VIEW friendship (friend1, friend2) 
AS SELECT p1.id, p2.id from person as p1, person as p2
WHERE 
(SELECT count(*) from friendship_request as fr1 WHERE 
fr1.sender = p1.id AND fr1.receiver = p2.id) > 0 
AND 
(SELECT count(*) from friendship_request as fr2 WHERE 
fr2.receiver = p1.id AND fr1.sender = p2.id) > 0

now query for 1st level connections is as simple as

SELECT p1.name, p1st.name, p2.name 
FROM person as p1, person as p2, person as p1st, 
friendship as fs1, friendship as fs2 
WHERE p1.id = fs1.friend1 
AND p2.id = fs2.friend1 
AND fs1.frind2 = fs2.frind2 
AND fs2.frind2 = p1st.id

for 2nd level connections:

SELECT DISTINCT p1.name, p2nd1.name, p2nd2.name, p2.name 
FROM person as p1, person as p2, person as p2nd1, person as p2nd2, 
friendship as fs1, friendship as fs2, friendship as fs2nd
WHERE  p1.id = fs1.friend1 
AND p2.id = fs2.friend1 
AND fs1.frind2 = fs2nd.frind2 
AND fs2.frind2 = fs2nd.frinend2 
AND p2nd1.id = fs1.frind2 
AND p2nd2.id = fs2.frind2

And so on.

Did not test but in any normal RDBMS should work :-)

Eugene Bartosh
  • 324
  • 3
  • 12
0

I would create a graph structure. An Adjacency List representation would work well. Then you can just run depth first search.

HDev
  • 29
  • 3
  • 3