# 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 ๐

Posted in SQL

#### 3 thoughts on “WITH clause and Depth First Search”

1. Deepu says:

fantastic blog.Keep writing.

2. Deepu says: