What can be represented in a relational database that can't be represented in a graph database?
Disclaimer: I am not a computer science academic. There are undoubtedly nuances and implied knowledge in that paper of which I am ignorant. I do, however, have some small practical exposure to these technologies.

To say that graph is a subset of relational would mean there is something that can be done in relational that cannot be done in graph. I would disagree with this. Data can be stored equally in either of these systems. Any graph can be represented relationally by a Node table and an Edge table (perhaps with additional NodeAttribute and EdgeAttribute tables) 1. Any relational database can be stored in graph form with one node per row, one attribute per column and one edge per foreign key. Non-binary relationships can be represented by inserting a junction node to which the multiple edges connect.

I know little of Logic stores (which I believe are also known as triple stores) but they seem to have a very direct translation to graphs and, hence, to a relational model.

As for standards, they only exist because some people decided to sit down and write them. There is nothing inherent in the structure of the universe that caused SQL to come into being. An equal effort could produce standards for graph processing. Languages like Gremlin and Cypher seems to be gaining broad acceptance and may, eventually, lead to a ISO standard graph language. The maths that underlies graph is just as valid as set theory.

The relational model has concepts like schema, primary key and referential integrity which are not part of the graph model. There is no reason why an actual graph DBMS could not implement these features, however. Indeed there are many databases hosted in relational software which are unnormalised, lack primary keys and have no DRI!

Graphs allow traversals of indeterminate length. Some RDBMs allow recursive queries which, although more cumbersome, can accomplish the same effect.

It seems to me these systems differ not so much in the data they can store, but in the ease with which their underlying structures can answer different classes of questions. Relational database engines are optimised to process sets of similarly-structured items (tables). Graphs are optimised for traversing links from node to node.



1 SQL Server 2017 has implemented graph processing with precisely this form. It has added extensions to identify a table as containing nodes or edges.