Recursive CTE Example: Path Enumeration in a Graph

Path enumeration in a graph can be accomplished using recursive Common Table Expressions (CTEs) in SQL. Path enumeration involves finding all possible paths between nodes in a graph. Here’s how you can do it with SQL:

Table Structure

Assume you have a table edges representing the edges of the graph:

sql
CREATE TABLE edges (
    start_node INT,
    end_node INT
);

Sample Data

Here’s some sample data for the edges table:

sql
INSERT INTO edges (start_node, end_node) VALUES
(1, 2),
(1, 3),
(2, 4),
(3, 4),
(4, 5),
(2, 5),
(3, 5);

SQL Query to Enumerate All Paths

To enumerate all paths between nodes using a recursive CTE, you can use the following SQL query. This query will find all possible paths starting from a given node, say 1.

sql
WITH RECURSIVE PathCTE AS (
    -- Anchor member: start with the initial node
    SELECT 
        start_node AS path_start,
        end_node AS path_end,
        CAST(start_node AS VARCHAR(100)) || '->' || CAST(end_node AS VARCHAR(100)) AS path,
        1 AS depth
    FROM 
        edges
    WHERE 
        start_node = 1

    UNION ALL

    -- Recursive member: find the next nodes in the path
    SELECT 
        p.path_start,
        e.end_node AS path_end,
        p.path || '->' || CAST(e.end_node AS VARCHAR(100)) AS path,
        p.depth + 1
    FROM 
        PathCTE p
    INNER JOIN 
        edges e ON p.path_end = e.start_node
)
SELECT 
    path,
    depth
FROM 
    PathCTE
ORDER BY 
    depth, path;

Explanation

1. Anchor Member:

   sql
   SELECT 
       start_node AS path_start,
       end_node AS path_end,
       CAST(start_node AS VARCHAR(100)) || '->' || CAST(end_node AS VARCHAR(100)) AS path,
       1 AS depth
   FROM 
       edges
   WHERE 
       start_node = 1

   This initializes the CTE with paths starting from the initial node (in this case, node 1). The CAST functions are used to concatenate the nodes into a path string.

2. Recursive Member:

   sql
   SELECT 
       p.path_start,
       e.end_node AS path_end,
       p.path || '->' || CAST(e.end_node AS VARCHAR(100)) AS path,
       p.depth + 1
   FROM 
       PathCTE p
   INNER JOIN 
       edges e ON p.path_end = e.start_node

   This part of the CTE extends the paths by joining the current path’s end node with the start node of the next edge. It concatenates the next node to the path string and increments the depth.

3. Final Select:

   sql
   SELECT 
       path,
       depth
   FROM 
       PathCTE
   ORDER BY 
       depth, path;

   This selects and orders the paths by depth and then by the path string.

Result

The result will be a table listing all possible paths starting from node 1, along with their respective depths:

 path             | depth
------------------|-------
 1->2             |     1
 1->3             |     1
 1->2->4          |     2
 1->2->5          |     2
 1->3->4          |     2
 1->3->5          |     2
 1->2->4->5       |     3
 1->3->4->5       |     3

Recursive CTE Example: Fibonacci Sequence

Using a recursive Common Table Expression (CTE) to generate a Fibonacci sequence in SQL is a great exercise for understanding how recursion works in SQL. Below is a detailed example that shows how to create a CTE to generate the first n numbers in the Fibonacci sequence.

Fibonacci Sequence with Recursive CTE

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1. The sequence typically starts as 0, 1, 1, 2, 3, 5, 8, and so on.

SQL Query to Generate Fibonacci Sequence

Here’s how you can write a SQL query to generate the Fibonacci sequence using a recursive CTE:

