People too often forget about graph databases when talking about NoSQL solutions. Graph databases offer an interesting and elegant alternative to relational databases and I could definitely see a startup decide to use this kind of technology.<p>As far as I know, most graph databases support transactions and offer great scalability. Such databases are also schema-less and can be queried with Gremlin, a powerful graph traversal language (see www.tinkerpop.com).<p>With respect to scalability and transactions, Titan (<a href="http://thinkaurelius.com/" rel="nofollow">http://thinkaurelius.com/</a>) looks very promising: it supports various backends for storage (Cassandra, HBase, etc.) and indexing (currently Elastic Search and Lucene). Graph analytics can be done via Faunus (<a href="http://thinkaurelius.github.io/faunus/" rel="nofollow">http://thinkaurelius.github.io/faunus/</a>), backed by Hadoop.<p>There are other vendors out there (Neo4J, OrientDB, etc.) which offer interesting solutions worth looking at - I'm just a bit less familiar with them.<p>The major downside I see with graph databases is that most of them are fairly recent and their ecosystem is tiny (though growing). Should a startup venture on such young technologies, or stick to mature and battle-tested solutions (ie. relational databases)?<p>Could startups use this kind of graph "NoSQL" databases? I don't see why not. If your startup is some kind of social network, graph databases are certainly an option worth considering. If I were to create a startup, I'd hardly use a document database like MongoDB but I will really consider using a graph database. In the end, it's all about having the right tool in hand, and knowing how to assert what is "right" for you.