0

I'm not very strong using CTE in Postgres, but I think it's the right direction for the graph problem I've got. What I'm trying to do is generate a SQL statement using my edges table combined with a shortest path array. I have two graphs: data and schema. The data graph contains all the data (obviously) and the schema graph describes how the different node types fit together.

Rather than recursively traverse the data graph, which is already large and growing, I created a schema graph, thinking I use it to generate a query for the data graph. The thought is that it would be significantly faster, if it's possible.

Let's say I have the following tables:

Node Type (Schema graph)

  • Patient (node_type_id = 1)
  • Admission (node_type_id = 12)
  • Visit (node_type_id = 15)

Node Type Edge (Schema graph)

  • source
  • target

Nodes (Data graph)

  • node_id
  • node_type_id
  • payload

Edges (Data graph)

  • source
  • target

I also have a shortest path function that returns the path as an array of integers for the schema. Ex: {15,12,1} would translate be equivalent of Visit JOINS Admission JOIN Patient

What I'm trying to do is generate a dynamic select statement to query the nodes. So, given the array above of {15,12,1} I would like the output to be something like:

 SELECT n.node_id, n.payload
   FROM nodes n
   JOIN node_type_edges a
     ON n.node_type_id = a.source
   JOIN node_type_edges b
     ON a.target = b."source"
  WHERE a.source = 15
    AND b.source = 12
    AND b.target = 1;

This is just an example. Reality is the data is connected in various depths, defined by the customer when they create their schema.

I thought some kind of recursive CTE statement would do it, but I’m totally stuck.

pass 1 -> SELECT n.node_id, n.payload
pass 1 ->   FROM nodes n
pass 1 ->   JOIN node_type_edges a
pass 1 ->     ON n.node_type_id = a.source
pass 2 ->   JOIN node_type_edges b
pass 2 ->     ON a.target = b."source"
pass 1 ->  WHERE a.source = 15
pass 2 ->    AND b.source = 12
pass 3 ->    AND b.target = 1;

Is this even possible? Does someone have a better suggestion? Thanks in advance for any suggestions!

0

1 Answer 1

0

You have a basic misunderstanding. Graphs are not Trees, i.e., there is not a unique path to go from A->B. How can the DB determine which path you want?

Also how can you avoid cycles for bidirectional edges? You simply cannot. In other words, a relational database cannot be used for traversing graphs. This is why, there are specialized graph databases like Neo4j, especially for that.

Regarding trees, you can always refer to Joe Celko's "Trees and Hierarchies in SQL for Smarties"

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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