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

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)?
pudjam666Asked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

chapmandewCommented:
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
pudjam666Author Commented:
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
ozoCommented:
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
Ultimate Tool Kit for Technology Solution Provider

Broken down into practical pointers and step-by-step instructions, the IT Service Excellence Tool Kit delivers expert advice for technology solution providers. Get your free copy now.

pudjam666Author Commented:
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
chapmandewCommented:
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

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
ozoCommented:
0
pudjam666Author Commented:
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
chapmandewCommented:
Indeed....Common Table Expressions (CTE)
0
pudjam666Author Commented:
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
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Query Syntax

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.