?
Solved

Building a social network. What's a good DB structure and query for finding how two people are connected?

Posted on 2008-10-26
9
Medium Priority
?
301 Views
Last Modified: 2012-05-05
I'm building a social network where friends can add friends, and so on.

Now Bob wants to know how he's connected to Susan, through mutual friends of theirs.

Two questions:
1)  What's a good data structure to store friend connections?
2) What's a good query to find out how any 2 people are connected (assuming a max of 4 degrees-of-separation or so)?
0
Comment
Question by:pudjam666
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 4
  • 3
  • 2
9 Comments
 
LVL 60

Expert Comment

by:chapmandew
ID: 22809940
Wow...that is more than a little question.  First things first is to determine the DB structure....I am thinking some sort of structure like this (by no means an exhaustive schema, just a simple idea)

Contacts
ContactID
Firstname
Lastname
Other Details

ContactFriends
PrimaryConactID
FriendContactID
OtherDetails...

One thing to consider is that ContactA is ContactB's friend, and vice versa....so, do you create two records for that relationship or just one.  

Does this make sense?
0
 

Author Comment

by:pudjam666
ID: 22809950
Thanks chapmandew.  

So far so good.  I think you're basically saying a "Users" table and a "ParentChild" table.  Sounds good to me.

Now I need to know a good query for finding how user A is connected to user B, through which mutual friends.  

I realize this isn't a simple question, but I figure I can't be the first person to ask it -- and it's gotta be a common enough question that someone here has a great answer.  

0
 
LVL 84

Assisted Solution

by:ozo
ozo earned 300 total points
ID: 22809970
I would use a graph
http://www.nist.gov/dads/HTML/graph.html
http://en.wikipedia.org/wiki/Graph_data_structure
and a meet-in-the-middle search 2 deep from the target nodes
0
Learn how to optimize MySQL for your business need

With the increasing importance of apps & networks in both business & personal interconnections, perfor. has become one of the key metrics of successful communication. This ebook is a hands-on business-case-driven guide to understanding MySQL query parameter tuning & database perf

 

Author Comment

by:pudjam666
ID: 22809990
Ozo - Thanks, that is helpful.  I'm no mathematician but I am a decently clever programmer.  Perhaps I can find some SQL examples of a graph somewhere.  

Anyone else have any ideas? Perhaps something simpler? :)
0
 
LVL 60

Accepted Solution

by:
chapmandew earned 1200 total points
ID: 22810016
Could of ways to do it...for mutual friends (for one particular person)

--get all friends of your primary contact and put in a temp table.
select primarycontactid, friendcontactid
into #temp
from contactfriends
where primarycontactid = @primarycontactid

--now get all contacts of the friends

select *
from contactfriends c
join #temp t on c.primarycontactid = t.friendcontactid

of course, this can be simplified a bit if you're on sql 2005...but this should get you started.
0
 
LVL 84

Expert Comment

by:ozo
ID: 22810020
0
 

Author Comment

by:pudjam666
ID: 22810058
chapmandew - That's great.  You mentioned it could be easier with SQL Server 2005 - which I am using.  Are you referring to recursive queries?  I found some stuff about that on the Microsoft site.
0
 
LVL 60

Assisted Solution

by:chapmandew
chapmandew earned 1200 total points
ID: 22810081
Indeed....Common Table Expressions (CTE)
0
 

Author Comment

by:pudjam666
ID: 22810153
Chapmandew - Thanks much.  Unfortunately you confirmed my theory that it's not that easy of a thing to do, but at least I know I'm on the right track.
0

Featured Post

[Webinar] Lessons on Recovering from Petya

Skyport is working hard to help customers recover from recent attacks, like the Petya worm. This work has brought to light some important lessons. New malware attacks like this can take down your entire environment. Learn from others mistakes on how to prevent Petya like worms.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Why is this different from all of the other step by step guides?  Because I make a living as a DBA and not as a writer and I lived through this experience. Defining the name: When I talk to people they say different names on this subject stuff l…
When there is a disconnect between the intentions of their creator and the recipient, when algorithms go awry, they can have disastrous consequences.
Via a live example, show how to shrink a transaction log file down to a reasonable size.
Viewers will learn how the fundamental information of how to create a table.
Suggested Courses

764 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question