3
\$\begingroup\$

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 ;)

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Mast Jun 9 at 16:53
3
\$\begingroup\$

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 ).

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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;
| improve this answer | |
\$\endgroup\$

Your Answer

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

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