Task: Rowset of all reachable(in any direction) nodes from any node in a graph. In other words I need to extract all nodes of a particular graph from a table in the database where graph specified by an id of any one graph node. The final goal is a map in the app.
Table structure of
DocumentDependency is simple as:
descendant_id | predecessor_id ------------------------------- 2857 | 2856 2858 | 2856 2859 | 2856 2859 | 2857 2860 | 2859 2861 | 2859
Finally I came up with CTE:
WITH RECURSIVE DocumentGraph AS ( SELECT CASE WHEN predecessor_id = 2858 THEN descendant_id ELSE predecessor_id END AS anchor_id, ARRAY[ROW(predecessor_id, descendant_id)] path, 1 depth FROM DocumentDependency WHERE 2858 in (descendant_id, predecessor_id) UNION ALL SELECT CASE WHEN DocumentDependency.predecessor_id = DocumentGraph.anchor_id THEN DocumentDependency.descendant_id ELSE DocumentDependency.predecessor_id END, path || ROW(DocumentDependency.predecessor_id, DocumentDependency.descendant_id) path, depth + 1 FROM DocumentGraph JOIN DocumentDependency ON DocumentGraph.anchor_id in (DocumentDependency.predecessor_id, DocumentDependency.descendant_id) AND ROW(DocumentDependency.predecessor_id, DocumentDependency.descendant_id) <> ALL(path) )
There are a lot discussions about directed graphs and this is sort of a compilation from stack* and one useful book1, but I'm experiencing an overdose and what I need is criticism.
- Maybe this is generally an inappropriate approach? =)
- Lightweight? (What if DocumentDependency will have 500k rows?)
- Portability? (for now I'm using PostgreSQL12)
- Simplicity? (I'm under custom ORM and need to extend for ROWS/ARRAYS/CTE support but probably there is a way to avoid using arrays?)
1Joe Celko's Trees and Hierarchies in SQL For Smarties (highly recommended, btw ;)