Graphs in the database: SQL meets social networks | Hacker News Reader

Graphs in the database: SQL meets social networks

techportal.ibuildings.com

51 pointszhiping15 comments

Looks like their database couldn't handle the traffic of a non-social network...

The 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...

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.

Twitter does this. Flockdb is built ontop of an RDBMS

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.)

Neo4J is proper?

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.

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.......

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).

2 million a second? That must be with cached data, no way it's picking up from disk that fast, even in the case where it has all the data lined up.

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.

Yes, Neo4j has a caching algorithm that optimizes traversals.

See http://docs.neo4j.org/chunked/stable/configuration-caches.ht..., http://docs.neo4j.org/chunked/stable/performance-guide.html

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.

The website is down

> Error establishing a database connection

Quite ironic, considering the title

When I go there I just told that the database is unavailable ;)

F5 and eventually it worked for me

Reply on news.ycombinator.com