我将尝试在SQL Server中使用递归CTE从包含底层树结构的表中建立谓词公式。
例如，我的表如下：
Id | Operator/Val | ParentId
--------------------------
1 | 'OR' | NULL
2 | 'AND' | 1
3 | 'AND' | 1
4 | '>' | 2
5 | 'a' | 4
6 | 'alpha' | 4
...
...它代表着 ((a > alpha) AND (b > beta)) OR ((c > gamma) AND (a < delta))。
ParentId 是指向同一表中父节点的 Id 的引用。
我想编写一个查询，从表中构建这个字符串。这是可能的吗？
谢谢。
对于生产环境，如果性能和递归深度限制（32级）不是问题，您可能希望选择递归函数以简化操作。
然而，这里提供了一种相当干净和高效的解决方案，使用公共表达式（CTEs）。请注意，它将接受任意数量的“树”，并为每个没有父元素的项目返回一个结果：
DECLARE @tbl TABLE
(
id int PRIMARY KEY
NOT NULL,
op nvarchar(max) NOT NULL,
parent int
) ;
INSERT INTO @tbl
SELECT 1, 'OR', NULL UNION ALL
SELECT 2, 'AND', 1 UNION ALL
SELECT 3, 'AND', 1 UNION ALL
SELECT 4, '>', 2 UNION ALL
SELECT 5, 'a', 4 UNION ALL
SELECT 6, 'alpha', 4 UNION ALL
SELECT 7, '>', 2 UNION ALL
SELECT 8, 'b', 7 UNION ALL
SELECT 9, 'beta', 7 UNION ALL
SELECT 10, '>', 3 UNION ALL
SELECT 11, 'c', 10 UNION ALL
SELECT 12, 'gamma', 10 UNION ALL
SELECT 13, '>', 3 UNION ALL
SELECT 14, 'd', 13 UNION ALL
SELECT 15, 'delta', 13 ;
WITH nodes -- A CTE which sets a flag to 1 for non-leaf nodes
AS (
SELECT t.*, CASE WHEN p.parent IS NULL THEN 0
ELSE 1
END node
FROM @tbl t
LEFT JOIN (
SELECT DISTINCT parent
FROM @tbl
) p ON p.parent = T.id
),
rec -- the main recursive run to determine the sort order and add meta information
AS (
SELECT id rootId, node lvl, CAST(0 AS float) sort, CAST(0.5 AS float) offset, *
FROM nodes
WHERE parent IS NULL
UNION ALL
SELECT r.rootId, r.lvl+t.node, r.sort+r.offset*CAST((ROW_NUMBER() OVER (ORDER BY t.id)-1)*2-1 AS float),
r.offset/2, t.*
FROM rec r
JOIN
nodes t ON r.id = t.parent
),
ranked -- ranking of the result to sort and find the last item
AS (
SELECT rootId, ROW_NUMBER() OVER (PARTITION BY rootId ORDER BY sort) ix,
COUNT(1) OVER (PARTITION BY rootId) cnt, lvl, op
FROM rec
),
concatenated -- concatenate the string, adding ( and ) as needed
AS (
SELECT rootId, ix, cnt, lvl, CAST(REPLICATE('(', lvl)+op AS nvarchar(max)) txt
FROM ranked
WHERE ix = 1
UNION ALL
SELECT r.rootId, r.ix, r.cnt, r.lvl,
c.txt+COALESCE(REPLICATE(')', c.lvl-r.lvl), '')+' '+COALESCE(REPLICATE('(', r.lvl-c.lvl), '')+r.op
+CASE WHEN r.ix = r.cnt THEN REPLICATE(')', r.lvl)
ELSE ''
END
FROM ranked r
JOIN
concatenated c ON (r.rootId = c.rootId)
AND (r.ix = c.ix+1)
)
SELECT rootId id, txt
FROM concatenated
WHERE ix = cnt
OPTION (MAXRECURSION 0);
我发现了一些东西，但看起来相当恶心。使用递归函数可以更轻松地完成这个任务...
DECLARE @Table TABLE(
ID INT,
Op VARCHAR(20),
ParentID INT
)
INSERT INTO @Table SELECT 1,'OR',NULL
INSERT INTO @Table SELECT 2,'AND',1
INSERT INTO @Table SELECT 3,'AND',1
INSERT INTO @Table SELECT 4,'>',2
INSERT INTO @Table SELECT 5,'a',4
INSERT INTO @Table SELECT 6,'alpha',4
INSERT INTO @Table SELECT 7,'>',2
INSERT INTO @Table SELECT 8,'b',7
INSERT INTO @Table SELECT 9,'beta',7
INSERT INTO @Table SELECT 10,'>',3
INSERT INTO @Table SELECT 11,'c',10
INSERT INTO @Table SELECT 12,'gamma',10
INSERT INTO @Table SELECT 13,'<',3
INSERT INTO @Table SELECT 14,'a',13
INSERT INTO @Table SELECT 15,'delta',13
;WITH Vals AS (
SELECT t.*,
1 Depth
FROM @Table t LEFT JOIN
@Table parent ON t.ID = parent.ParentID
WHERE parent.ParentID IS NULL
UNION ALL
SELECT t.*,
v.Depth + 1
FROM @Table t INNER JOIN
Vals v ON v.ParentID = t.ID
),
ValLR AS(
SELECT DISTINCT
vLeft.ID LeftID,
vLeft.Op LeftOp,
vRight.ID RightID,
vRight.Op RightOp,
vLeft.ParentID OperationID,
vLeft.Depth
FROM Vals vLeft INNER JOIN
Vals vRight ON vLeft.ParentID = vRight.ParentID
AND vLeft.ID < vRight.ID
WHERE (vRight.ID IS NOT NULL)
),
ConcatVals AS(
SELECT CAST('(' + LeftOp + ' ' + Op + ' ' + RightOp + ')' AS VARCHAR(500)) ConcatOp,
t.ID OpID,
v.Depth,
1 CurrentDepth
FROM ValLR v INNER JOIN
@Table t ON v.OperationID = t.ID
WHERE v.Depth = 1
UNION ALL
SELECT CAST('(' + cL.ConcatOp + ' ' + t.Op + ' {' + CAST(v.RightID AS VARCHAR(10)) + '})' AS VARCHAR(500)) ConcatOp,
t.ID OpID,
v.Depth,
cL.CurrentDepth + 1
FROM ValLR v INNER JOIN
@Table t ON v.OperationID = t.ID INNER JOIN
ConcatVals cL ON v.LeftID = cL.OpID
WHERE v.Depth = cL.CurrentDepth + 1
),
Replaces AS(
SELECT REPLACE(
c.ConcatOp,
SUBSTRING(c.ConcatOp,PATINDEX('%{%', c.ConcatOp), PATINDEX('%}%', c.ConcatOp) - PATINDEX('%{%', c.ConcatOp) + 1),
(SELECT ConcatOp FROM ConcatVals WHERE OpID = CAST(SUBSTRING(c.ConcatOp,PATINDEX('%{%', c.ConcatOp) + 1, PATINDEX('%}%', c.ConcatOp) - PATINDEX('%{%', c.ConcatOp) - 1) AS INT))
) ConcatOp,
1 Num
FROM ConcatVals c
WHERE Depth = (SELECT MAX(Depth) FROM ConcatVals)
UNION ALL
SELECT REPLACE(
r.ConcatOp,
SUBSTRING(r.ConcatOp,PATINDEX('%{%', r.ConcatOp), PATINDEX('%}%', r.ConcatOp) - PATINDEX('%{%', r.ConcatOp) + 1),
(SELECT ConcatOp FROM ConcatVals WHERE OpID = CAST(SUBSTRING(r.ConcatOp,PATINDEX('%{%', r.ConcatOp) + 1, PATINDEX('%}%', r.ConcatOp) - PATINDEX('%{%', r.ConcatOp) - 1) AS INT))
) ConcatOp,
Num + 1
FROM Replaces r
WHERE PATINDEX('%{%', r.ConcatOp) > 0
)
SELECT TOP 1
*
FROM Replaces
ORDER BY Num DESC
输出
ConcatOp
----------------------------------------------------------------
(((a > alpha) AND (b > beta)) OR ((c > gamma) AND (a < delta)))
如果你更喜欢看递归函数，请告诉我，我们可以一起看看。
编辑：递归函数
看看这个有多简单。
CREATE TABLE TableValues (
ID INT,
Op VARCHAR(20),
ParentID INT
)
INSERT INTO TableValues SELECT 1,'OR',NULL
INSERT INTO TableValues SELECT 2,'AND',1
INSERT INTO TableValues SELECT 3,'AND',1
INSERT INTO TableValues SELECT 4,'>',2
INSERT INTO TableValues SELECT 5,'a',4
INSERT INTO TableValues SELECT 6,'alpha',4
INSERT INTO TableValues SELECT 7,'>',2
INSERT INTO TableValues SELECT 8,'b',7
INSERT INTO TableValues SELECT 9,'beta',7
INSERT INTO TableValues SELECT 10,'>',3
INSERT INTO TableValues SELECT 11,'c',10
INSERT INTO TableValues SELECT 12,'gamma',10
INSERT INTO TableValues SELECT 13,'<',3
INSERT INTO TableValues SELECT 14,'a',13
INSERT INTO TableValues SELECT 15,'delta',13
GO
CREATE FUNCTION ReturnMathVals (@ParentID INT, @Side VARCHAR(1))
RETURNS VARCHAR(500)
AS
BEGIN
DECLARE @RetVal VARCHAR(500)
IF (@ParentID IS NULL)
BEGIN
SELECT @RetVal = ' (' + dbo.ReturnMathVals(ID,'L') + Op + dbo.ReturnMathVals(ID,'R') + ') '
FROM TableValues
WHERE ParentID IS NULL
END
ELSE
BEGIN
SELECT TOP 1 @RetVal = ' (' + dbo.ReturnMathVals(ID,'L') + Op + dbo.ReturnMathVals(ID,'R') + ') '
FROM TableValues
WHERE ParentID = @ParentID
ORDER BY CASE WHEN @Side = 'L' THEN ID ELSE -ID END
SET @RetVal = ISNULL(@RetVal, (SELECT TOP 1 Op FROM TableValues WHERE ParentID = @ParentID ORDER BY CASE WHEN @Side = 'L' THEN ID ELSE -ID END))
END
RETURN @RetVal
END
GO
SELECT dbo.ReturnMathVals(NULL, NULL)
GO
DROP FUNCTION ReturnMathVals
DROP TABLE TableValues
我无法理解如何进行双重递归，但希望本文中的其中一个中间CTE可以为您指明正确的方向：
SET NOCOUNT ON
DECLARE @tree AS TABLE
(
Id int NOT NULL
,Operator varchar(10) NOT NULL
,ParentId int
)
INSERT INTO @tree
VALUES (1, 'OR', NULL)
INSERT INTO @tree
VALUES (2, 'AND', 1)
INSERT INTO @tree
VALUES (3, 'AND', 1)
INSERT INTO @tree
VALUES (4, '>', 2)
INSERT INTO @tree
VALUES (5, 'a', 4)
INSERT INTO @tree
VALUES (6, 'alpha', 4)
INSERT INTO @tree
VALUES (7, '>', 2)
INSERT INTO @tree
VALUES (8, 'b', 7)
INSERT INTO @tree
VALUES (9, 'beta', 7)
INSERT INTO @tree
VALUES (10, '>', 3)
INSERT INTO @tree
VALUES (11, 'c', 10)
INSERT INTO @tree
VALUES (12, 'gamma', 10)
INSERT INTO @tree
VALUES (13, '>', 3)
INSERT INTO @tree
VALUES (14, 'd', 13)
INSERT INTO @tree
VALUES (15, 'delta', 13) ;
WITH lhs_selector
AS (
SELECT ParentId
,MIN(Id) AS Id
FROM @tree
GROUP BY ParentId
),
rhs_selector
AS (
SELECT ParentId
,MAX(Id) AS Id
FROM @tree
GROUP BY ParentId
),
leaf_selector
AS (
SELECT Id
FROM @tree AS leaf
WHERE NOT EXISTS ( SELECT *
FROM @tree
WHERE ParentId = leaf.Id )
),
recurse
AS (
SELECT operator.Id
,CASE WHEN lhs_is_leaf.Id IS NOT NULL THEN NULL
ELSE lhs.Id
END AS LhsId
,CASE WHEN rhs_is_leaf.Id IS NOT NULL THEN NULL
ELSE rhs.Id
END AS RhsId
,CASE WHEN COALESCE(lhs_is_leaf.Id, rhs_is_leaf.Id) IS NULL
THEN '({' + CAST(lhs.Id AS varchar) + '} ' + operator.Operator + ' {'
+ CAST(rhs.Id AS varchar) + '})'
ELSE '(' + lhs.Operator + ' ' + operator.Operator + ' ' + rhs.Operator + ')'
END AS expression
FROM @tree AS operator
INNER JOIN lhs_selector
ON lhs_selector.ParentID = operator.Id
INNER JOIN rhs_selector
ON rhs_selector.ParentID = operator.Id
INNER JOIN @tree AS lhs
ON lhs.Id = lhs_selector.Id
INNER JOIN @tree AS rhs
ON rhs.Id = rhs_selector.Id
LEFT JOIN leaf_selector AS lhs_is_leaf
ON lhs_is_leaf.Id = lhs.Id
LEFT JOIN leaf_selector AS rhs_is_leaf
ON rhs_is_leaf.Id = rhs.Id
)
SELECT *
,REPLACE(REPLACE(op.expression, '{' + CAST(op.LhsId AS varchar) + '}', lhs.expression),
'{' + CAST(op.RhsId AS varchar) + '}', rhs.expression) AS final_expression
FROM recurse AS op
LEFT JOIN recurse AS lhs
ON lhs.Id = op.LhsId
LEFT JOIN recurse AS rhs
ON rhs.Id = op.RhsId
是的，可以做到，但问题不在CTE上，请使用PIVOT进行检查。请从此链接了解更多信息。
http://msdn.microsoft.com/en-us/library/ms177410.aspx
这份文档中的一些示例与您的问题相似