Table Recursion Query In SQL Server 2008 R2

Question

I know this is a common "recursive lookup" type of question and there are many on SO, but I can't find an answer that solves my particular problem. It's an issue I need to solve using data that I have inherited from a customer.

Considering the following table example (simplistic version of the actual data):

ancestor_page_id parent_page_id page_id page_name 
---------------- -------------- ------- ---------
NULL             1              3       ROOT A
NULL             3              4       CHILD A
NULL             4              5       SUB CHILD A
NULL             4              6       SUB CHILD B
NULL             5              7       SUB SUB CHILD A
NULL             2              8       ROOT B
NULL             8              9       CHILD B
NULL             9              10      SUB CHILD C
NULL             9              11      SUB CHILD D
NULL             10             12      SUB SUB CHILD B

How do I get it into the form:

ancestor_page_id parent_page_id page_id page_name 
---------------- -------------- ------- ---------
1                1              3       ROOT A
1                3              4       CHILD A
1                4              5       SUB CHILD A
1                4              6       SUB CHILD B
1                5              7       SUB SUB CHILD A
2                2              8       ROOT B
2                8              9       CHILD B
2                9              10      SUB CHILD C
2                9              11      SUB CHILD D
2                10             12      SUB SUB CHILD B

Where the ancestor_page_id is the ancestral parent_page_id value.

I know parent_page_id values 1 and 2 should have records, but they don't exist (there is no FK constraint).

I hope this makes sense. Please help!

Answer 1

Searching through labels will be very expensive without full-text indexing. We don't have to rely on that.

DECLARE @your_table TABLE (
    ancestor_page_id INT NULL
    , parent_page_id INT NOT NULL
    , page_id INT NOT NULL
    , page_name VARCHAR(255) NOT NULL
)

INSERT INTO @your_table (ancestor_page_id, parent_page_id, page_id, page_name)
VALUES  (NULL, 1, 3, 'ROOT A')
    , (NULL, 3, 4, 'CHILD A')
    , (NULL, 4, 5, 'SUB CHILD A')
    , (NULL, 4, 6, 'SUB CHILD B')
    , (NULL, 5, 7, 'SUB SUB CHILD A')
    , (NULL, 2, 8, 'ROOT B')
    , (NULL, 8, 9, 'CHILD B')
    , (NULL, 9, 10, 'SUB CHILD C')
    , (NULL, 9, 11, 'SUB CHILD D')
    , (NULL, 10, 21, 'SUB SUB CHILD B')
;

WITH recursive_cte
AS (
    -- find roots
    SELECT T1.parent_page_id ancestor_page_id, T1.parent_page_id, T1.page_id, T1.page_name
    FROM @your_table T1
        -- look for any records which have no parents, i.e. roots/trunks
        LEFT JOIN @your_table T2 ON T1.parent_page_id = T2.page_id
    WHERE T2.page_id IS NULL

    UNION ALL

    -- now find all children down each branch, passing the root value intact
    SELECT T4.ancestor_page_id, T3.parent_page_id, T3.page_id, T3.page_name
    FROM @your_table T3
        INNER JOIN recursive_cte T4 ON T3.parent_page_id = T4.page_id
)
SELECT *
FROM recursive_cte
ORDER BY page_id ASC

Answer 2

Does this provide the required output?

DECLARE @TABLE TABLE
(
    ancestor_page_id INT NULL,
    parent_page_id INT NOT NULL,
    page_id INT NOT NULL,
    page_name VARCHAR(50) NOT NULL
);
INSERT INTO @TABLE
VALUES
(NULL, 1,  3, 'ROOT A'),
(NULL, 3,  4, 'CHILD A'),
(NULL, 4,  5, 'SUB CHILD A'),
(NULL, 4,  6, 'SUB CHILD B'),
(NULL, 5,  7, 'SUB SUB CHILD A'),
(NULL, 2,  8, 'ROOT B'),
(NULL, 8,  9, 'CHILD B'),
(NULL, 9,  10, 'SUB CHILD C'),
(NULL, 9,  11, 'SUB CHILD D'),
(NULL, 10, 12, 'SUB SUB CHILD B');

WITH CTE(ancestor_page_id, parent_page_id, page_id, page_name)
AS
(
    SELECT
        parent_page_id AS ancestor_page_id, 
        parent_page_id, 
        page_id, 
        page_name
    FROM
        @TABLE 
    WHERE
        page_name LIKE 'ROOT%' -- An assumption for the anchor?

    UNION ALL

    SELECT
        CTE.ancestor_page_id,
        T.parent_page_id, 
        T.page_id, 
        T.page_name     
    FROM
        CTE
        INNER JOIN @TABLE AS T
        ON T.parent_page_id = CTE.page_id    
)

SELECT * FROM CTE
ORDER BY ancestor_page_id, parent_page_id, page_id