# Fetching all nodes of a directed graph by an id of any node

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.

1. Maybe this is generally an inappropriate approach? =)
2. Lightweight? (What if DocumentDependency will have 500k rows?)
3. Portability? (for now I'm using PostgreSQL12)
4. 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 ;)

• Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. – Mast Jun 9 at 16:53

I am not well qualified to answer this, as I know nothing of PostgreSQL or the RECURSIVE extension you are using, so unfortunately I cannot very well comment on your solution.

However perhaps it can be tackled with (relatively!) standard SQL. Let's define a temporary table

CREATE TABLE #Temp ( id int, status int )


A status of 1 will indicate the node is reachable, but it has not yet been processed, a status of 2 indicates the node is reachable, and all immediate descendants have been added. We initialise by inserting the starting node ( I think in your example it is 2858 ).

INSERT INTO #temp ( id, status ) VALUES ( 2858, 1 )


Now we can set up a loop to insert all the reachable nodes:

DECLARE @x int
WHILE 1 = 1
BEGIN
SELECT @x = -1 -- Some value that is not a valid node id
SELECT @x = id FROM #Temp WHERE Status = 1
IF @x = -1 BREAK -- All reachable nodes processed.

INSERT INTO #temp( id, status )
SELECT descendant_id, 1
FROM DocumentDependency WHERE predecessor_id = @x
AND descendant_id NOT in ( SELECT id FROM #Temp )

UPDATE #temp SET status = 2 WHERE id = @x
END


When the loop terminates, #Temp should contain all the reachable node ids. Provided suitable indexes are defined, I think this should be reasonably efficient. As a variation, you could perhaps process multiple nodes with status 1 on each iteration of the loop, I will leave that as an exercise ( you may need an extra status value to differentiate between nodes that have just been added and nodes that are being processed ).

Based on the nearly the same idea from Celko's book I came up with another version without arrays&rows but still using common table expression.

WITH RECURSIVE DocumentGraph AS
(
SELECT DISTINCT
document1_id document2_id,
0 depth,
'/2856' path

FROM DocumentCyclicDependency

WHERE
document1_id = 2856

UNION ALL

SELECT
document_dependency.document2_id,
document_graph.depth + 1,
document_graph.path || '/' || document_dependency.document2_id

FROM
DocumentCyclicDependency AS document_dependency,
DocumentGraph AS document_graph

WHERE
document_graph.document2_id = document_dependency.document1_id
AND
document_graph.path NOT LIKE '%' || document_dependency.document2_id || '%'
)

SELECT document2_id, depth, path
FROM DocumentGraph


DocumentCyclicDependency is actually a tricky view:

CREATE VIEW DocumentCyclicDependency(document1_id, document2_id) AS

SELECT descendant_id, predecessor_id FROM DocumentDependency

UNION ALL

SELECT predecessor_id, descendant_id FROM DocumentDependency;