Recursive CTE Problem

Question

Próbuję użyć rekurencyjnego CTE w SQL Server do zbudowania predykatów z tabeli zawierającej podstawową strukturę drzewa. Na przykład, mój tabeli wygląda następująco:

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

... który stanowi ((a> alfa) i (b> p)), lub ((c> y) i (a < trójkąt)).

ParentId jest odniesieniem do Id w tej samej tabeli węzła nadrzędnego.

Chcę napisać zapytanie, które zbuduje ten ciąg z tabeli. Czy to możliwe?

Dzięki

Answer 1

Tak, to jest możliwe, aby to zrobić, ale problem nie jest CTE, sprawdź to z PIVOT przeczytać więcej na ten temat z tego linku

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

kilka przykładów w tej dokumentacji jest podobny do twojego problemu

Answer 2

Nie mogłem wymyślić jak wykonać podwójną rekursję, ale mam nadzieję, że jeden z pośrednich CTE w tym ustawi cię na właściwej drodze:

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

Znalazłeś już rozwiązanie? Znalazłem coś, ale wygląda całkiem paskudnie. Byłbyś w stanie zrobić to o wiele łatwiejsze przy użyciu rekurencyjnego 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 

WYJŚCIE

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

Jeśli wolisz zajrzeć do funkcji rekurencyjnej, daj mi krzyczeć i możemy rzucić okiem.

EDIT: rekurencyjne Funkcja

Wystarczy popatrzeć na ile łatwiej jest to

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

W środowisku produkcyjnym, może chcesz iść z funkcji rekurencyjnej dla uproszczenia, jeśli wydajność i rekurencji Ograniczenia głębokości (32 poziomy) nie stanowią problemu.

Jednak tutaj jest dość czyste i dość wydajne rozwiązanie z CTE (zauważ, że będzie przyjmować dowolną liczbę „drzewa” i powrócić jeden wynik dla każdego elementu, który nie ma rodzica):

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