再帰SQL - 階層構造における子孫のカウント数

Question

は、次の列をデータベーステーブルを考えてみましょう：

• が
• 名
• advisor1
• advisor2

mathematician_idデータベースを表しMath Genealogy Projectのデータです。各数学者には通常1人のアドバイザーがいますが、イオンは2人の顧問がいるとき。

物事を明確にするには、Visual援助：

私は数学の各子孫の数をカウントするにはどうすればよいですか？

おそらくCommon Table Expressions（WITH RECURSIVE）を使用する必要がありますが、私は現時点ではかなり固執しています。私が見つけた同様の例はすべて、2つではなく1つの親しか持たない階層を扱っています。

更新：

私はまた、PostgreSQLでは動作するようにVladimir Baranovが提供するSQL Server用のソリューションを適応：

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 

Answer 1

あなたが使用DBMS何も言いませんでした。この例ではSQL Serverを使用しますが、再帰クエリもサポートする他のデータベースでも機能します。

サンプル・データ

私はオイラーから始まる、あなたの木の唯一の右の部分に入りました。

最も興味深い部分は、LagrangeとDirichletの間の複数のパスです。

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); 

これは次のように、それがどのように見えるかです：それは2つの、興味深い点を持つ古典的な再帰クエリです

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）子孫への複数のパスを有することが可能であるので、再帰クエリ月出力ノード数回。これらの重複を排除するために、CTE_Distinctに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は、子孫としてノード自身をカウントします。葉ノードに対して1ではなく0を表示する場合は、この結果から1を引くことができます。

ここはSQL Fiddleです。