the downside is that unlike a proper graph database (such as neo4j) you can only query a single hop per SQL query (which is fine for twitter, since there is no requirement for 'followers of followers' etc.)
I thought their use of WITH RECURSIVE in the demos on the article linked was interesting. It should allow you to recurse to an arbitrary depth. The only problem there is that if you don't set a max depth in your recursive query and you have a closed cycle.... you might end up with an infinite loop.......
I switched to a real graph database when I needed to implement transitive closure, opened up the algorithms book, and figured it would be more trouble to implement myself than deal with the BS for a new product.
This is a brilliant article. Are there other resources that go in as much depth as this article but aren't really stuck to RDBMS? What's the standard to doing graphs like these (linkedin/facebook)? RDBMS or a document oriented DB?
If you mean SQL specific resources, Joe Celko (who's book "SQL for Smarties" was mentioned in the article) has written a good deal. He generally expresses himself using ANSI Standard SQL (and served on the standards committees). But I think that the various NoSql solutions are far more popular for large scale implementations like LinkedIn/Facebook.
Yeah, thats what I thought that NoSql solutions like mongoDB etc. would be better suited for this purpose. However, I haven't come across a resource from NoSql side that goes in depth of explaining how to really implement: How you are connected with a certain person. etc.
Look at graph databases. These are very different from document stores or KV stores (NoSQL doesn't imply any commonality), though a KV store or something like HadoopFS might be used as a storage layer. They have their own challenges to scale up.
If you're storing something like followers or friends, a solution like Redis, Neo4J, Cassandra, etc is likely a better (and simpler to implement) choice.
You can represent a graph in just about any data structure.
The key thing that separates a graph database like Neo4j (http://neo4j.org) from a graph represented in a relational database is that in a real graph database, relationships between nodes are explicitly connected so you don't have any overhead from external index look ups during traversals.
Index look ups also degrade the bigger the index gets in a relational database, whereas in a directly connected graph, it doesn't matter how many other nodes or relationships there are in the graph, performance stays constant -- Neo4j for example does about 2 million traversal steps per second (a traversal step resembles a join in a RDBMS).
16 comments
[ 9.3 ms ] story [ 17.6 ms ] threadThe webpage at http://techportal.ibuildings.com/2009/09/07/graphs-in-the-da... might be temporarily down or it may have moved permanently to a new web address.
Googlecache:
http://webcache.googleusercontent.com/search?q=cache:b6OLx7s...
F5 and eventually it worked for me
http://github.com/twitter/flockdb
the downside is that unlike a proper graph database (such as neo4j) you can only query a single hop per SQL query (which is fine for twitter, since there is no requirement for 'followers of followers' etc.)
What I see is that Neo4J attracts noobs and leaves behind a trail of tears and failed projects.
Something like OWLIM or Virtuoso Open Link handles databases that are 20x bigger.
> Error establishing a database connection
Quite ironic, considering the title
The key thing that separates a graph database like Neo4j (http://neo4j.org) from a graph represented in a relational database is that in a real graph database, relationships between nodes are explicitly connected so you don't have any overhead from external index look ups during traversals.
Index look ups also degrade the bigger the index gets in a relational database, whereas in a directly connected graph, it doesn't matter how many other nodes or relationships there are in the graph, performance stays constant -- Neo4j for example does about 2 million traversal steps per second (a traversal step resembles a join in a RDBMS).
Edit:
I'm not saying you are wrong, I'm curious to see if they can do it and what I can learn from it.
See http://docs.neo4j.org/chunked/stable/configuration-caches.ht..., http://docs.neo4j.org/chunked/stable/performance-guide.html