sql
WITH RECURSIVE FibonacciCTE AS (
    -- Anchor members: start with the first two numbers in the sequence
    SELECT 
        0 AS position,
        0 AS fibonacci
    UNION ALL
    SELECT 
        1,
        1
    UNION ALL
    -- Recursive member: generate the next number in the sequence
    SELECT 
        position + 1 AS position,
        f1.fibonacci + f2.fibonacci AS fibonacci
    FROM 
        FibonacciCTE f1
    INNER JOIN 
        FibonacciCTE f2 ON f1.position + 1 = f2.position
    WHERE 
        f1.position < 20 -- Set the limit to avoid infinite recursion
)
SELECT 
    position, 
    fibonacci
FROM 
    FibonacciCTE
ORDER BY 
    position;

Explanation

1. Anchor Members:

   sql
   SELECT 
       0 AS position,
       0 AS fibonacci
   UNION ALL
   SELECT 
       1,
       1

   These two queries initialize the sequence with the first two numbers: 0 and 1.

2. Recursive Member:

   sql
   SELECT 
       position + 1 AS position,
       f1.fibonacci + f2.fibonacci AS fibonacci
   FROM 
       FibonacciCTE f1
   INNER JOIN 
       FibonacciCTE f2 ON f1.position + 1 = f2.position
   WHERE 
       f1.position < 20 -- Set the limit to avoid infinite recursion

   This part of the CTE generates the next number in the sequence by summing the two preceding numbers. It uses a self-join on the CTE to get the preceding two numbers. The WHERE clause ensures that the recursion stops after generating 20 numbers.

3. Final Select:

   sql
   SELECT 
       position, 
       fibonacci
   FROM 
       FibonacciCTE
   ORDER BY 
       position;

   This selects and orders the results by the position in the sequence.

Adjusting the Limit

To generate more numbers in the Fibonacci sequence, simply adjust the limit in the WHERE clause. For example, to generate the first 30 numbers, change f1.position < 20 to f1.position < 30.

Result

The result will be a table listing the positions and the corresponding Fibonacci numbers:

 position | fibonacci
----------|-----------
        0 | 0
        1 | 1
        2 | 1
        3 | 2
        4 | 3
        5 | 5
        6 | 8
        7 | 13
        8 | 21
        9 | 34
       10 | 55
       11 | 89
       12 | 144
       13 | 233
       14 | 377
       15 | 610
       16 | 987
       17 | 1597
       18 | 2584
       19 | 4181
       20 | 6765

In this example, the Fibonacci sequence starts from position 0 and generates up to position 20. The query can be adjusted to generate as many numbers in the sequence as needed.

Recursive CTE Example: organization chart with depth

Creating an organization chart with depth using a recursive Common Table Expression (CTE) is a practical way to manage and visualize hierarchical data. Here’s how you can achieve this in SQL:

Table Structure

Let's assume you have an employees table structured as follows:

sql
CREATE TABLE employees (
    employee_id INT PRIMARY KEY,
    employee_name VARCHAR(100),
    manager_id INT
);

Sample Data

Here’s some sample data for this table:

sql
INSERT INTO employees (employee_id, employee_name, manager_id) VALUES
(1, 'Alice', NULL),
(2, 'Bob', 1),
(3, 'Charlie', 1),
(4, 'David', 2),
(5, 'Eve', 2),
(6, 'Frank', 3);

SQL Query to Retrieve Organization Chart with Depth

To construct an organization chart with depth, we’ll use a recursive CTE. The depth indicates the level of each employee in the hierarchy, with the top-level manager having a depth of 1.

sql
WITH RECURSIVE OrgChart AS (
    -- Anchor member: start with the top-level manager
    SELECT 
        employee_id,
        employee_name,
        manager_id,
        1 AS depth
    FROM 
        employees
    WHERE 
        manager_id IS NULL

    UNION ALL

    -- Recursive member: find employees who report to the current employee
    SELECT 
        e.employee_id,
        e.employee_name,
        e.manager_id,
        oc.depth + 1 AS depth
    FROM 
        employees e
    INNER JOIN 
        OrgChart oc ON e.manager_id = oc.employee_id
)
SELECT 
    employee_id,
    employee_name,
    manager_id,
    depth
