WITH clause and Depth First Search

In this article, I am going to explain how you can implement the depth first search with using the WITH clause or also known as subquery factoring clause. Suppose that you have the following data set.

    SELECT 1 ID, 'A' NODE, NULL PARENT_NODE FROM DUAL
    UNION ALL
    SELECT 2, 'B', 'A' FROM DUAL
    UNION ALL
    SELECT 3, 'C', 'A' FROM DUAL
    UNION ALL
    SELECT 4, 'D', 'B' FROM DUAL
    UNION ALL
    SELECT 5, 'E', 'B' FROM DUAL
    UNION ALL
    SELECT 6, 'F', 'C' FROM DUAL
    UNION ALL
    SELECT 6, 'G', 'E' FROM DUAL;

The relation between each node can be seen from the below diagram. In addition, as in the depth first search algorithm, I want to enumerate each node as follows.

Let’s find the parent ids first.

WITH
Q1 AS (
    SELECT 1 ID, 'A' NODE, NULL PARENT_NODE FROM DUAL
    UNION ALL
    SELECT 2, 'B', 'A' FROM DUAL
    UNION ALL
    SELECT 3, 'C', 'A' FROM DUAL
    UNION ALL
    SELECT 4, 'D', 'B' FROM DUAL
    UNION ALL
    SELECT 5, 'E', 'B' FROM DUAL
    UNION ALL
    SELECT 6, 'F', 'C' FROM DUAL
    UNION ALL
    SELECT 6, 'G', 'E' FROM DUAL    
),
Q2(id, node, parent_no, parent_id, lvl) AS (
    SELECT q1.id, q1.node, q1.parent_node, null parent_id, 1 FROM q1 where id = 1
    union all
    SELECT q1.id, q1.node, q1.parent_node, q2.id, q2.lvl + 1 FROM q1, q2 where q1.parent_node = q2.node
)
SELECT * FROM Q2;

As you can see, branch level is also calculated in the recursive part. Time to get DFS column. Notice that how easy it can be to get with only a single command, highlighted in the code snippet below.

WITH
Q1 AS (
    SELECT 1 ID, 'A' NODE, NULL PARENT_NODE FROM DUAL
    UNION ALL
    SELECT 2, 'B', 'A' FROM DUAL
    UNION ALL
    SELECT 3, 'C', 'A' FROM DUAL
    UNION ALL
    SELECT 4, 'D', 'B' FROM DUAL
    UNION ALL
    SELECT 5, 'E', 'B' FROM DUAL
    UNION ALL
    SELECT 6, 'F', 'C' FROM DUAL
    UNION ALL
    SELECT 6, 'G', 'E' FROM DUAL    
),
Q2(id, node, parent_no, parent_id, lvl) AS (
    SELECT q1.id, q1.node, q1.parent_node, null parent_id, 1 FROM q1 where id = 1
    union all
    SELECT q1.id, q1.node, q1.parent_node, q2.id, q2.lvl + 1 FROM q1, q2 where q1.parent_node = q2.node
)
SEARCH DEPTH FIRST BY ID SET DFS
SELECT * FROM Q2;

WITH
Q1 AS (
    SELECT 1 ID, 'A' NODE, NULL PARENT_NODE FROM DUAL
    UNION ALL
    SELECT 2, 'B', 'A' FROM DUAL
    UNION ALL
    SELECT 3, 'C', 'A' FROM DUAL
    UNION ALL
    SELECT 4, 'D', 'B' FROM DUAL
    UNION ALL
    SELECT 5, 'E', 'B' FROM DUAL
    UNION ALL
    SELECT 6, 'F', 'C' FROM DUAL
    UNION ALL
    SELECT 6, 'G', 'E' FROM DUAL    
),
Q2(id, node, parent_no, parent_id, lvl) AS (
    SELECT q1.id, q1.node, q1.parent_node, null parent_id, 1 FROM q1 where id = 1
    union all
    SELECT q1.id, q1.node, q1.parent_node, q2.id, q2.lvl + 1 FROM q1, q2 where q1.parent_node = q2.node
)
SEARCH DEPTH FIRST BY ID SET DFS
SELECT 
    LISTAGG(NODE||' ('||DFS||')', ' - ') WITHIN GROUP(ORDER BY DFS) DFS_PATH
FROM Q2;

A (1) - B (2) - D (3) - E (4) - G (5) - C (6) - F (7)

I hope it helps 🙂

Caglar's Oracle Blog

3 thoughts on “WITH clause and Depth First Search”

Leave a Reply Cancel reply