1

This question is about attempting to model/design an elementary graph-like database within postgres.

The starting point is that graphs have:

  1. Nodes
  2. Nodes have properties
  3. Node are connected by (bi/uni-directional) edges
  4. Edges, too, have properties.

As an example, we consider a situation where the entities/nodes are people and news articles. There can be edges between people, and people can be friends or followers with each other, and can have a "similarity" value.

So in trying to mimic a graph in postgres, we first create a single-columned table called Node. The actual nodes people and articles are inherited from this table. Then there's another table called node_property with a foreign key to node. From the table node_property, we inherit two tables called people_property and articles_property, with foreign keys to the people and articles tables respectively. There could possibly be more than one property table per node, for instance if one wanted to split out read-heavy and write-heavy columns, or based on some other criteria.

Then we do edges. First a table called edge with an id, and two columns called source and target, with foreign keys to any of the node tables (i.e. people or property). From this edge parent table, we inherit three tables called person_person with both fk's to the people table, article_article with both fk's to the articles table, and similarly person_article. Finally there is a table called edge_property with a foreign key to the edge table. From this edge_property table, we inherit property tables for each of the 3 aforementioned edges. These edge property tables have info like date when person read the article, boolean for if the person liked/shared the article, boolean for if the two persons are friends, and so on.

This basically looks just like a highly normalized regular rdbms design. The (recursive) CTE's feature of Postgres comes in very useful when doing actual graph-like queries - for example, to find articles liked by friends of friends, etc. Materialized views using multiple inner joins are used heavily for fast queries across multiple tables.

The biggest advantage this offers is the stability of postgres, with the ability to do some graph-like things. The outstanding questions are:

  1. What are the shortcomings of this sort of design? This is being run as an experiment, so I'm sure there are plenty. Are there ways this can be improved? What is this missing?
  2. A specific point, does it make sense to have separate node/edge and the corresponding property tables or is better if they're combined (i.e. all properties in the node table itself)?
  • 2
    Some thoughts, you may end up discovering that recursive cte's are to slow, you also need to be careful with cycles in the graph. Not sure how materialized views are going to help, is there an upper limit on the transitive closure of a node? You miy find some interest in the classic paper on the subject of transitive closure of graphs in sql: ` homepages.inf.ed.ac.uk/libkin/papers/tc-sql.pdf` – Lennart Apr 7 '18 at 7:19
  • 2
    Take a look at this interesting project. – Vérace Apr 7 '18 at 11:21
  • @Vérace Yes, I am well aware of the Agensgraph project and its background. If this experiment goes well, we might as well consider investing the effort to implement an instance of Agensgraph. – Yogesch Apr 7 '18 at 12:26

Your Answer

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

Browse other questions tagged or ask your own question.