Generating Dynamic Breadcrumb Menus Using Tree Table & Recursive CTE
Tags: cte, sql, breadcrumb, tree
Published: 2023-12-02 15:19:34

It's a quite common pattern to store application navigation information in the database to achieve flexibility and control over generating dynamic menus based on roles. Many enterprise applications including large Core Banking Solutions with thousands of hierarchical navigation information store hierarchical data in a database using **Tree Data Structure**. However, there are a few different approaches that can be used to effectively store and manage tree data in an RDBMS. One of the common models is the **Adjacency List Model**. The adjacency list model is a straightforward approach to representing trees in an RDBMS. It involves storing each node in a separate row in a table, along with a reference to its parent node.

So In this blog post, we will learn about extracting the ancestor data of a menu item from RDBMS so that we can visualize the Breadcrumb Menu in the user interface. 


![Breadcrumb Menu Example](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/m56qzd8z84okgl5u4l94.png)
<p>
    <em>Example of a Breadcrumb Menu</em>
</p>
---

## Prerequisites 

1. Postgres database installed in Local / Cloud machine.
2. PgAdmin for executing the query and visualizing the result.
3. Prior knowledge of Recursive CTE will be helpful.

## Preparing the Data

Let's create the Navigations Tree Table first. 

```sql
CREATE TABLE navigations (
	id SERIAL PRIMARY KEY,
	title VARCHAR(50) UNIQUE NOT NULL,
	parent_id INT,
	created_on TIMESTAMP NOT NULL DEFAULT NOW(),
	FOREIGN KEY (parent_id) REFERENCES navigations (id)
);
```
Here we are storing **id** as a primary key and **parent_id** as a foreign key referencing the primary key of another row in the same table. 

Our table is ready now. So let's insert some dummy data for navigation.

```sql
INSERT INTO navigations (title)
VALUES ('User');

INSERT INTO navigations (title)
VALUES ('Role');

INSERT INTO navigations (title, parent_id)
VALUES ('User Reports', (SELECT id FROM navigations WHERE title = 'User'));

INSERT INTO navigations (title, parent_id)
VALUES ('Daily Reports', (SELECT id FROM navigations WHERE title = 'User Reports'));

INSERT INTO navigations (title, parent_id)
VALUES ('User Activity', (SELECT id FROM navigations WHERE title = 'Daily Reports'));

INSERT INTO navigations (title, parent_id)
VALUES ('Role Reports', (SELECT id FROM navigations WHERE title = 'Role'));
```

After the successful execution of Insert Statements, we will have our tree structure ready for running the Recursive CTE.


![Navigations Table](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/7adg9w25mo7xqkc5oc8j.png) 
<p>
    <em>Navigations Table</em>
</p>
---

## About Recursive CTE

A recursive common table expression (CTE) is a powerful tool for performing recursive queries in SQL. It allows you to traverse hierarchical data structures, such as trees or graphs, and perform operations on the data at each level of the hierarchy.

In Postgres, Recursive CTE can be defined using the `WITH RECURSIVE` clause. It consists of mainly two parts **Anchor Query** and **Recursive Query** combined by the `UNION` clause. 

So let's print 1 to 10 using Recursive CTE and learn its building blocks without spending more time on theory.

```sql
WITH RECURSIVE counter AS (
	SELECT 1 AS count -- Anchor query return 1 (R0)
	UNION -- Combine R0 ... Rn
	-- Recursive Query increment count by 1
	-- Until its value reaches the limit / termination statement
	-- (R1 ... Rn)
	SELECT counter.count + 1 FROM counter
	WHERE counter.count < 10
)
SELECT * FROM counter; -- (Output: 1,2,3,4 ... 10)
```

---


## Preparing the query for Breadcrumb Menu
So let's discuss the content of the Breadcrumb Menu. After clicking any menu item the user is usually routed to a new page/component. The Breadcrumb menu will visualize the path meaning the ancestor tree of a particular node. For instance, if a user clicks on the `User Activity` menu item the breadcrumb menu will display - 

```
User > User Reports > Daily Reports > User Activity
```

A simple Recursive CTE can be used to extract data for equivalent output. 

```sql
WITH RECURSIVE cte_get_parents AS (
    -- Anchor Query
	SELECT 
		id, 
		title, 
		parent_id, 
		created_on,
		0 AS level
	from navigations
    -- Title will be changed based on the user's click
	where title = 'User Activity'
	
	UNION
	
    -- Recursive Query
	SELECT 
		n.id, 
		n.title, 
		n.parent_id, 
		n.created_on,
		c.level - 1
	FROM navigations n INNER JOIN cte_get_parents c
	ON n.id = c.parent_id
)
SELECT 
	id, 
	title, 
	parent_id, 
	created_on,  
	level + (SELECT 
			 ABS(MIN(level)) 
			 from cte_get_parents
		) AS level
FROM cte_get_parents
ORDER BY id ASC;
```

**Explanations**

1. The Anchor query returns the result of the node that we want to extract the ancestors. It also bootstraps the value of `level` so that we can track the depth of each node in the tree.
2. The recursive query takes the result of the anchor query and iterates the rows until `parent_id` becomes `null`. 
3. As we are matching the **ID** of the table to the **Parent ID** of the CTE (`ON n.id = c.parent_id`), We are traversing the table bottom-up - One step towards the root after each iteration. 
4. The recursive query terminates when the `parent_id` of an ancestor node becomes `null` (because no rows with the id `null` in the table). In our case the root node.
5. After termination of the recursive statement `UNION` will merge the results of Anchor and Recursive Statements.
6. The `SELECT` statement after the CTE expression will format the result in our desired format accessing the CTE result. 

## Final Result

After executing the Recursive CTE we will get the desired output. Thus, We can expose an API on top of it and visualize the result using a Breadcrumb UI component.


![Recursive CTE Result](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/zem6uiiplubon1ehsdho.png)

<p>
    <em>Output of the Recursive CTE</em>
</p>
---

## Conclusion
Tree tables are a fundamental data structure for representing hierarchical data in relational databases. They provide an efficient and organized way to store and manage parent-child relationships within a data model. Recursive CTEs (Common Table Expressions) emerged as a powerful tool for traversing and manipulating tree data structures in RDBMS. By leveraging the recursive nature of CTEs, users can effectively query and manipulate hierarchical data, enabling them to extract meaningful insights from complex data relationships. 

From Navigations to Chart-of-Accounts, there are endless use cases of hierarchical data processing using Recursive CTEs.

Happy Coding!!!