Hi all!

Any ideas on how to model a directed acyclic graph (DAG) i postgresql? I need the model to be efficient with respect to traversing the graph.

Please see the attached image for an example.

A typical query on the graph is to traverse backwards following all paths from a given node to it's "start nodes" (i.e. nodes with in-degree 0; the nodes named 'f' in the figure).

As an example, given the node 'c3' in the figure I'd like to be able to retrieve all "connecting" nodes, i.e. c1, c2, f1, f2, f3.

Anybody have experience with modeling graphs? I suspect I have to be careful not to run into performance problems on larger graphs (i.e. milions of nodes). As can be seen from the figure, any node can reference any number of nodes, and any node can be references by any number of nodes, i.e. a many-to-many between nodes.


Thank you!

I've never thought about modelling a network diagram like this. Maybe a self referencing, many-many relationship? You would have to explicitly exclude (maybe via trigger?) a node referencing itself.

They're already covering Section C now? I didn't think we were that far into the semester!

-PatP