FROM 
    OrgChart
ORDER BY 
    depth, employee_id;

Explanation

1. Anchor Member:

   sql
   SELECT 
       employee_id,
       employee_name,
       manager_id,
       1 AS depth
   FROM 
       employees
   WHERE 
       manager_id IS NULL

   This initializes the CTE with the top-level manager(s) who have no manager (i.e., manager_id IS NULL). The depth is set to 1 for these managers.

2. Recursive Member:

   sql
   SELECT 
       e.employee_id,
       e.employee_name,
       e.manager_id,
       oc.depth + 1 AS depth
   FROM 
       employees e
   INNER JOIN 
       OrgChart oc ON e.manager_id = oc.employee_id

   This part of the CTE finds employees who report to the current employees in the CTE and increments their depth by 1.

3. Final Select:

   sql
   SELECT 
       employee_id,
       employee_name,
       manager_id,
       depth
   FROM 
       OrgChart
   ORDER BY 
       depth, employee_id;

   This selects and orders the results by depth and then by employee ID.

Result

The result will be a table listing each employee with their respective depth in the organizational hierarchy:

 employee_id | employee_name| manager_id | depth
-------------|--------------|------------|-------
           1 | Alice        | NULL       |     1
           2 | Bob          | 1          |     2
           3 | Charlie      | 1          |     2
           4 | David        | 2          |     3
           5 | Eve          | 2          |     3
           6 | Frank        | 3          |     3

In this example:

• Alice is at the top level (depth 1).
• Bob and Charlie report to Alice, so they are at depth 2.
• David, Eve, and Frank report to Bob and Charlie, so they are at depth 3.

This query effectively constructs the organizational chart, showing each employee’s position in the hierarchy along with their depth.

Recursive CTE Example: Directory Structure

Managing and querying directory structures in SQL can be effectively accomplished using recursive Common Table Expressions (CTEs). Below is a detailed example that demonstrates how to use a recursive CTE to retrieve the full path of each directory in a hierarchical structure.

Directory Table Structure

Suppose we have a directories table with the following schema:

sql
CREATE TABLE directories (
    directory_id INT PRIMARY KEY,
    directory_name VARCHAR(100),
    parent_directory_id INT
);

Sample Data

Here's some sample data to work with:

sql
INSERT INTO directories (directory_id, directory_name, parent_directory_id) VALUES
(1, 'root', NULL),
(2, 'home', 1),
(3, 'user', 2),
(4, 'documents', 3),
(5, 'photos', 3),
(6, 'work', 1);

SQL Query to Retrieve Full Directory Paths

We want to construct a query to retrieve the full path for each directory. Here’s how to do it using a recursive CTE:

sql
WITH RECURSIVE DirectoryPaths AS (
    -- Anchor member: start with root directory
    SELECT 
        directory_id,
        directory_name,
        parent_directory_id,
        directory_name AS full_path
    FROM 
        directories
    WHERE 
        parent_directory_id IS NULL

    UNION ALL

    -- Recursive member: append current directory to its parent's path
    SELECT 
        d.directory_id,
        d.directory_name,
        d.parent_directory_id,
        CONCAT(dp.full_path, '/', d.directory_name) AS full_path
    FROM 
        directories d
    INNER JOIN 
        DirectoryPaths dp ON d.parent_directory_id = dp.directory_id
)
SELECT 
    directory_id,
    directory_name,
    parent_directory_id,
    full_path
FROM 
    DirectoryPaths
ORDER BY 
    full_path;

Explanation

1. Anchor Member:

   sql
   SELECT 
       directory_id,
       directory_name,
       parent_directory_id,
       directory_name AS full_path
   FROM 
       directories
   WHERE 
       parent_directory_id IS NULL
   
   

   This initializes the CTE with the root directory.

