萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 資料庫 >> SQL Server 教學

SQL Server 2005 以關聯式資料庫儲存控制流程圖 (CFG) 並用 CTE 遞迴查詢支配關係

控制流程圖 (CFG) 表達程式區塊間的支配關係。利用關聯式資料庫儲存 CFG 節點與邊,配合 CTE 遞迴查詢可高效解決「節點 A 支配哪些節點」等圖論問題。

資料模型

CREATE TABLE CfgEdges (
    NodeId   NVARCHAR(50) NOT NULL,  -- 當前節點
    ParentId NVARCHAR(50) NULL,      -- 父節點 (支配者)
    CONSTRAINT PK_CfgEdges PRIMARY KEY (NodeId)
);

-- 範例資料:a 支配 b,c,d
INSERT INTO CfgEdges VALUES 
('a', NULL),   -- 根節點
('b', 'a'),
('c', 'a'),
('d', 'a');

CTE 遞迴查詢:尋找節點 'a' 的所有被支配節點

WITH Re_CTE (NodeId, ParentId, Level) AS (
    -- 定位點:根節點
    SELECT NodeId, ParentId, 1 AS Level
    FROM CfgEdges
    WHERE NodeId = 'a'
    
    UNION ALL
    
    -- 遞迴成員:向下遍歷
    SELECT t.NodeId, t.ParentId, c.Level + 1
    FROM CfgEdges t
    INNER JOIN Re_CTE c ON t.ParentId = c.NodeId
)
SELECT * FROM Re_CTE;

查詢結果

CTE 遞迴執行流程

  1. 拆分為定位點成員與遞迴成員
  2. 執行定位點 → 產生基準結果集 T0 (Level=1)
  3. 以 T0 為輸入執行遞迴成員 → 產生 T1 (Level=2)
  4. 以 T1 為輸入 → T2 ... 直到某次迭代回傳空集
  5. 最終結果 = T0 UNION ALL T1 UNION ALL ...

遞迴 CTE 結構規範 (MSDN)

WITH cte_name (column_list) AS (
    -- Anchor member(s)
    query_definition
    UNION ALL
    -- Recursive member(s) referencing cte_name
    query_definition
)
SELECT * FROM cte_name;
  • 至少一個定位點、一個遞迴成員
  • 定位點間:UNION/UNION ALL/INTERSECT/EXCEPT
  • 最後一定點與遞迴成員、遞迴成員間:**必須 UNION ALL**
  • 所有成員欄位數、型別完全一致
  • 遞迴成員 FROM 只能引用 CTE 一次
  • 遞迴成員禁用:DISTINCT, GROUP BY, HAVING, 標量彙總, TOP, OUTER JOIN, 子查詢

擴充應用:完整支配樹與路徑

WITH DomTree AS (
    SELECT NodeId, ParentId, 0 AS Level,
           CAST(NodeId AS NVARCHAR(MAX)) AS Path
    FROM CfgEdges WHERE ParentId IS NULL
    
    UNION ALL
    
    SELECT e.NodeId, e.ParentId, d.Level + 1,
           d.Path + '->' + e.NodeId
    FROM CfgEdges e
    INNER JOIN DomTree d ON e.ParentId = d.NodeId
)
SELECT * FROM DomTree ORDER BY Path;

效能考量

  • 遞迴深度預設 100 層,深層圖需 OPTION (MAXRECURSION 0)
  • 大圖建議建立 ParentId 索引支援 JOIN
  • 超大規模圖運算 (百萬節點) 考慮圖資料庫或應用層演算法

關聯式資料庫 + CTE 遞迴,優雅解決階層/圖結構查詢,是 SQL 開發者必備技能包。

copyright © 萬盛學電腦網 all rights reserved
NodeIdParentIdLevel
aNULL1
ba2
ca2
da2