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

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

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