I read Blockeel's article that is comparing different paradigms how to represent data. He mentions following advantages of the relational paradigm in comparison to graph paradigm:

  1. They can naturally represent non-binary relationships.
  2. There is a standard way of associating information with each individual or relationship.
  3. They naturally distinguish between different types of individuals, each type possibly having a different kind of information associated with it.

Can you agree on this list of limitations of the graph paradigm in comparison to relational paradigm?

And can you agree, that in the regard of expressiveness of the paradigms it holds: logic ⊃ relational ⊃ graph ?


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.

|improve this answer|||||
  • And then there is a graph databases based on a relational database. agensgraph.com – a_horse_with_no_name Mar 30 '17 at 11:16
  • 1
    I concluded that it is possible to theoretically compare expressiveness of predicate logic, relational algebra and graph theory since their definitions are succinct enough to reason about. It is also possible to empirically compare different implementations of databases on given data and application scenarios. But it is close to impossible to compare expressiveness of languages like Datalog, SQL and Cypher because their definitions are complex and sometimes underdefined. In this regard, I particularly like a quote from Libkin: "To put it mildly, SQL is not very easy to reason about". – user824276 Apr 1 '17 at 13:18
  • Merely focussing on the structure of the data is not sufficient to prove equivalence. To show equivalence one must show an equivalence to relational algebra. – dan b Oct 5 '18 at 12:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.