遞歸CTE問題

我想在SQL Server中使用遞歸CTE從包含基礎樹結構的表構建謂詞公式。例如，我的表如下所示：遞歸CTE問題

Id | Operator/Val | ParentId 
-------------------------- 
1 | 'OR'   | NULL 
2 | 'AND'   | 1 
3 | 'AND'   | 1 
4 | '>'   | 2 
5 | 'a'   | 4 
6 | 'alpha'  | 4 
...

...表示（（A>阿爾法）和（b>測試版））OR（（C>伽瑪）和（a <增量））。

ParentId是在父節點的同一個表中對Id的引用。

我想寫一個查詢，將從表中建立這個字符串。可能嗎？

感謝

來源

2010-04-08 Chris

請把一些原始數據和預期產出之間的中間步驟來解釋這一點。我看不到你如何從一個到另一個，對不起 – gbn 2010-04-08 16:52:34

當我有機會的時候，我需要爲你創建一個圖像 - 基本上它將謂詞表示爲一個樹狀結構，然後在表格中展開，每個節點有一個指向其父母的指針。 – Chris 2010-04-08 20:44:46

酷！我一直在典型的分類大綱中做這類東西，但我從來沒有想過用CTE來對付語法樹。 – harpo 2010-04-08 22:21:39

是有可能做到這一點，但問題是不是CTE，檢查它與PIVOT 本文檔中閱讀更多關於它從這個鏈接

http://msdn.microsoft.com/en-us/library/ms177410.aspx

一些例子是類似於你的問題

來源

2010-04-08 16:22:09 Kronass

我想不出如何做雙遞歸，但希望其中的一箇中間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

來源

2010-04-08 17:15:58

您是否找到了解決方案？我發現了一些東西，但看起來很討厭。你將能夠使用遞歸fundtion這樣做容易得多......

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

來源

2010-04-08 19:11:37

看起來非常好，謝謝你。我需要明天進一步測試。我沒有考慮過使用遞歸函數，但它似乎是一個更好的解決方案。 – Chris 2010-04-08 20:42:25

請注意，標量函數僅限於遞歸深度爲32（不可更改），而CTE的遞歸深度默認爲100，可以增加甚至禁用。另請參閱http://msdn.microsoft.com/en-us/library/ms186755.aspx和http://msdn.microsoft.com/en-us/library/ms175972.aspx – Lucero 2010-04-08 22:12:29

對於生產環境，您可能需要使用遞歸函數去爲簡單起見，如果性能和遞歸深度限制（32級）不是問題。

然而，這裏是用熱膨脹係數（請注意，它會接受任何數量的「樹」，並返回一個結果爲沒有父每個項目）相當乾淨漂亮高效的解決方案：

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);

來源

2010-04-08 21:46:09 Lucero

非常聰明，謝謝。 – Chris 2010-04-09 14:05:17

感謝您的反饋！ upvote會把這個答案放在兩個不完整/非工作答案的基礎上。 ;） – Lucero 2010-04-09 14:16:59

遞歸CTE問題

回答

相關問題