Vấn đề CTE đệ quy

Question

Tôi đang cố gắng sử dụng CTE đệ quy trong SQL Server để xây dựng công thức dự đoán từ bảng chứa cấu trúc cây bên dưới. Ví dụ, bàn của tôi trông giống như:

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

... mà đại diện ((a> alpha) AND (b> beta)) OR ((c> gamma) AND (một < delta)).

ParentId là tham chiếu đến Id trong cùng một bảng của nút chính.

Tôi muốn viết truy vấn sẽ tạo chuỗi này từ bảng. Có thể không?

Cảm ơn

Answer 1

Có nó có thể làm điều đó nhưng vấn đề không phải là CTE, kiểm tra xem nó với PIVOT đọc thêm về nó từ liên kết này

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

một số ví dụ trong tài liệu này tương tự với sự cố của bạn

Answer 2

Tôi không thể tìm ra cách thực hiện thao tác đệ quy kép, nhưng hy vọng một trong các CTE trung gian sẽ giúp bạn đi đúng hướng:

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 

Answer 3

Bạn đã tìm thấy giải pháp chưa? Tôi tìm thấy một cái gì đó, nhưng có vẻ khá khó chịu. Bạn sẽ có thể thực hiện điều này dễ dàng hơn nhiều bằng cách sử dụng fundtion đệ quy ...

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 

OUTPUT

ConcatOp               
---------------------------------------------------------------- 
(((a > alpha) AND (b > beta)) OR ((c > gamma) AND (a < delta))) 

Nếu bạn muốn muốn nhìn vào một hàm đệ quy, cho tôi một tiếng hét và chúng ta có thể có một cái nhìn.

EDIT: Recursive Chức năng

Có xem xét đây là cách dễ dàng hơn nhiều

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 

Answer 4

Đối với một môi trường sản xuất, bạn có thể muốn đi với một hàm đệ quy vì đơn giản nếu hiệu suất và đệ quy giới hạn độ sâu (32 cấp độ) không phải là một vấn đề.

Tuy nhiên, đây là một giải pháp khá sạch sẽ và khá hiệu quả với CTEs (lưu ý rằng nó sẽ chấp nhận bất kỳ số lượng "cây" và gửi lại một kết quả cho từng hạng mục mà không có cha mẹ):

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