Going to graph databases is certainly throwing the baby out with the bathwater. The relational model was invented to address shortcomings in the hierarchical and graph database models.
Still not confused enough? Check this out: http://www.strozzi.it/cgi-bin/CSA/tw7/I/en_US/NoSQL/
I only recently started working with a graph database (a bit over two years now), and it struck me just how terrible relational databases are at relationships, compared to graph databases. I know nothing about the history of databases, but my impression is that relational DBs are basically an expansion of simpler table-based databases that can also handle relations between different entries, if awkwardly. Graph databases are a much better fit and smoother to work with.
Most databases support some form of recursion and have for decades. The reason they don't market themselves as a "graph database" is that the performance and scalability of graph data models in conventional database architectures is typically very poor, so representing your entire data model that way is not encouraged. The way indexing is implemented in many traditional database engine designs, e.g. B-trees, is pathological for some common graph-like traversals. Even databases that market themselves as "graph databases" have conventional internals and perform only marginally better for graph data models than databases that are positioned differently.
The idea of graph databases are great. Unfortunately, the existing implementations all suffer from very poor scalability due to fundamental limitations of the data structures and algorithms used internally. The core theoretical challenges are well-understood but few people are credibly working on addressing those.
I've also heard that some modern graph databases are not true native graph databases below the surface, and therefore perform worse at graph-specific queries.
Edit: is it possible you're talking about Network Model DBs[0]? Wikipedia mentions them being around since the late 1960s, and that they could model graphs, but suggests it's more of a predecessor to graph DBs, which saw a lot of improvements until the arrival of modern commercial graph DBs in the 2000s[1].
Again, I'm not an expert on this at all, but it sounds like there have been significant improvements in graph databases since the 1970s. Much more so than in relational databases.
The hierarchical database evolved from the flat file database by allowing nested records (i.e a record could have sets of child records, arbitrary deep). The graph model further added support for navigation links or pointers between records across the structure, hence supporting a graph model (also commonly called network model at the time).
I believe they just called them "network databases" back then.
