Generating Dynamic Breadcrumb Menus Using Tree Table & Recursive CTE

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.

Example of a Breadcrumb Menu

---

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.

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.

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

---

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.

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.

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.

Output of the Recursive CTE

---

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!!!