For example, it's extremely awkward in SQL to find all the elements in a tree. There are at least 4 hacks I know of to fix this, none totally satisfactory. In a NOSQL context you can just store the entire tree - your implementation becomes straightforward and simple.
In general though I agree with you. I can whip out SQL queries in seconds that would take me minutes to write against Mongo, even though they're all technically possible. I love SQL. But it's not the right tool for every situation.
You usually want to query and update subtrees, often concurrently. Storing the entire tree is a horrible way to think about this problem. While some NoSQL databases try to help with this, they are not in any better position to solve the problem than a simple library over an SQL database.
Kinda depends on the use case. Let's say you have a caching layer and update a subtree in your RDBMS. Then you need to go find all values referencing that object and invalidate them. That's potentially a lot of complexity. Of course you could cache only parent objects and fetch the subtree on demand (cache or db). Hello slow.
So I prefer to not use words like "usually" as it truly depends on your application and use case.
I do not see how the caching comment here applies, and I think it is telling that this example still includes updating a subtree. I am wondering if you think by "library" I mean "cache layer": I don't.
So, either the NoSQL solution you are using is incredibly dumb (and your schema is pretty much "id->blob") or it is internally going to have to do just as many joins against separately stored data objects in order to rebuild a concurrently-modifiable tree.
In the former case your NoSQL solution is a really fancy object serialization framework (and probably one that is not optimal for your app) and in the second case it is implementing a database and has a library on top to help you store and index trees.
To be clear, and to go back to my argument: I feel the former provides no real value and the latter could be implemented as a library over a normal SQL solution without having also had to reinvent the storage layer, the transactional semantics, etc..
I'm dealing with this exact problem right now. I'm looking at MongoDB, CouchDB, and Postgres.
I agree that Postgres can do this - I've done it before. But I think you're a bit wrong to dismiss document databases so quickly.
Firstly, the subtree update problem isn't a huge problem. MongoDB allows dot notation to update items within a document. Yes, it is may well have to do just as much work as a SQL database in the update case, but I don't care. I'd prefer it is implemented in the database than something I have to do myself.
Secondly, the schema-free nature of a document database is a killer-feature for me. I have truly schema-free tree data (different levels of the tree have different, unknowable-in-advance data stored against them). Yes, I can implement this in a SQL database schema, but it's going to be an ugly schema (eg, I'll have to use rows to store things that should be columns). It will also be slow because of the hierarchical walking needed in the queries. (Although Postgres helps some here with hierarchical query support).
To your "first", I continue to state: that could be handled in a library. There is no reason why this is better handled inside rather than outside of the database. Insisting that this be provided by the database vendor instead of as a layer on top, however, means that you are now taking an entire backend storage implementation (one that is incredibly touchy, I will mind you: I've been using MongoDB in production for the last eight months and I now consider myself an idiot for having wasted time with it) from someone because they provided a convenient syntax.
To your "second": that is not a property of your usage of trees, and starts a new, unrelated discussion. I have nothing against document-oriented databases, and use them often. I feel you are blurring the line between syntax and implementation with your "slow" comment (again: if you are able to concurrently update those schema-less data items you are going to be taking the same hit you would be getting with any other backend for the separate storage and indexing), but will certainly not argue that there are classes of problems where document-oriented databases are really useful. However, trees in particular are not one of their killer features.
You just store the entire tree? Then how do you get a subtree? I don't think you're solving anything by just storing the whole tree as one thing. I mean you can do that in SQL too if you want.
MongoDb lets you query inside the document/tree. It's sort of like how some databases (eg Postgres: http://www.postgresql.org/docs/current/static/xml2.html) let you store XML in a blob, then query inside that using XPath
And yes, XML/XPath support in SQL databases allows them to act as schema-free document stores. However, they aren't optimized for that, so indexing inside the document is limited. OTOH, SQL DB vendors might be able to add that quicker than NoSQL vendors can improve tool support and querying. OTOH you have to deal with XML instead of JSON. OTOH...
In general though I agree with you. I can whip out SQL queries in seconds that would take me minutes to write against Mongo, even though they're all technically possible. I love SQL. But it's not the right tool for every situation.