Recursive CTE Problem

Question

I am trying to use a recursive CTE in SQL Server to build up a predicate formula from a table containing the underlying tree structure. For example, my table looks like:

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

...which represents ((a > alpha) AND (b > beta)) OR ((c > gamma) AND (a < delta)).

ParentId is a reference to the Id in the same table of the parent node.

I want to write a query which will build up this string from the table. Is it possible?

Thanks

Buttery

Please put some intermediate steps between the raw data and expected output to explain this more. I can't see how you get from one to the other, sorry – Fascicule

I'll need to create an image for you when I get chance - basically it's representing the predicate as a tree structure which is then flattened in the table, each node having a pointer to its parent. – Buttery

Cool! I do this kind of stuff all the time on your typical category outline, but I never thought about using CTE against a grammar tree. – Gallegos

how do you plan on dealing with the assumption that the Id column is enough to specify left vs right ordering withing the tree structure? – Ake

Good point Nat - I had planned on adding another column for the left/right ordering in the tree, but wanted to keep it simple for the question, then build on it. – Buttery

@Chris: Have you found the answer you've been looking for? Please do accept answers and vote, it's what makes SO go round. – Macrogamete

Answer 1

For a production environment, you may want to go with a recursive function for simplicity if performance and recursion depth limits (32 levels) is not a problem.

However, here's a quite clean and pretty efficient solution with CTEs (note that it will accept any number of "trees" and return one result for each item which has no parent):

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

Macrogamete

Thanks for the feedback! A upvote would put this answer on top of the two incomplete/non-working answers. ;) – Macrogamete

Answer 2

I found something, but it looks pretty nasty. You would be able to do this a lot easier using a recursive 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

OUTPUT

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

If you would rather want to look at a recursive function, give me a shout and we can have a look.

EDIT: Recursive Function

Have a look at how much easier this is

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

Kodak

Looks very good, thanks for this. I need to test it further tomorrow. I hadn't considered just using recursive functions, but it seems to be a better solution. – Buttery

Note that scalar functions are limited to a recursion depth of 32 (not changeable), while the recursion depth for CTEs is by default 100 and can be increased or even disabled. See also msdn.microsoft.com/en-us/library/ms186755.aspx and msdn.microsoft.com/en-us/library/ms175972.aspx – Macrogamete

Answer 3

Yes it is possible to do it but the problem is not the CTE, check it with PIVOT read more about it from this link

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

some examples in this documentation is similar with your problem

Storage

Answer 4

I couldn't figure out how to do the double-recursion, but hopefully one of the intermediate CTEs in this will set you on the right track:

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

Indecency