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
295 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
  • 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
 

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
Best Practices: Disaster Recovery Testing

Besides backup, any IT division should have a disaster recovery plan. You will find a few tips below relating to the development of such a plan and to what issues one should pay special attention in the course of backup planning.

 
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

Enterprise Mobility and BYOD For Dummies

Like “For Dummies” books, you can read this in whatever order you choose and learn about mobility and BYOD; and how to put a competitive mobile infrastructure in place. Developed for SMBs and large enterprises alike, you will find helpful use cases, planning, and implementation.

Question has a verified solution.

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

Suggested Solutions

Prime numbers are natural numbers greater than 1 that have only two divisors (the number itself and 1). By “divisible” we mean dividend % divisor = 0 (% indicates MODULAR. It gives the reminder of a division operation). We’ll follow multiple approac…
PL/SQL can be a very powerful tool for working directly with database tables. Being able to loop will allow you to perform more complex operations, but can be a little tricky to write correctly. This article will provide examples of basic loops alon…
This video shows, step by step, how to configure Oracle Heterogeneous Services via the Generic Gateway Agent in order to make a connection from an Oracle session and access a remote SQL Server database table.
Using examples as well as descriptions, and references to Books Online, show the different Recovery Models available in SQL Server and explain, as well as show how full, differential and transaction log backups are performed

947 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

Need Help in Real-Time?

Connect with top rated Experts

18 Experts available now in Live!

Get 1:1 Help Now