-- This implementation assumes the initial table catgories which is then
-- updated to
DROP TABLE IF EXISTS categories CASCADE;
CREATE TABLE categories (
id serial PRIMARY KEY,
title VARCHAR (50) UNIQUE ,
parent_id INT,
lft INT, -- Left boundary for nested set logic
rgt INT, -- Right boundary for nested set logic
-- depth INT DEFAULT 0,
FOREIGN KEY (parent_id) REFERENCES categories (id));
INSERT INTO categories(title, parent_id) VALUES('Electronics', NULL);
INSERT INTO categories(title, parent_id) VALUES('Televisions', 1);
INSERT INTO categories(title, parent_id) VALUES('Portables', 1);
INSERT INTO categories(title, parent_id) VALUES('Plasma', 2);
INSERT INTO categories(title, parent_id) VALUES('LCD', 2);
INSERT INTO categories(title, parent_id) VALUES('MP3', 3);
INSERT INTO categories(title, parent_id) VALUES('CD', 3);
INSERT INTO categories(title, parent_id) VALUES('Laptops', 3);
INSERT INTO categories(title, parent_id) VALUES('Osio', 6);
-- Computing lft and rgt values using recursion and updating the categories table
WITH RECURSIVE tree_hierarchy AS (
-- 1. Locate the root node
SELECT id, title, parent_id,
CAST(id AS TEXT) AS execution_path
FROM categories
WHERE parent_id IS NULL
UNION ALL
-- 2. Traverse down the tree and assemble the sortable string path
SELECT child.id, child.title, child.parent_id,
CONCAT(parent.execution_path, ',', child.id)
FROM categories child
INNER JOIN tree_hierarchy parent ON child.parent_id = parent.id
),
numbered_steps AS (
-- 3. Calculate sequence step orders via DFS layout
SELECT id,
ROW_NUMBER() OVER (ORDER BY execution_path) AS dfs_order
FROM tree_hierarchy
),
descendant_counts AS (
-- 4. Count complete descendant sub-trees per item
SELECT parent.id, COUNT(child.id) AS total_descendants
FROM tree_hierarchy parent
LEFT JOIN tree_hierarchy child ON child.execution_path LIKE CONCAT(parent.execution_path, '%')
GROUP BY parent.id
),
calculated_bounds AS (
-- 5. Synthesize final math limits
SELECT n.id,
((n.dfs_order * 2) - n.dfs_order) AS final_lft,
(((n.dfs_order * 2) - n.dfs_order) + (d.total_descendants * 2) - 1) AS final_rgt
FROM numbered_steps n
JOIN descendant_counts d ON n.id = d.id
)
-- 6. Apply mapped variables directly back into columns
UPDATE categories c
SET lft = cb.final_lft, rgt = cb.final_rgt
FROM calculated_bounds cb WHERE c.id = cb.id;
-- Alternatively, it is possible to update the table categories manually as follows:
UPDATE categories SET lft = 1, rgt = 18 WHERE title = 'Electronics';
UPDATE categories SET lft = 2, rgt = 7 WHERE title = 'Televisions';
UPDATE categories SET lft = 3, rgt = 4 WHERE title = 'Plasma';
UPDATE categories SET lft = 5, rgt = 6 WHERE title = 'LCD';
UPDATE categories SET lft = 8, rgt = 17 WHERE title = 'Portables';
UPDATE categories SET lft = 9, rgt = 12 WHERE title = 'MP3';
UPDATE categories SET lft = 10, rgt = 11 WHERE title = 'Osio';
UPDATE categories SET lft = 13, rgt = 14 WHERE title = 'CD';
UPDATE categories SET lft = 15, rgt = 16 WHERE title = 'Laptops';
select * from categories;
-- Find all Leaf Nodes
SELECT title
FROM categories
WHERE rgt = lft + 1;
-- Retrieve a Full Path
SELECT parent.title
FROM categories AS node,
categories AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
AND node.title = 'Osio'
ORDER BY parent.lft;
-- Find the total number of Descendants
SELECT title, (rgt - lft - 1) / 2 AS total_descendants
FROM categories
WHERE title = 'Portables';
-- Finding a subtree
SELECT child.*
FROM categories AS parent
JOIN categories AS child ON child.lft BETWEEN parent.lft AND parent.rgt
WHERE parent.title = 'Portables'
ORDER BY id asc;
-- Retrieve 'Portables' and all its descendants
SELECT child.*
FROM categories AS parent
JOIN categories AS child ON child.lft BETWEEN parent.lft AND parent.rgt
WHERE parent.title = 'Portables';
-- The query identifies the depth (level) for every category in your table
SELECT node.title, (COUNT(parent.title) - 1) AS depth
FROM categories AS node,
categories AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.title, node.lft
ORDER BY node.lft;
-- Finding the root node
SELECT *
FROM categories c
WHERE parent_id IS NULL;
-- Finding the immediate children of a node
SELECT *
FROM categories c
WHERE parent_id = 1;
-- Finding how many immediate children a node has
SELECT parents.title, COUNT(c2.id)
FROM categories parents
JOIN categories c2 ON c2.parent_id = parents.id
GROUP BY parents.title;
-- Finding the leaf nodes
SELECT c.id, c.title
FROM categories c
WHERE c.id NOT IN (
SELECT parent_id FROM categories c2
WHERE parent_id IS NOT NULL);
-- Using recursion
-- Finding the parent of a node by id
WITH RECURSIVE category_path (id, title, parent_id) AS
(
SELECT id, title, parent_id
FROM categories
WHERE id = 3
UNION ALL
select c.id, c.title, cp.parent_id
FROM category_path AS cp JOIN categories AS c
ON cp.id = c.parent_id
)
Select * from category_path
LIMIT 1;
-- Finding the parent of a node by title
WITH RECURSIVE category_path (id, title, parent_id) AS
(
SELECT id, title, parent_id
FROM categories
WHERE title = 'Osio'
UNION ALL
select c.id, c.title, cp.parent_id
FROM category_path AS cp JOIN categories AS c
ON cp.id = c.parent_id
)
Select * from category_path
LIMIT 1;
-- Finding full path for each node
WITH RECURSIVE category_path (id, title, path) AS
(
SELECT id, title, title as path
FROM categories
WHERE parent_id IS NULL
UNION ALL
SELECT c.id, c.title, CONCAT(cp.path, ' --> ', c.title)::varchar(50)
FROM category_path AS cp JOIN categories AS c
ON cp.id = c.parent_id
)
SELECT * FROM category_path
ORDER BY path;
-- Finding full path with array and level
WITH RECURSIVE category_path (id, title, parent_id, PATH, lvl) AS
(
SELECT id, title, parent_id, string_to_array(title, '') as PATH, 0 AS lvl
FROM categories
WHERE parent_id IS NULL
UNION ALL
SELECT c.id, c.title, c.parent_id, array_cat(cp.PATH, string_to_array(c.title, '')), cp.lvl + 1 AS level
FROM category_path AS cp JOIN categories AS c ON cp.id = c.parent_id
)
SELECT * FROM category_path;
-- Querying a sub-tree (including the root)
WITH RECURSIVE category_path (id, title, parent_id, PATH, lvl) AS
(
SELECT id, title, parent_id, string_to_array(title, '') as PATH, 0 AS lvl
FROM categories
WHERE id = 3
UNION ALL
SELECT c.id, c.title, c.parent_id, array_cat(cp.PATH, string_to_array(c.title, '')), cp.lvl + 1 AS level
FROM category_path AS cp JOIN categories AS c ON cp.id = c.parent_id
)
SELECT * FROM category_path;
-- Querying a single path from BOTTOM to TOP (including the root)
WITH RECURSIVE category_path (id, title, parent_id, PATH, lvl) AS
(
SELECT id, title, parent_id, string_to_array(title, '') as PATH, 0 AS lvl
FROM categories
WHERE id = 6
--WHERE parent_id IS NULL
UNION ALL
SELECT c.id, c.title, c.parent_id, array_cat(cp.PATH, string_to_array(c.title, '')), cp.lvl + 1 AS level
FROM category_path AS cp JOIN categories AS c ON cp.id = c.parent_id
)
SELECT * FROM category_path;
-- Updating the hierarchy
-- Inserting a new root node
WITH parent AS (
INSERT INTO categories(parent_id)
VALUES (NULL)
RETURNING id
)
UPDATE categories
SET parent_id = parent.id
FROM parent
WHERE parent_id IS NULL;
select * from categories;
-- Inserting a node between two existing nodes
WITH created_node AS (
INSERT INTO categories(parent_id)
VALUES (1)
RETURNING id
)
UPDATE categories
SET parent_id = created_node.id
FROM created_node
WHERE categories.id = 10;
-- Adding a child node, that gets it’s siblings as children
WITH created_node AS (
INSERT INTO categories(parent_id)
VALUES (2)
RETURNING id
)
UPDATE categories
SET parent_id = created_node.id
FROM created_node
WHERE categories.parent_id = 2;
SELECT *
FROM categories;