sql - 生成层次结构

Question

我在面试时遇到了以下问题，它完全难住了我，所以我想知道是否有人可以帮我解释一下。假设我有下表:

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

问题是编写一个 SQL 查询，返回一个表，其中有一列表示每个员工的姓名，一列显示组织中有多少人高于该员工:即

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

我什至不知道从哪里开始将其编写为 SQL 查询(也许是游标？)。如果我再次被问到类似的问题，有人可以帮助我吗？谢谢。

Answer 1

最简单的示例是使用(真实或临时)表，并一次添加一个级别 ( 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

对于每个 RDBMS，其他解决方案会略有不同。作为一个示例，在 SQL Server 中，您可以使用递归 CTE 来扩展它 ( 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

其他解决方案包括递归存储过程，甚至使用动态 SQL 来迭代地增加连接数量，直到每个人都被考虑在内。

当然，所有这些示例都假设没有循环，并且每个人都可以沿着链条追溯到头目(reportsTo = NULL)。