I mean REST has its place. For example, it has very predictable performance and well-known cache characteristics. The problem is when you want to fetch data in repeated rounds, or when you want to fetch data that isn't expressed well as a hierarchy (think a graph with cycles -- not uncommon). That's where it breaks down.
I think you can get pretty far with batched REST, but I'd like to see some way to query graphs in an easier way.
I think REST is orthogonal to relational data. (Actual REST, that adheres to HATEOAS and a real REST standard. If one rolls his own JSON services, it's not REST.) HATEOAS puts no constraint on how your data is shaped. A specific implementation of REST may or may not have a nice way to navigate graphs.
How is REST problematic for cyclic graphs? I mean the Web is a graph with many cycles and the Web is the defining instance of a REST application. HATEOAS, a pillar of REST, seems, among other things, to be particularly apt for dealing with arbitrary graphs.
