Recursive Query to Find Grandchild-Child-Parent-Grandparent in a Table

In this article, we will explore how to find grandchild-child-parent-grandparent objects from one table using recursive SQL queries. We’ll break down the problem step by step and provide example code snippets to illustrate the process.

Understanding the Problem

We have a table with columns ID and ParentId, where each row represents an element in a hierarchical structure. The goal is to write a query that can find all grandchild-child-parent-grandparent objects from a given ID, regardless of their position in the hierarchy.

To illustrate this, let’s consider a sample table structure:

+----+----------+
| ID | ParentId |
+----+----------+
| 23 | null     |
| 22 | 23       |
| 21 | 22       |
| 13 | null     |
| 12 | 13       |
| 11 | 12       |
+----+----------+

In this table, the ID 23 is a root element (i.e., its ParentId is null). The IDs 22 and 21 are children of 23, while the IDs 13, 12, and 11 are grandchildren of 23. We want to find all objects that have a parent-child relationship with these roots.

Solution Overview

To solve this problem, we will use recursive SQL queries. These queries allow us to recursively join rows in a table based on a condition, effectively traversing the hierarchy.

Here’s a high-level overview of our solution:

1. Identify the root elements (i.e., elements with ParentId = null).
2. Recursively join these roots with their child elements.
3. Continue joining until we reach all levels in the hierarchy.

Recursive Query Example

Let’s implement this solution using a recursive SQL query:

WITH RECURSIVE deepSearch AS (
  -- Base case: select root elements (ID with ParentId = null)
  SELECT "t"."id" as root, 
         "t"."id",
         "t"."parent_id"
  FROM "Table" AS t
  WHERE t.parent_id IS NULL
  
  UNION ALL
  
  -- Recursive step: join child elements with their parent element
  SELECT
    "p".root,
    "c"."id",
    "c"."parent_id"
  FROM "Table" as c
  INNER JOIN deepSearch AS p ON "c"."parent_id" = "p"."id"
)
-- Select all grandchild-child-parent-grandparent objects
SELECT
  rootjoin.id,
  rootjoin.parent_id
FROM deepSearch
INNER JOIN deepSearch as rootjoin 
    ON rootjoin.root = deepSearch.root
WHERE
  deepSearch.id = 23 -- condition of your choice (e.g., 22, 21, 11)
;

This query uses the WITH RECURSIVE clause to define a recursive common table expression (CTE) called deepSearch. The CTE has two parts:

1. The base case: selects all root elements with ParentId = null.
2. The recursive step: joins child elements with their parent element, using the ID from the previous iteration as the join condition.

The final SELECT statement joins the deepSearch CTE with itself, using the root column to match rows across iterations. This effectively traverses the hierarchy and returns all grandchild-child-parent-grandparent objects for the given root ID.

Explanation and Example Walkthrough

Let’s break down this query step by step:

1. Base case: We start by selecting all elements with ParentId = null, which represent the root elements.

+----+----------+
| ID | ParentId |
+----+----------+
| 23 | null     |
+----+----------+

These are the starting points for our recursive query.

2. Recursive step: We then join child elements with their parent element using the id column as the join condition.

SELECT
  "p".root,
  "c"."id",
  "c"."parent_id"
FROM "Table" as c
INNER JOIN deepSearch AS p ON "c"."parent_id" = "p"."id"
;

For example, if we join the row with ID = 22 (c) with its parent element (the row with ID = 23), we get:

+--------+-----+---------+
| root   | id | parent_id |
+--------+-----+---------+
| 23     | 22 | 23      |
+--------+-----+---------+

This shows that the ID 22 is a child of the ID 23.

3. Iteration: We repeat this process, joining each new set of rows with their parent elements, until we reach all levels in the hierarchy.

+--------+-----+---------+--------+-----+---------+
| root   | id | parent_id | root   | id | parent_id |
+--------+-----+---------+--------+-----+---------+
| 23     | 22 | 23      | 23    | 21 | 22       |
+--------+-----+---------+--------+-----+---------+

Now, we have the row with ID = 21 joined with its parent element (the row with ID = 22).

4. Final result: We select all grandchild-child-parent-grandparent objects by joining the deepSearch CTE with itself using the root column to match rows across iterations.

SELECT
  rootjoin.id,
  rootjoin.parent_id
FROM deepSearch
INNER JOIN deepSearch as rootjoin 
    ON rootjoin.root = deepSearch.root
WHERE
  deepSearch.id = 23 -- condition of your choice (e.g., 22, 21, 11)
;

This returns the final result:

+-----+---------+
| id | parent_id |
+-----+---------+
| 22 | 23       |
| 21 | 22       |
+-----+---------+

This shows that the IDs 22 and 21 are children of the ID 23.

Conclusion

In this article, we explored how to find grandchild-child-parent-grandparent objects from one table using recursive SQL queries. We defined a recursive common table expression (CTE) called deepSearch, which traverses the hierarchy by joining child elements with their parent element and repeating until all levels are reached. Finally, we joined the deepSearch CTE with itself to select all grandchild-child-parent-grandparent objects for a given root ID.

This technique can be applied to any table structure where you need to traverse a hierarchical relationship using recursive SQL queries.

Last modified on 2023-12-08