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
294 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
Free Trending Threat Insights Every Day

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

 
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

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

The greatest common divisor (gcd) of two positive integers is their largest common divisor. Let's consider two numbers 12 and 20. The divisors of 12 are 1, 2, 3, 4, 6, 12 The divisors of 20 are 1, 2, 4, 5, 10 20 The highest number among the c…
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…
Via a live example, show how to backup a database, simulate a failure backup the tail of the database transaction log and perform the restore.
Viewers will learn how to use the SELECT statement in SQL and will be exposed to the many uses the SELECT statement has.

706 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

11 Experts available now in Live!

Get 1:1 Help Now