代码之家 › 专栏 › 技术社区 › Tudor Ciotlos

递归SQL-计算层次结构中的子体数

hierarchical-data common-table-expression recursion postgresql sql

Tudor Ciotlos · 技术社区 · 9 年前

考虑具有以下列的数据库表:

数学家id
名称
建议1
建议2

数据库表示来自 Math Genealogy Project ,其中每个数学家通常有一个顾问,但有时有两个顾问。

视觉帮助使事情更清晰:

如何计算每个数学家的后代数量?

我可能应该使用通用表表达式( 使用递归 ),但我现在很困。我发现的所有类似例子都涉及只有一个父级而不是两个父级的层次结构。

更新:

我调整了由提供的SQL Server解决方案 Vladimir Baranov 也可以使用PostgreSQL:

WITH RECURSIVE cte AS (
    SELECT m.id as start_id,
        m.id,
        m.name,
        m.advisor1,
        m.advisor2,
        1 AS level
    FROM public.mathematicians AS m

    UNION ALL

    SELECT cte.start_id,
        m.id,
        m.name,
        m.advisor1,
        m.advisor2,
        cte.level + 1 AS level
    FROM public.mathematicians AS m
    INNER JOIN cte ON cte.id = m.advisor1
               OR cte.id = m.advisor2
),
cte_distinct AS (
    SELECT DISTINCT start_id, id 
    FROM cte
)
SELECT cte_distinct.start_id,
    m.name,
    COUNT(*)-1 AS descendants_count
FROM cte_distinct
INNER JOIN public.mathematicians AS m ON m.id = cte_distinct.start_id
GROUP BY cte_distinct.start_id, m.name
ORDER BY cte_distinct.start_id

1 回复 | 直到 7 年前

Vladimir Baranov 9 年前

你没有说你使用什么DBMS。我将在这个示例中使用SQLServer,但它也适用于支持递归查询的其他数据库。

样本数据

我只进入了你树的右边部分,从欧拉开始。

最有趣的部分是拉格朗日和狄利克雷之间的多重路径。

DECLARE @T TABLE (ID int, name nvarchar(50), Advisor1ID int, Advisor2ID int);

INSERT INTO @T (ID, name, Advisor1ID, Advisor2ID) VALUES
(1,  'Euler', NULL, NULL),
(2,  'Lagrange', 1, NULL),
(3,  'Laplace', NULL, NULL),
(4,  'Fourier', 2, NULL),
(5,  'Poisson', 2, 3),
(6,  'Dirichlet', 4, 5),
(7,  'Lipschitz', 6, NULL),
(8,  'Klein', NULL, 7),
(9,  'Lindemann', 8, NULL),
(10, 'Furtwangler', 8, NULL),
(11, 'Hilbert', 9, NULL),
(12, 'Taussky-Todd', 10, NULL);

这就是它的样子:

SELECT * FROM @T;

+----+--------------+------------+------------+
| ID |     name     | Advisor1ID | Advisor2ID |
+----+--------------+------------+------------+
|  1 | Euler        | NULL       | NULL       |
|  2 | Lagrange     | 1          | NULL       |
|  3 | Laplace      | NULL       | NULL       |
|  4 | Fourier      | 2          | NULL       |
|  5 | Poisson      | 2          | 3          |
|  6 | Dirichlet    | 4          | 5          |
|  7 | Lipschitz    | 6          | NULL       |
|  8 | Klein        | NULL       | 7          |
|  9 | Lindemann    | 8          | NULL       |
| 10 | Furtwangler  | 8          | NULL       |
| 11 | Hilbert      | 9          | NULL       |
| 12 | Taussky-Todd | 10         | NULL       |
+----+--------------+------------+------------+

查询

这是一个经典的递归查询,有两个有趣的点。

1) 的递归部分 CTE 使用两种方法连接到定位零件 Advisor1ID 和 Advisor2ID :

        INNER JOIN CTE 
            ON CTE.ID = T.Advisor1ID
            OR CTE.ID = T.Advisor2ID

2) 由于可能有多个路径指向子体,递归查询可能会多次输出节点。为了消除这些重复,我使用了 DISTINCT 在里面 CTE_Distinct 可以更有效地解决该问题。

为了更好地理解查询的工作方式,请分别运行每个CTE并检查中间结果。

WITH
CTE
AS
(
    SELECT
        T.ID AS StartID
        ,T.ID
        ,T.name
        ,T.Advisor1ID
        ,T.Advisor2ID
        ,1 AS Lvl
    FROM @T AS T

    UNION ALL

    SELECT
        CTE.StartID
        ,T.ID
        ,T.name
        ,T.Advisor1ID
        ,T.Advisor2ID
        ,CTE.Lvl + 1 AS Lvl
    FROM
        @T AS T
        INNER JOIN CTE 
            ON CTE.ID = T.Advisor1ID
            OR CTE.ID = T.Advisor2ID
)
,CTE_Distinct
AS
(
    SELECT DISTINCT
        StartID
        ,ID
    FROM CTE
)
SELECT
    CTE_Distinct.StartID
    ,T.name
    ,COUNT(*) AS DescendantCount
FROM
    CTE_Distinct
    INNER JOIN @T AS T ON T.ID = CTE_Distinct.StartID
GROUP BY
    CTE_Distinct.StartID
    ,T.name
ORDER BY CTE_Distinct.StartID;

后果

+---------+--------------+-----------------+
| StartID |     name     | DescendantCount |
+---------+--------------+-----------------+
|       1 | Euler        |              11 |
|       2 | Lagrange     |              10 |
|       3 | Laplace      |               9 |
|       4 | Fourier      |               8 |
|       5 | Poisson      |               8 |
|       6 | Dirichlet    |               7 |
|       7 | Lipschitz    |               6 |
|       8 | Klein        |               5 |
|       9 | Lindemann    |               2 |
|      10 | Furtwangler  |               2 |
|      11 | Hilbert      |               1 |
|      12 | Taussky-Todd |               1 |
+---------+--------------+-----------------+

在这里 DescendantCount 将节点本身计数为后代。如果希望叶节点的值为0而不是1,则可以从该结果中减去1。

这里是 SQL Fiddle .