Graph databases are morphologically a superset of relational databases.
Combine a graph db with document support and it can be a big win to not have to model every nested document while getting O(1) query time join performance.
Is it a strict superset? Many graph DBs are implemented using relational ones. This doesn't make a graph DB a good tool for the job of a relational DB or vice versa. Their features and optimizations surround pretty different use cases. To scrape the surface, I can't SQL-query a graph, and I can't DFS-query a relational DB. Relational DBs nowadays have document columns like jsonb, btw, but usually you use them sparingly.
DBs are also the biggest area where ideal design and abstraction will quickly give way to practical concerns like performance (measured, not big-O). Generally, nothing is going to look like it did on paper.
Generally, the difference between being able to do SQL or depth-first searching comes down to the storage layer. Traditional row-oriented RDBMSs can’t do DFS efficiently, but a RDBMS backed by RDF-like columnar storage sure could.
Combine a graph db with document support and it can be a big win to not have to model every nested document while getting O(1) query time join performance.