2. Recursive Member:

   sql
   SELECT 
       d.directory_id,
       d.directory_name,
       d.parent_directory_id,
       CONCAT(dp.full_path, '/', d.directory_name) AS full_path
   FROM 
       directories d
   INNER JOIN 
       DirectoryPaths dp ON d.parent_directory_id = dp.directory_id
   
   

   This part of the CTE appends each directory to its parent’s full path. It joins the directories table with the DirectoryPaths CTE on the parent_directory_id to build the full path.

3. Final Select:

   sql
   SELECT 
       directory_id,
       directory_name,
       parent_directory_id,
       full_path
   FROM 
       DirectoryPaths
   ORDER BY 
       full_path;

   This selects and orders the results by the full path.

Result

The result will be a table listing each directory with its full path:

 directory_id | directory_name | parent_directory_id |      full_path      
--------------|----------------|---------------------|---------------------
            1 | root           |                NULL | root
            2 | home           |                   1 | root/home
            3 | user           |                   2 | root/home/user
            4 | documents      |                   3 | root/home/user/documents
            5 | photos         |                   3 | root/home/user/photos
            6 | work           |                   1 | root/work

This query effectively builds the full directory paths by leveraging the power of recursive CTEs, making it easier to manage and query hierarchical data in SQL.

Recursive CTE Example: Hierarchy of Employees

 Finding the Hierarchy of Employees

Imagine you have an employees table with the following structure:

sql
CREATE TABLE employees (
    employee_id INT PRIMARY KEY,
    employee_name VARCHAR(100),
    manager_id INT
);

Here's a sample dataset:

sql
INSERT INTO employees (employee_id, employee_name, manager_id) VALUES
(1, 'Alice', NULL),
(2, 'Bob', 1),
(3, 'Charlie', 1),
(4, 'David', 2),
(5, 'Eve', 2),
(6, 'Frank', 3);

You want to find the hierarchy of all employees starting from a specific manager (say, Alice).

sql
WITH RECURSIVE EmployeeHierarchy AS (
    -- Anchor member: start with the root manager
    SELECT 
        employee_id,
        employee_name,
        manager_id,
        1 AS level
    FROM 
        employees
    WHERE 
        employee_name = 'Alice'

    UNION ALL

    -- Recursive member: find employees who report to the current employee
    SELECT 
        e.employee_id,
        e.employee_name,
        e.manager_id,
        eh.level + 1
    FROM 
        employees e
    INNER JOIN 
        EmployeeHierarchy eh ON e.manager_id = eh.employee_id
)
SELECT 
    employee_id,
    employee_name,
    manager_id,
    level
FROM 
    EmployeeHierarchy
ORDER BY 
    level, employee_id;

Recursive CTE Example: calculate the factorial of a number

Calculating the factorial of a number using a recursive CTE in SQL can be both an instructive and practical example. Here’s a detailed step-by-step guide to achieve this.

Step-by-Step Explanation

1. Anchor Member: The base case of the recursion. For the factorial calculation, the base case is 0! = 1 or 1! = 1.
2. Recursive Member: Defines the recursive step. For the factorial of n, we have n! = n * (n-1)!.

Here's the SQL code to calculate the factorial of a number (let's say 5):

SQL Code

sql
WITH RECURSIVE FactorialCTE AS (
    -- Anchor member: start with 1
    SELECT 
        1 AS n, 
        1 AS factorial
    UNION ALL
    -- Recursive member: calculate factorial for n + 1
    SELECT 
        n + 1,
        factorial * (n + 1)
    FROM 
        FactorialCTE
    WHERE 
        n < 5 --Set the Dynamic limit to the desired number, in this case, 5
)
SELECT 
    n, 
    factorial
FROM 
    FactorialCTE
ORDER BY 
    n;

Explanation

1. Anchor Member:

   sql
   SELECT 
       1 AS n, 
       1 AS factorial
   This initializes the recursion with 1! = 1.

