How to model this[Networks, details in post] in database for efficiency and ease of use?

Question

At linkedin, when you visit someones profile you can see how you are connected to them. I believe that linkedin shows upto 3rd level connections if not more, something like

shabda -> Foo user, bar user, baz user -> Joel's connection -> Joel

How can I represent this in the database.

If I model as,

User
  Id PK
  Name Char

Connection
  User1 FK
  User2 FK

Then to find the network, three levels deep, I need to get all my connection, their connections, and their connections, and then see if the current user is there. This obviously would be very inefficient with DB of any size, and probably clunky to work with as well.

Since, on linked in I can see this network, on any profile I visit, I don't think this is precalculated either.

The other thing which comes to my mind is probably this is best not stored in a relational DB, but then what would be the best way to store and retrieve it?

Answer 1

My recommendation would be to use a graph database. There seems to be only one implementation currently available, and that's Neo4j. It's written in Java, but has bindings to Ruby and Scala (Python in progress).

If you don't know Java, you probably won't be able to find anything similar on any other platform (yet), unfortunately. However, if you do know Java (or are at least willing to learn), it's way worth it. (Technically you don't even need to learn Java because of the Ruby/Python bindings.) Neo4j was built for exactly what you're trying to do. You'd go through a ton of trouble trying to implement this in a relational database, when you'd be able to do the exact same thing in only a few lines of Java code, and also much more efficiently.

If that's not an option, I'd still recommend looking at other database types such as object databases. Relational databases weren't built for this kind of thing, and you'd go through more pain by trying to do it in an RDBMS than by switching to a different kind of database and learning it.