SQL 2005 - Common Table Expression - Find last in hierarchy

Question

Let's say I've got the following table:

CREATE TABLE Employees
(
EmployeeId int PRIMARY KEY NOT NULL,
ParentEmployeId int REFERENCES Employees(EmployeeId) NULL,
Name varChar(255)
)

All records have a primary identifier and records are able to identify another record as a parent. (My actual schema isn't about employees, this is just a simplified version for illustration so if you've got a better way of handling employee information its not germane to this conversation.)

The following records are inserted:

INSERT INTO Employees VALUES (1, NULL, 'Company President 1')
INSERT INTO Employees VALUES (2, NULL, 'Company President 2')

INSERT INTO Employees VALUES (3, 1, 'Company President 1 - VP')
INSERT INTO Employees VALUES (4, 2, 'Company President 2 - VP')

INSERT INTO Employees VALUES (5, 3, 'Company President 1 - VP - Secretary')
INSERT INTO Employees VALUES (6, 4, 'Company President 2 - VP - Secretary')

INSERT INTO Employees VALUES (7, 5, 'Company President 1 - VP - Secretary - Sandwich Delivery')

These inserts represent:

Company President 1
    Company President 1 - VP
        Company President 1 - VP - Secretary
            Company President 1 - VP - Secretary - Sandwich Delivery
Company President 2
    Company President 2 - VP
        Company President 2 - VP - Secretary

What I'm trying to do is for all employees that have a NULL ParentEmployeeId I want to find the last person in the chain, which in this example would be "Company President 1 - VP - Secretary - Sandwich Delivery" and "Company President 2 - VP - Secretary".

I've got the following CTE which gives me everything including the nesting level but I'm not sure where to go from here. I'd like to avoid cursors if possible.

Also, and this is very important, I have logic elsewhere that guarantees that an employee can only have 1 direct subordinate. So although the schema technically allows for it, Company President 1 will never have two VP's listed.

WITH EmployeeRec(EmployeeId, ParentEmployeeId, Name, Level) AS
(
    SELECT
        EmployeeId,
        ParentEmployeId,
        Name,
        1 as [Level]
    FROM
        Employees
    WHERE
        ParentEmployeId IS NULL

    UNION ALL

    SELECT
        E.EmployeeId,
        E.ParentEmployeId,
        E.Name,
        R.[Level] + 1
    FROM
        Employees E
    INNER JOIN
        EmployeeRec R
    ON
        E.ParentEmployeId = R.EmployeeId
)
SELECT * FROM EmployeeRec

In case anyone is ever interest, here's a mySQL version of this, specifically targeting MariaDB 10.2: https://cjhaas.com/2019/10/25/mysql-recursive-cte/ — Chris Haas, Oct 25 '19 at 09:34

score 6 · Accepted Answer · edited Nov 17 '10 at 18:24

6

Keeping track of your master EmployeeID allows you to join the results with the last level to retain the records you need.

WITH EmployeeRec(Master, EmployeeId, ParentEmployeeId, Name, Level) AS
(
    SELECT
        [Master] = EmployeeId,
        EmployeeId,
        ParentEmployeId,
        Name,
        1 as [Level]
    FROM
        Employees
    WHERE
        ParentEmployeId IS NULL

    UNION ALL

    SELECT
        R.Master,
        E.EmployeeId,
        E.ParentEmployeId,
        E.Name,
        R.[Level] + 1
    FROM
        Employees E
    INNER JOIN
        EmployeeRec R
    ON
        E.ParentEmployeId = R.EmployeeId
)
SELECT  *
FROM    EmployeeRec er
        INNER JOIN (
          SELECT  Master, Level = MAX(Level)
          FROM    EmployeeRec
          GROUP BY Master
        ) m ON m.Master = er.Master
               AND m.Level = er.Level

edited Nov 17 '10 at 18:24

AakashM

62,551
17
151
186

answered Nov 17 '10 at 18:18

Lieven Keersmaekers

57,207
13
112
146

Fixed your syntax and +1 because I think your self-join of `EmployeeRec` is more elegant than my intermediate resultset :) – AakashM Nov 17 '10 at 18:24
@AakashM, thanks, I've missed that. In my defence, I'm writing this without access to a SQL Server instance. – Lieven Keersmaekers Nov 17 '10 at 18:25
... and I returned the favor :) – Lieven Keersmaekers Nov 17 '10 at 18:26

score 3 · Answer 2 · answered Nov 17 '10 at 18:17

The key here is to keep track of the top-level parent in the recursive CTE:

;WITH EmployeeRec(
   EmployeeId, ParentEmployeeId, UltimateGrandbossEmployeeId, Name, Level)
 AS
(
    SELECT
        EmployeeId,
        ParentEmployeeId,
        EmployeeId UltimateGrandbossEmployeeId,
        Name,
        1 as [Level]
    FROM
        Employees
    WHERE
        ParentEmployeeId IS NULL

    UNION ALL

    SELECT
        E.EmployeeId,
        E.ParentEmployeeId,
        R.UltimateGrandbossEmployeeId,
        E.Name,
        R.[Level] + 1
    FROM
        Employees E
    INNER JOIN
        EmployeeRec R
    ON
        E.ParentEmployeeId = R.EmployeeId
)

... form an intermediate CTE to capture the 'bottom up' level ...

SELECT 
    UltimateGrandbossEmployeeId,
    Name,
    ROW_NUMBER() OVER (PARTITION BY UltimateGrandbossEmployeeId 
                       ORDER BY Level Desc ) BottomUp
 FROM EmployeeRec
)

... for each ultimate grandboss, select their deepest child:

SELECT
    UltimateGrandbossEmployeeId, DeepestChildName
FROM
    Inter
WHERE
    BottomUp = 1

(concatenate together all these code fragments to form a single query with two CTEs and a SELECT)

Results:

1   Company President 1 - VP - Secretary - Sandwich Delivery
2   Company President 2 - VP - Secretary

You can JOIN this back to Employee to get ultiamte grandboss names or track the names in the CTE, as makes sense in your actual situation.

SQL 2005 - Common Table Expression - Find last in hierarchy

2 Answers2