2. Recursive Member:

   sql
   SELECT 
       n + 1,
       factorial * (n + 1)
   FROM 
       FactorialCTE
   WHERE 
       n < 5
   
   

   This part of the CTE calculates the factorial by multiplying the current value of factorial by n + 1 until n reaches 5.

3. Final Select:

   sql
   SELECT 
       n, 
       factorial
   FROM 
       FactorialCTE
   ORDER BY 
       n;
   
   

   This selects and orders the results by n.

Result

The result will be a table listing each n from 1 to 5 and the corresponding factorial value:

 n | factorial
---|-----------
 1 | 1
 2 | 2
 3 | 6
 4 | 24
 5 | 120

Recursive Common Table Expressions (CTEs)

 Recursive Common Table Expressions (CTEs) are a powerful feature in T-SQL that allow for the creation of complex queries involving hierarchical or recursive data. They are particularly useful for querying data that has a parent-child relationship, such as organizational structures, family trees, or graph data.

Key Concepts of Recursive CTEs

1. CTE Structure: A CTE is defined using the WITH keyword followed by a query that generates the initial result set (the anchor member) and a recursive query (the recursive member) that references the CTE itself.

2. Anchor Member: This is the initial query that forms the base result set. It usually selects the starting point of the recursion.

3. Recursive Member: This part of the CTE references the CTE name and performs the recursive operation. It usually joins the result of the previous iteration with other tables to produce the next level of results.

4. Termination Condition: The recursion terminates when the recursive member does not produce any more rows.

5. MAXRECURSION Option: SQL Server limits the number of recursive calls to 100 by default to prevent infinite loops. This limit can be changed using the OPTION (MAXRECURSION n) clause.

Example of a Recursive CTE

Fibonacci Sequence
organization chart with depth
Directory Structure
Hierarchy of Employees
Calculate the factorial of a number
Path Enumeration in a Graph

Here is an example that demonstrates how to use a recursive CTE to traverse an organizational hierarchy:

sql
WITH EmployeeHierarchy AS (
    -- Anchor member: Select the top-level employees
    SELECT 
        EmployeeID,
        FirstName,
        LastName,
        ManagerID,
        0 AS Level
    FROM Employees
    WHERE ManagerID IS NULL

    UNION ALL

    -- Recursive member: Join with the CTE to find subordinates
    SELECT 
        e.EmployeeID,
        e.FirstName,
        e.LastName,
        e.ManagerID,
        eh.Level + 1
    FROM Employees e
    INNER JOIN EmployeeHierarchy eh ON e.ManagerID = eh.EmployeeID
)
-- Select from the CTE
SELECT 
    EmployeeID,
    FirstName,
    LastName,
    ManagerID,
    Level
FROM EmployeeHierarchy
ORDER BY Level, LastName;

Detailed Explanation

1. Anchor Member:

   sql
   SELECT 
       EmployeeID,
       FirstName,
       LastName,
       ManagerID,
       0 AS Level
   FROM Employees
   WHERE ManagerID IS NULL

2. Recursive Member:

   sql
   SELECT 
       e.EmployeeID,
       e.FirstName,
       e.LastName,
       e.ManagerID,
       eh.Level + 1
   FROM Employees e
   INNER JOIN EmployeeHierarchy eh ON e.ManagerID = eh.EmployeeID

3. Termination Condition: The recursion stops when there are no more employees to process (no more rows returned by the recursive member).

4. Final Query:

   sql
   SELECT 
       EmployeeID,
       FirstName,
       LastName,
       ManagerID,
       Level
   FROM EmployeeHierarchy
   ORDER BY Level, LastName;

Use Cases

1. Hierarchical Data: Ideal for organizational charts, bill of materials, and any data that has a tree-like structure.
2. Graph Data: Useful for querying graph structures like social networks, family trees, and routing algorithms.
3. Recursive Algorithms: Can be used to implement recursive algorithms in SQL, such as calculating factorials or Fibonacci numbers.

