SQL 再帰CTE — グラフ探索・RBAC・BOM展開の応用

WITH RECURSIVE paths AS (

  -- ① アンカー部: 出発地 TYO を起点として登録、訪問済み配列を初期化
  SELECT
    'TYO'         AS current_city,
    0             AS total_cost,
    ARRAY['TYO'] AS visited,        -- 訪問済み都市コードの配列
    'TYO'         AS route_str

  UNION ALL

  -- ② 再帰部: 未訪問かつホップ数制限内の次の都市へ移動
  SELECT
    r.to_code,
    p.total_cost + r.cost,
    p.visited || r.to_code,             -- 配列に次の都市を追加（||はPG配列連結演算子）
    p.route_str || '→' || r.to_code
  FROM  paths p
  JOIN  routes r ON r.from_code = p.current_city
  WHERE r.to_code != ALL(p.visited)     -- 循環防止: visitedの全要素と異なる都市のみ
    AND   array_length(p.visited, 1) < 4 -- 最大3フライト: 配列長4（4都市）未満

)
SELECT
  route_str,
  total_cost
FROM  paths
WHERE current_city = 'FUK'  -- 目的地 FUK に到達した経路のみ抽出
ORDER BY total_cost;

/*
  実行順序（SQLの論理的な評価順）:
  1. アンカー部
  2. 再帰1回目（from TYO）
  3. 再帰2回目（from OSA,NGO）
  4. 再帰3回目（from HIR,OSA[NGO経由]）
  5. 再帰4回目
  6. 外側クエリ
  */

WITH RECURSIVE role_chain AS (

  -- ① アンカー部: alice(user_id=1)の直接ロール（editor）を起点に登録
  SELECT
    r.role_id,
    r.role_name,
    r.parent_role_id,
    0 AS chain_level         -- 直接ロール = chain_level 0
  FROM  users u
  JOIN  roles r ON r.role_id = u.role_id
  WHERE u.user_id = 1          -- 対象ユーザー

  UNION ALL

  -- ② 再帰部: 現在のロールの parent_role_id を辿って上位ロールへ遡る
  SELECT
    r.role_id,
    r.role_name,
    r.parent_role_id,
    rc.chain_level + 1        -- 上位ロールになるほど chain_level が増加
  FROM  roles r
  JOIN  role_chain rc ON r.role_id = rc.parent_role_id  -- ← ボトムアップ方向のJOIN

)
SELECT
  p.permission_name,
  rc.role_name  AS granted_by_role,  -- どのロールで付与されたか（監査ログ用途）
  rc.chain_level
FROM  role_chain rc
JOIN  permissions p ON p.role_id = rc.role_id
ORDER BY rc.chain_level, p.permission_name;

/*
  実行順序（SQLの論理的な評価順）:
  1. アンカー部
  2. 再帰1回目
  3. 再帰2回目
  4. 再帰3回目
  5. 外側クエリ
  */

WITH RECURSIVE bom_expand AS (
  -- アンカー: 全部品を「自分自身の直接の起点」として初期化
  SELECT
    p.part_id    AS root_id,        -- コスト集計の起点となる部品
    p.part_id    AS current_id,     -- 現在処理中の部品（展開の先端）
    1            AS accumulated_qty, -- 累積数量（最初は1）
    p.unit_cost                       -- 葉部品の単価（アセンブリはNULL）
  FROM parts p

  UNION ALL

  -- 再帰部: BOMを辿って子部品へ展開、数量を乗算しながら引き継ぐ
  SELECT
    be.root_id,                                                   -- 起点は変えない
    b.child_part_id    AS current_id,                             -- 展開先が新たな先端
    be.accumulated_qty * b.quantity                               -- ★ 数量を乗算で積み上げる
      AS accumulated_qty,
    p.unit_cost
  FROM bom_expand be
  JOIN bom b        ON b.parent_part_id = be.current_id           -- 子部品を結合
  JOIN parts p      ON p.part_id = b.child_part_id                -- 子部品の情報を取得
)
SELECT
  p.part_id,
  p.part_name,
  SUM(be.accumulated_qty * be.unit_cost) AS total_component_cost  -- 葉部品のコスト（累積数量 × 単価）を集計
