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
298 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 100 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
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

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 400 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 400 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

Free Tool: Postgres Monitoring System

A PHP and Perl based system to collect and display usage statistics from PostgreSQL databases.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

I'm trying, I really am. But I've seen so many wrong approaches involving date(time) boundaries I despair about my inability to explain it. I've seen quite a few recently that define a non-leap year as 364 days, or 366 days and the list goes on. …
Composite queries are used to retrieve the results from joining multiple queries after applying any filters. UNION, INTERSECT, MINUS, and UNION ALL are some of the operators used to get certain desired results.​
Familiarize people with the process of retrieving data from SQL Server using an Access pass-thru query. Microsoft Access is a very powerful client/server development tool. One of the ways that you can retrieve data from a SQL Server is by using a pa…
Viewers will learn how to use the SELECT statement in SQL to return specific rows and columns, with various degrees of sorting and limits in place.

735 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