CODEWITHSUNDEEP
sql
jay
jay

Reputation: 1524

Generating a hierarchy

I got the following question at a job interview and it completely stumped me, so I'm wondering if anybody out there can help explain it to me. Say I have the following table:

employees
--------------------------
id | name     | reportsTo
--------------------------
 1 | Alex     | 2
 2 | Bob      | NULL
 3 | Charlie  | 5
 4 | David    | 2
 5 | Edward   | 8
 6 | Frank    | 2
 7 | Gary     | 8
 8 | Harry    | 2
 9 | Ian      | 8

The question was to write a SQL query that returned a table with a column for each employee's name and a column showing how many people are above that employee in the organization: i.e.,

hierarchy
--------------------------
name     | hierarchyLevel
--------------------------
Alex     | 1
Bob      | 0
Charlie  | 3
David    | 1
Edward   | 2
Frank    | 1
Gary     | 2
Harry    | 1
Ian      | 2

I can't even figure out where to begin writing this as a SQL query (a cursor, maybe?). Can anyone help me out in case I get asked a similar question to this again? Thanks.

Upvotes: 2

Views: 103

Answers (1)

lc.
lc.

Reputation: 116498

The simplest example would be to use a (real or temporary) table, and add one level at a time (fiddle):

INSERT INTO hierarchy
SELECT id, name, 0
FROM employees
WHERE reportsTo IS NULL;

WHILE ((SELECT COUNT(1) FROM employees) <> (SELECT COUNT(1) FROM hierarchy))
BEGIN
    INSERT INTO hierarchy
    SELECT e.id, e.name, h.hierarchylevel + 1
    FROM employees e
    INNER JOIN hierarchy h ON e.reportsTo = h.id
    AND NOT EXISTS(SELECT 1 FROM hierarchy hh WHERE hh.id = e.id)
END

Other solutions will be slightly different for each RDBMS. As one example, in SQL Server, you can use a recursive CTE to expand it (fiddle):

;WITH expanded AS
(
    SELECT id, name, 0 AS level
    FROM employees
    WHERE reportsTo IS NULL
    UNION ALL
    SELECT e.id, e.name, level + 1 AS level
    FROM expanded x
    INNER JOIN employees e ON e.reportsTo = x.id
)
SELECT * 
FROM expanded
ORDER BY id

Other solutions include recursive stored procedures, or even using dynamic SQL to iteratively increase the number of joins until everybody is accounted for.

Of course all these examples assume there are no cycles and everyone can be traced up the chain to a head honcho (reportsTo = NULL).

Upvotes: 2

Related Questions