FROM bom_expand be
JOIN parts p          ON p.part_id = be.root_id
WHERE be.unit_cost IS NOT NULL                                    -- 葉部品行のみ集計対象（アセンブリ行を除外）
GROUP BY p.part_id, p.part_name
ORDER BY p.part_id;

/*
  実行順序:
  1. WITH RECURSIVE bom_expand      → 全部品を自分自身でアンカー化
  2. UNION ALL 再帰部(iter1)           → 直接子を展開
  3. UNION ALL 再帰部(iter2)           → 孫を展開し終了
  4. 外側WHERE unit_cost IS NOT NULL  → 中間アセンブリ行を除外
  5. GROUP BY + SUM                 → root_id 別にコストを合計
  6. JOIN parts + ORDER BY part_id  → 部品名を付加し昇順出力
  */

WITH RECURSIVE
dept_tree AS (                                  -- ① 部門ツリー: 深度とパス文字列を付与しながらトップダウン展開
  SELECT
    dept_id, dept_name, parent_id, own_budget,
    0              AS depth,
    dept_name      AS path                      -- パスの起点はルート部門名
  FROM departments
  WHERE parent_id IS NULL                       -- ルート部門（本社）がアンカー

  UNION ALL

  SELECT
    d.dept_id, d.dept_name, d.parent_id, d.own_budget,
    dt.depth + 1                         AS depth,
    dt.path || ' > ' || d.dept_name    AS path          -- ★ パスを連結
  FROM departments d
  JOIN dept_tree dt ON d.parent_id = dt.dept_id
),
closure AS (                                            -- ② 閉包テーブル: (ancestor, descendant) の全ペアを生成
  SELECT
    dept_id AS ancestor_id,
    dept_id AS descendant_id                            -- 自分自身へのペア（distance=0）
  FROM departments

  UNION ALL

  SELECT
    c.ancestor_id,
    d.dept_id AS descendant_id         -- ★ 祖先から全子孫へのペアを展開
  FROM closure c
  JOIN departments d ON d.parent_id = c.descendant_id
)

SELECT
  dt.dept_id,
  dt.dept_name,
  dt.depth,
  dt.path,
  dt.own_budget,
  SUM(d2.own_budget) AS total_budget  -- 配下全部門のown_budgetを合計
FROM dept_tree dt
JOIN closure cl    ON cl.ancestor_id = dt.dept_id   -- 対象部門を祖先として検索
JOIN departments d2 ON d2.dept_id = cl.descendant_id -- 配下部門の予算を取得
GROUP BY dt.dept_id, dt.dept_name, dt.depth, dt.path, dt.own_budget
ORDER BY dt.depth, dt.dept_id;

/*
  実行順序:
  1. dept_tree(アンカー): parent_id IS NULL の本社のみ取得(1行)
  2. dept_tree(再帰 iter1): 技術部・営業部を展開、pathに' > '連結(+2行)
  3. dept_tree(再帰 iter2): バックエンド・フロント・国内・海外を展開(+4行) → 計7行
  4. closure(アンカー): 全7部門の自己ペア(ancestor=descendant)を生成(7行)
  5. closure(再帰 iter1): 各部門の直接子へのペアを追加(+6ペア)
  6. closure(再帰 iter2): 本社→孫部門(バックエンド等)のペアを追加(+4ペア) → 計17ペア
  7. 外側: dept_tree JOIN closure(ancestor=dept) JOIN departments(d2=descendant)
  8. GROUP BY + SUM: 各部門を祖先とする全ペアのown_budgetを合算
  9. ORDER BY depth, dept_id: 深度・部門ID順に出力
*/