如何在T-SQL中实现基于变量依赖的方程集合拓扑排序

实现逻辑 #

• 拆分每个表达式，提取等号左侧的目标变量和右侧的表达式内容
• 解析右侧表达式，提取所有依赖的变量，过滤常量数值
• 通过递归CTE计算每个表达式的依赖层级：无任何变量依赖的常量表达式层级为1，其他表达式层级为其所有依赖变量的最大层级+1
• 按层级从小到大分配排序序号，确保所有依赖项的计算优先级高于当前表达式

完整可运行代码 #

DECLARE @TopSort TABLE 
(
   Expression VARCHAR(2000)
  ,[Order] INT
);

INSERT INTO @TopSort VALUES ('SSS =  BBB + KKK + JJJ', null)
INSERT INTO @TopSort VALUES ('MMM = EEE + RRR + GGG', null)
INSERT INTO @TopSort VALUES ('KKK = BBB + CCC + AAA', null)
INSERT INTO @TopSort VALUES ('BBB = CCC + QQQ', null)
INSERT INTO @TopSort VALUES ('DDD = BBB + SSS + RRR + 34', null)
INSERT INTO @TopSort VALUES ('AAA = PPP + 21', null)
INSERT INTO @TopSort VALUES ('PPP = 8', null)
INSERT INTO @TopSort VALUES ('JJJ = EEE + HHH + PPP + AAA', null)
INSERT INTO @TopSort VALUES ('YYY = SSS + MMM + DDD', null)
INSERT INTO @TopSort VALUES ('GGG = PPP + EEE + 45', null)
INSERT INTO @TopSort VALUES ('HHH = 76', null)
INSERT INTO @TopSort VALUES ('CCC = RRR + MMM', null)
INSERT INTO @TopSort VALUES ('QQQ = MMM + JJJ + CCC', null) 
INSERT INTO @TopSort VALUES ('EEE = 23', null)
INSERT INTO @TopSort VALUES ('RRR = AAA + HHH + GGG + 56', null)
INSERT INTO @TopSort VALUES ('ZZZ = AAA+DDD+BBB', null);

WITH SplitExpressions AS (
    -- 拆分表达式为目标变量和右侧计算部分
    SELECT
        Expression,
        LTRIM(RTRIM(LEFT(Expression, CHARINDEX('=', Expression) - 1))) AS TargetVar,
        REPLACE(REPLACE(LTRIM(RTRIM(RIGHT(Expression, LEN(Expression) - CHARINDEX('=', Expression)))), ' ', ''), '+', '|') AS RightPart
    FROM @TopSort
),
VarDependencies AS (
    -- 提取所有依赖的变量，过滤数字常量
    SELECT
        s.TargetVar,
        s.Expression,
        v.value AS DependentVar
    FROM SplitExpressions s
    CROSS APPLY STRING_SPLIT(s.RightPart, '|') v
    WHERE ISNUMERIC(v.value) = 0
),
RecursiveLevelCalc AS (
    -- 递归锚点：没有任何依赖的常量表达式层级为1
    SELECT
        s.TargetVar,
        s.Expression,
        1 AS CalcLevel
    FROM SplitExpressions s
    LEFT JOIN VarDependencies d ON s.TargetVar = d.TargetVar
    WHERE d.DependentVar IS NULL

    UNION ALL

    -- 递归计算：当前表达式层级=依赖变量的最大层级+1
    SELECT
        d.TargetVar,
        d.Expression,
        r.CalcLevel + 1 AS CalcLevel
    FROM VarDependencies d
    INNER JOIN RecursiveLevelCalc r ON d.DependentVar = r.TargetVar
)
-- 去重取最大层级，分配排序序号
SELECT 
    Expression,
    DENSE_RANK() OVER(ORDER BY MAX(CalcLevel) ASC) AS [Order]
FROM RecursiveLevelCalc
GROUP BY TargetVar, Expression
ORDER BY [Order], Expression;

输出说明 #

运行上述代码后，Order字段值越小优先级越高，可直接按照该顺序执行表达式计算，保证所有依赖变量都已提前完成求值。

内容的提问来源于stack exchange，提问作者John Snow