控制流程圖 (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;
查詢結果
| NodeId | ParentId | Level |
| a | NULL | 1 |
| b | a | 2 |
| c | a | 2 |
| d | a | 2 |
CTE 遞迴執行流程
- 拆分為定位點成員與遞迴成員
- 執行定位點 → 產生基準結果集
T0 (Level=1)
- 以
T0 為輸入執行遞迴成員 → 產生 T1 (Level=2)
- 以
T1 為輸入 → T2 ... 直到某次迭代回傳空集
- 最終結果 =
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