# SQL Recursion Tutorial: Mastering Hierarchical Data with PostgreSQL

## Table of Contents
1. [Introduction to SQL Recursion](#Introduction-to-SQL-Recursion)
2. [Common Table Expressions (CTEs) Basics](#Common-Table-Expressions-(CTEs)-Basics)
3. [Recursive CTE Syntax](#Recursive-CTE-Syntax)
4. [Real-World Use Cases](#Real-World-Use-Cases)
5. [Finding Leaf Nodes from Root](#Finding-Leaf-Nodes-from-Root)
6. [Finding Root Nodes from Leaf](#Finding-Root-Nodes-from-Leaf)
7. [Advanced Examples](#Advanced-Examples)
8. [Performance Considerations](#performance-Considerations)
9. [Best Practices](#Best-Practices)

## Introduction to SQL Recursion

SQL recursion is a powerful technique for working with hierarchical or tree-structured data. It allows you to traverse parent-child relationships, build organizational charts, navigate category trees, and solve many other problems that involve self-referencing data structures.

PostgreSQL's recursive Common Table Expressions (CTEs) provide an elegant way to write queries that would otherwise require complex joins or multiple queries.

## Common Table Expressions (CTEs) Basics

Before diving into recursion, let's understand CTEs:

-- Basic CTE example
WITH sales_summary AS (
    SELECT 
        region,
        SUM(amount) as total_sales
    FROM sales
    GROUP BY region
)
SELECT * FROM sales_summary WHERE total_sales > 100000;

## Recursive CTE Syntax

A recursive CTE has two parts:
1. **Base case (anchor)**: The starting point of recursion
2. **Recursive case**: The part that references the CTE itself

WITH RECURSIVE cte_name AS (
    -- Base case (anchor)
    SELECT columns FROM table WHERE condition
    
    UNION ALL
    
    -- Recursive case
    SELECT columns FROM table 
    JOIN cte_name ON condition
)
SELECT * FROM cte_name;

## Real-World Use Cases

Let's explore practical examples using different types of hierarchical data.

### 1. Organizational Structure

First, let's create an employee hierarchy table:

-- Create employees table
CREATE TABLE employees (
    employee_id SERIAL PRIMARY KEY,
    name VARCHAR(100) NOT NULL,
    manager_id INTEGER REFERENCES employees(employee_id),
    department VARCHAR(50),
    salary NUMERIC(10,2),
    hire_date DATE
);

-- Insert sample data
INSERT INTO employees (name, manager_id, department, salary, hire_date) VALUES
('John CEO', NULL, 'Executive', 200000, '2020-01-01'),
('Alice VP Sales', 1, 'Sales', 150000, '2020-02-01'),
('Bob VP Engineering', 1, 'Engineering', 160000, '2020-02-01'),
('Carol Sales Manager', 2, 'Sales', 120000, '2020-03-01'),
('David Tech Lead', 3, 'Engineering', 140000, '2020-03-01'),
('Eve Sales Rep', 4, 'Sales', 80000, '2020-04-01'),
('Frank Sales Rep', 4, 'Sales', 75000, '2020-04-01'),
('Grace Developer', 5, 'Engineering', 90000, '2020-04-01'),
('Henry Developer', 5, 'Engineering', 95000, '2020-04-01'),
('Ivy Junior Dev', 8, 'Engineering', 70000, '2020-05-01');

### 2. Product Categories

-- Create categories table
CREATE TABLE categories (
    category_id SERIAL PRIMARY KEY,
    name VARCHAR(100) NOT NULL,
    parent_id INTEGER REFERENCES categories(category_id),
    description TEXT
);

-- Insert sample data
INSERT INTO categories (name, parent_id, description) VALUES
('Electronics', NULL, 'All electronic products'),
('Clothing', NULL, 'All clothing items'),
('Computers', 1, 'Computing devices'),
('Mobile Devices', 1, 'Phones and tablets'),
('Laptops', 3, 'Portable computers'),
('Desktops', 3, 'Desktop computers'),
('Smartphones', 4, 'Smart phones'),
('Tablets', 4, 'Tablet devices'),
('Gaming Laptops', 5, 'High-performance laptops for gaming'),
('Business Laptops', 5, 'Laptops for business use');

### 3. File System Structure

-- Create file_system table
CREATE TABLE file_system (
    id SERIAL PRIMARY KEY,
    name VARCHAR(255) NOT NULL,
    parent_id INTEGER REFERENCES file_system(id),
    type VARCHAR(10) CHECK (type IN ('folder', 'file')),
    size_bytes BIGINT DEFAULT 0,
    created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP
);

-- Insert sample data
INSERT INTO file_system (name, parent_id, type, size_bytes) VALUES
('/', NULL, 'folder', 0),
('home', 1, 'folder', 0),
('var', 1, 'folder', 0),
('user1', 2, 'folder', 0),
('user2', 2, 'folder', 0),
('log', 3, 'folder', 0),
('documents', 4, 'folder', 0),
('projects', 4, 'folder', 0),
('report.pdf', 7, 'file', 2048000),
('sql-tutorial', 8, 'folder', 0),
('tutorial.md', 10, 'file', 15000),
('examples.sql', 10, 'file', 8500);

## Finding Leaf Nodes from Root

### Example 1: Find All Employees Under a Specific Manager

-- Find all employees reporting to John CEO (directly or indirectly)
WITH RECURSIVE employee_hierarchy AS (
    -- Base case: Start with the root manager
    SELECT 
        employee_id,
        name,
        manager_id,
        department,
        salary,
        0 as level,
        ARRAY[name] as path
    FROM employees 
    WHERE name = 'John CEO'
    
    UNION ALL
    
    -- Recursive case: Find all subordinates
    SELECT 
        e.employee_id,
        e.name,
        e.manager_id,
        e.department,
        e.salary,
        eh.level + 1,
        eh.path || e.name
    FROM employees e
    JOIN employee_hierarchy eh ON e.manager_id = eh.employee_id
)
SELECT 
    employee_id,
    name,
    department,
    salary,
    level,
    array_to_string(path, ' -> ') as reporting_path
FROM employee_hierarchy
ORDER BY level, name;

### Example 2: Find All Leaf Employees (No Subordinates)

-- Find employees who don't manage anyone (leaf nodes)
WITH RECURSIVE employee_tree AS (
    SELECT 
        employee_id,
        name,
        manager_id,
        department,
        0 as level
    FROM employees 
    WHERE manager_id IS NULL  -- Start from CEO
    
    UNION ALL
    
    SELECT 
        e.employee_id,
        e.name,
        e.manager_id,
        e.department,
        et.level + 1
    FROM employees e
    JOIN employee_tree et ON e.manager_id = et.employee_id
),
leaf_employees AS (
    SELECT et.*
    FROM employee_tree et
    LEFT JOIN employees subordinates ON subordinates.manager_id = et.employee_id
    WHERE subordinates.employee_id IS NULL  -- No subordinates = leaf node
)
SELECT 
    name,
    department,
    level as depth_from_ceo
FROM leaf_employees
ORDER BY level, name;

### Example 3: Find All Subcategories Under Electronics

-- Find all subcategories under Electronics category
WITH RECURSIVE category_tree AS (
    -- Base case: Start with Electronics
    SELECT 
        category_id,
        name,
        parent_id,
        0 as level,
        name as path
    FROM categories 
    WHERE name = 'Electronics'
    
    UNION ALL
    
    -- Recursive case: Find all subcategories
    SELECT 
        c.category_id,
        c.name,
        c.parent_id,
        ct.level + 1,
        ct.path || ' -> ' || c.name
    FROM categories c
    JOIN category_tree ct ON c.parent_id = ct.category_id
)
SELECT 
    category_id,
    name,
    level,
    path as category_path
FROM category_tree
ORDER BY level, name;

## Finding Root Nodes from Leaf

### Example 1: Find the Complete Management Chain for an Employee

-- Find the complete management chain from a specific employee to CEO
WITH RECURSIVE management_chain AS (
    -- Base case: Start with the specific employee (leaf)
    SELECT 
        employee_id,
        name,
        manager_id,
        department,
        salary,
        0 as level
    FROM employees 
    WHERE name = 'Ivy Junior Dev'  -- Start from leaf employee
    
    UNION ALL
    
    -- Recursive case: Find managers up the chain
    SELECT 
        e.employee_id,
        e.name,
        e.manager_id,
        e.department,
        e.salary,
        mc.level + 1
    FROM employees e
    JOIN management_chain mc ON e.employee_id = mc.manager_id
)
SELECT 
    employee_id,
    name,
    department,
    salary,
    level,
    CASE 
        WHEN level = 0 THEN 'Employee'
        WHEN manager_id IS NULL THEN 'CEO'
        ELSE 'Manager Level ' || level
    END as role_level
FROM management_chain
ORDER BY level;

### Example 2: Find Root Category from Subcategory

-- Find the complete category path from a leaf category to root
WITH RECURSIVE category_path AS (
    -- Base case: Start with a specific subcategory
    SELECT 
        category_id,
        name,
        parent_id,
        0 as level,
        name as full_path
    FROM categories 
    WHERE name = 'Gaming Laptops'  -- Start from leaf category
    
    UNION ALL
    
    -- Recursive case: Move up to parent categories
    SELECT 
        c.category_id,
        c.name,
        c.parent_id,
        cp.level + 1,
        c.name || ' -> ' || cp.full_path
    FROM categories c
    JOIN category_path cp ON c.category_id = cp.parent_id
)
SELECT 
    category_id,
    name,
    level,
    full_path
FROM category_path
ORDER BY level DESC;  -- Show from root to leaf

### Example 3: Find File Path from Root Directory

-- Find the complete file path from root to a specific file
WITH RECURSIVE file_path AS (
    -- Base case: Start with the specific file
    SELECT 
        id,
        name,
        parent_id,
        type,
        0 as level,
        name as path
    FROM file_system 
    WHERE name = 'tutorial.md'  -- Target file
    
    UNION ALL
    
    -- Recursive case: Move up to parent directories
    SELECT 
        fs.id,
        fs.name,
        fs.parent_id,
        fs.type,
        fp.level + 1,
        CASE 
            WHEN fs.name = '/' THEN fp.path
            ELSE fs.name || '/' || fp.path
        END
    FROM file_system fs
    JOIN file_path fp ON fs.id = fp.parent_id
)
SELECT 
    id,
    name,
    type,
    level,
    path as full_path
FROM file_path
WHERE parent_id IS NULL;  -- Get the complete path from root

## Advanced Examples

### 1. Calculate Total Team Size for Each Manager

-- Calculate the total number of people each manager oversees (including indirect reports)
WITH RECURSIVE team_counts AS (
    -- Base case: All employees
    SELECT 
        employee_id,
        name,
        manager_id,
        1 as team_size
    FROM employees
    
    UNION ALL
    
    -- Recursive case: Aggregate team sizes
    SELECT 
        e.employee_id,
        e.name,
        e.manager_id,
        tc.team_size + 1
    FROM employees e
    JOIN team_counts tc ON tc.manager_id = e.employee_id
)
SELECT 
    e.name as manager_name,
    e.department,
    COUNT(tc.employee_id) as total_team_size,
    SUM(CASE WHEN tc.employee_id != e.employee_id THEN tc.team_size ELSE 0 END) as direct_and_indirect_reports
FROM employees e
LEFT JOIN team_counts tc ON tc.manager_id = e.employee_id
GROUP BY e.employee_id, e.name, e.department
HAVING COUNT(tc.employee_id) > 1  -- Only show managers with reports
ORDER BY total_team_size DESC;

### 2. Find Common Ancestors

-- Find the common manager between two employees
WITH RECURSIVE emp1_chain AS (
    SELECT employee_id, name, manager_id, 0 as level
    FROM employees WHERE name = 'Grace Developer'
    
    UNION ALL
    
    SELECT e.employee_id, e.name, e.manager_id, ec.level + 1
    FROM employees e
    JOIN emp1_chain ec ON e.employee_id = ec.manager_id
),
emp2_chain AS (
    SELECT employee_id, name, manager_id, 0 as level
    FROM employees WHERE name = 'Eve Sales Rep'
    
    UNION ALL
    
    SELECT e.employee_id, e.name, e.manager_id, ec.level + 1
    FROM employees e
    JOIN emp2_chain ec ON e.employee_id = ec.manager_id
)
SELECT 
    e1.name as common_manager,
    e1.level as distance_from_emp1,
    e2.level as distance_from_emp2
FROM emp1_chain e1
JOIN emp2_chain e2 ON e1.employee_id = e2.employee_id
ORDER BY e1.level + e2.level  -- Closest common manager first
LIMIT 1;

### 3. Bill of Materials Example

-- Create a bill of materials table for manufacturing
CREATE TABLE bill_of_materials (
    component_id SERIAL PRIMARY KEY,
    name VARCHAR(100) NOT NULL,
    parent_component_id INTEGER REFERENCES bill_of_materials(component_id),
    quantity_needed INTEGER DEFAULT 1,
    unit_cost NUMERIC(10,2),
    component_type VARCHAR(20)
);

-- Insert sample data for a computer assembly
INSERT INTO bill_of_materials (name, parent_component_id, quantity_needed, unit_cost, component_type) VALUES
('Desktop Computer', NULL, 1, 800.00, 'final_product'),
('Motherboard Assembly', 1, 1, 200.00, 'assembly'),
('Power Supply', 1, 1, 80.00, 'component'),
('Case', 1, 1, 60.00, 'component'),
('CPU', 2, 1, 300.00, 'component'),
('RAM', 2, 2, 100.00, 'component'),
('Motherboard PCB', 2, 1, 50.00, 'component'),
('CPU Socket', 7, 1, 10.00, 'part'),
('Capacitors', 7, 50, 0.10, 'part'),
('Resistors', 7, 100, 0.05, 'part');

-- Calculate total cost breakdown with full BOM explosion
WITH RECURSIVE bom_explosion AS (
    -- Base case: Start with final product
    SELECT 
        component_id,
        name,
        parent_component_id,
        quantity_needed,
        unit_cost,
        component_type,
        1 as total_quantity,
        unit_cost as extended_cost,
        0 as level,
        name as path
    FROM bill_of_materials 
    WHERE parent_component_id IS NULL
    
    UNION ALL
    
    -- Recursive case: Explode all subcomponents
    SELECT 
        bom.component_id,
        bom.name,
        bom.parent_component_id,
        bom.quantity_needed,
        bom.unit_cost,
        bom.component_type,
        be.total_quantity * bom.quantity_needed as total_quantity,
        be.total_quantity * bom.quantity_needed * bom.unit_cost as extended_cost,
        be.level + 1,
        be.path || ' -> ' || bom.name
    FROM bill_of_materials bom
    JOIN bom_explosion be ON bom.parent_component_id = be.component_id
)
SELECT 
    component_id,
    name,
    component_type,
    total_quantity,
    unit_cost,
    extended_cost,
    level,
    path
FROM bom_explosion
ORDER BY level, name;

## Performance Considerations

### 1. Add Indexes for Better Performance

-- Index on foreign key columns for faster joins
CREATE INDEX idx_employees_manager_id ON employees(manager_id);
CREATE INDEX idx_categories_parent_id ON categories(parent_id);
CREATE INDEX idx_file_system_parent_id ON file_system(parent_id);

-- Composite indexes for common query patterns
CREATE INDEX idx_employees_manager_dept ON employees(manager_id, department);
CREATE INDEX idx_categories_parent_name ON categories(parent_id, name);

### 2. Limit Recursion Depth

-- Prevent infinite recursion by limiting depth
WITH RECURSIVE deep_hierarchy AS (
    SELECT employee_id, name, manager_id, 0 as level
    FROM employees 
    WHERE manager_id IS NULL
    
    UNION ALL
    
    SELECT e.employee_id, e.name, e.manager_id, dh.level + 1
    FROM employees e
    JOIN deep_hierarchy dh ON e.manager_id = dh.employee_id
    WHERE dh.level < 10  -- Prevent infinite recursion
)
SELECT * FROM deep_hierarchy;

### 3. Use Materialized Views for Complex Hierarchies

-- Create materialized view for frequently accessed hierarchy data
CREATE MATERIALIZED VIEW employee_hierarchy_mv AS
WITH RECURSIVE emp_tree AS (
    SELECT 
        employee_id,
        name,
        manager_id,
        department,
        0 as level,
        ARRAY[employee_id] as path_ids,
        name as path_names
    FROM employees 
    WHERE manager_id IS NULL
    
    UNION ALL
    
    SELECT 
        e.employee_id,
        e.name,
        e.manager_id,
        e.department,
        et.level + 1,
        et.path_ids || e.employee_id,
        et.path_names || ' -> ' || e.name
    FROM employees e
    JOIN emp_tree et ON e.manager_id = et.employee_id
)
SELECT * FROM emp_tree;

-- Create index on materialized view
CREATE INDEX idx_emp_hierarchy_mv_level ON employee_hierarchy_mv(level);
CREATE INDEX idx_emp_hierarchy_mv_dept ON employee_hierarchy_mv(department);

-- Refresh materialized view when data changes
-- REFRESH MATERIALIZED VIEW employee_hierarchy_mv;

## Best Practices

### 1. Always Include Cycle Detection

-- Prevent infinite loops by detecting cycles
WITH RECURSIVE safe_hierarchy AS (
    SELECT 
        employee_id,
        name,
        manager_id,
        ARRAY[employee_id] as visited_ids,
        0 as level
    FROM employees 
    WHERE manager_id IS NULL
    
    UNION ALL
    
    SELECT 
        e.employee_id,
        e.name,
        e.manager_id,
        sh.visited_ids || e.employee_id,
        sh.level + 1
    FROM employees e
    JOIN safe_hierarchy sh ON e.manager_id = sh.employee_id
    WHERE e.employee_id != ALL(sh.visited_ids)  -- Cycle detection
      AND sh.level < 20  -- Additional safety limit
)
SELECT * FROM safe_hierarchy;

### 2. Use Appropriate Data Types

-- Use appropriate data types for better performance
ALTER TABLE employees 
ADD COLUMN path_materialized TEXT,
ADD COLUMN level_in_hierarchy INTEGER;

-- Pre-calculate hierarchy information for read-heavy workloads
UPDATE employees SET 
    level_in_hierarchy = subquery.level,
    path_materialized = subquery.path_names
FROM (
    WITH RECURSIVE emp_levels AS (
        SELECT employee_id, 0 as level, name as path_names
        FROM employees WHERE manager_id IS NULL
        
        UNION ALL
        
        SELECT e.employee_id, el.level + 1, el.path_names || ' -> ' || e.name
        FROM employees e
        JOIN emp_levels el ON e.manager_id = el.employee_id
    )
    SELECT * FROM emp_levels
) subquery
WHERE employees.employee_id = subquery.employee_id;

### 3. Consider Alternative Approaches for Large Datasets

For very large hierarchical datasets, consider these alternatives:

1. **Nested Set Model**: Pre-calculate left and right values
2. **Path Enumeration**: Store the complete path as a string or array
3. **Closure Table**: Maintain a separate table with all ancestor-descendant relationships

-- Example: Closure table approach
CREATE TABLE employee_closure (
    ancestor_id INTEGER REFERENCES employees(employee_id),
    descendant_id INTEGER REFERENCES employees(employee_id),
    depth INTEGER,
    PRIMARY KEY (ancestor_id, descendant_id)
);

-- Populate closure table (would be maintained by triggers in production)
WITH RECURSIVE emp_closure AS (
    -- Direct relationships (depth 0 - self)
    SELECT employee_id as ancestor_id, employee_id as descendant_id, 0 as depth
    FROM employees
    
    UNION ALL
    
    -- All ancestor-descendant relationships
    SELECT ec.ancestor_id, e.employee_id as descendant_id, ec.depth + 1
    FROM employee_closure ec
    JOIN employees e ON e.manager_id = ec.descendant_id
)
INSERT INTO employee_closure 
SELECT * FROM emp_closure;

## Conclusion

SQL recursion with PostgreSQL's recursive CTEs is a powerful tool for working with hierarchical data. The key points to remember:

1. **Structure**: Always have a base case (anchor) and recursive case
2. **Performance**: Add appropriate indexes and consider materialized views
3. **Safety**: Include cycle detection and depth limits
4. **Flexibility**: Recursive CTEs work for both top-down and bottom-up traversals
5. **Real-world applications**: Organizational charts, category trees, file systems, bill of materials, and more

Practice with these examples and adapt them to your specific use cases. Remember that while recursive CTEs are powerful, they may not always be the most efficient solution for very large datasets, where alternative approaches like closure tables might be more appropriate.