Best Practices

1. Limit Recursion: Always use the MAXRECURSION option to prevent infinite loops.
2. Optimize Queries: Ensure that the anchor and recursive members are optimized for performance.
3. Test Thoroughly: Recursive CTEs can be complex; thoroughly test them with various data sets to ensure they work correctly.

Report Localization in SSRS

 Report localization in SQL Server Reporting Services (SSRS) involves translating and formatting reports to support multiple languages and regions. Here are some key steps and strategies for effectively localizing SSRS reports:

1. Resource Files for Localization:

   • Use resource files (.resx) to store localized strings for different languages. You can create separate resource files for each language and reference these in your SSRS reports.
   • Create a base resource file (e.g., ReportStrings.resx) and localized versions (e.g., ReportStrings.fr.resx for French).

2. Expressions for Localized Text:

   • Use expressions to dynamically display localized text in your reports. You can use custom code or embedded code in the report to fetch the localized strings.
   • Add custom code in the Report Properties (Code tab) to load the appropriate resource file based on the user’s language.

   vb
   Public Function GetLocalizedString(key As String, language As String) As String
       Dim rm As New System.Resources.ResourceManager("Namespace.ReportStrings", GetType(ReportName).Assembly)
       Return rm.GetString(key, New System.Globalization.CultureInfo(language))
   End Function

   • Use expressions in your report items to call this function and display the localized text.

   vb
   
   =Code.GetLocalizedString("ReportTitle", Parameters!Language.Value)
   

3. Parameters for Language Selection:

   • Add a parameter to your report to allow users to select their preferred language. This parameter can be used to determine which resource file to load and which culture to apply for formatting.

   sql
   
   @Language (e.g., "en-US", "fr-FR")
   

4. Localized Data:

   • Ensure that any data displayed in the report is also localized. This can involve querying localized data from your database or translating data within the report.

5. Date, Number, and Currency Formatting:

   • Use culture-specific formatting for dates, numbers, and currency values. You can set the format of report items based on the selected language or culture.

   vb
   =Format(Fields!DateField.Value, "d", New System.Globalization.CultureInfo(Parameters!Language.Value))

6. Localized Subreports:

   • If your report contains subreports, ensure that these subreports are also localized. Pass the language parameter to subreports and apply the same localization logic.

7. Multi-Language Report Layouts:

   • For complex reports, consider creating separate layouts for each language. This approach can provide more control over the appearance and placement of localized text.

8. Testing and Validation:

   • Thoroughly test your localized reports in all supported languages. Ensure that text fits properly within report items and that formatting is applied correctly.

Example: Implementing Localization in SSRS

1. Create Resource Files:

   • Create resource files (ReportStrings.resx, ReportStrings.fr.resx, etc.) and add localized strings for each language.

2. Add Language Parameter:

   • Add a report parameter named Language with available language options.

3. Custom Code for Localization:

   • Add the following custom code in the Report Properties (Code tab):

     vb
     Public Function GetLocalizedString(key As String, language As String) As String
         Dim rm As New System.Resources.ResourceManager("Namespace.ReportStrings", GetType(ReportName).Assembly)
         Return rm.GetString(key, New System.Globalization.CultureInfo(language))
     End Function

4. Expressions for Localized Text:

   • Use expressions to display localized text in report items:

     vb
     
     =Code.GetLocalizedString("ReportTitle", Parameters!Language.Value)
     

5. Culture-Specific Formatting:

   • Apply culture-specific formatting for dates, numbers, and currency values:

     vb
     =Format(Fields!DateField.Value, "d", New System.Globalization.CultureInfo(Parameters!Language.Value))

6. Pass Language Parameter to Subreports:

   • If using subreports, pass the language parameter to ensure they are also localized:

     sql
     
     =Parameters!Language.Value
     

By following these steps, you can effectively localize your SSRS reports to support multiple languages and regions, providing a better user experience for a global audience.