You can usually get around this. Many people make their resources have too much hierarchy; there's nothing inherently unRESTful about having a flat one.
You should _not_ be having 3-4 round trips for every API interaction. Each request is an interaction. Hypermedia APIs expose a workflow, not a data model.
I would say this is true of REST APIs. Not necessarily hypermedia APIs. An API that directly exposed a graph database as an HTTP-based API using hypertext/links within resources would still need to be classified as a hypermedia API, but would fail to adhere to the HATEOAS principle.
Edit: More specifically - a graph database that exposed itself with links for every edge and a resource for every node.
Secondly, when your data is hierarchical, it's nice for other reasons to reflect this in your URI structure. It's intuitive (and thus discoverable in its own way) and can make for human-friendly URLs (especially when your datatypes have natural identifiers).
It's pretty trivial to have the client hit the root on startup, and then cache that and never make another call. API roots don't change very much.
> First, are there then multiple roots?
Nope. Here's an example of what I call the 'hypermedia proxy pattern' in Sinatra: https://gist.github.com/3172911
I based this off of this talk by Jon Moore: https://vimeo.com/20781278 and demo'd it at the end of this presentation: http://oredev.org/2012/sessions/designing-hypermedia-apis
Basically, you can fold elements of the collection up into the parent, and the client will automatically make less requests. Jon's presentation goes from 14 requests for the first iteration to 2 on the first hit, 1 every hit thereafter, with no changes to the client.
> when your data is hierarchical, it's nice for other reasons to reflect this in your URI structure.
Sure! So provide both: one 'deep link' or full collection in the root (or wherever) response, but also serve the data as a separate resource that's hierarchical. Best of both worlds.
That's true and will work in most cases, but perhaps not when client sessions are short-lived.
> Basically, you can fold elements of the collection up into the parent, and the client will automatically make less requests.
Now it looks like my choices are to either fetch more data than I need, or make more requests than I need.
> Best of both worlds.
Well, both best and worst of both worlds. Each approach needs to stand up to cost-benefit analysis alone or I doubt it's worth maintaining both.
I do see advantages in these patterns, but I think some of them are more theoretical than practical, and I'll take the practical advantage I see today over the theoretical one I might need in the future.