Suppose that you work for ABC Solutions, which has a set of business rules it uses to determine whether an employee is authorized to execute a particular operation. You've been tasked with evaluating the business rules for each employee. The database table named Employee stores the IDs of the employees, along with the attributes used to describe them. Each business rule is expressed through a Boolean proposition that involves the employee attributes. The proposition is codified as the number of rows stored in the database table named Rules.

Related: CTEs with Multiple Recursive Members

You can evaluate the business rules for each employee by running a T-SQL query against the Employee and Rules tables, without placing limits on proposition complexity. To do so, you need to use two components: recursive common table expressions (CTEs) and Reverse Polish notation (RPN).

Exploring Recursive CTEs

You can think of a CTE as a temporary result set defined within a T-SQL statement. Once defined, you can further reference the CTE in the statement. When the CTE definition references itself, you're in the presence of recursive CTE.

For example, the code in Listing 1 demonstrates how a recursive CTE works.

  1. USE AdventureWorksDW2012
  2. GO
  3. WITH Emp_CTE AS (
  4.   -- Anchor
  5.   SELECT EmployeeKey, FirstName, LastName, 1 as EmpLevel
  6.   FROM dbo.DimEmployee
  7.   WHERE ParentEmployeeKey IS NULL
  8.   UNION ALL
  9.   -- Recursive member
  10.   SELECT e.EmployeeKey, e.FirstName, e.LastName,
  11.     ecte.EmpLevel + 1
  12.   FROM dbo.DimEmployee e
  13.   INNER JOIN Emp_CTE ecte
  14.    ON ecte.EmployeeKey = e.ParentEmployeeKey
  15. )
  16. SELECT FirstName, LastName, EmpLevel
  17. FROM Emp_CTE

In this code, which uses the data from the AdventureWorksDW2012 database, the CTE is named Emp_CTE. It contains two SELECT statements. The first SELECT statement, generally known as the anchor, provides the base elements of the final result set. In this case, the base elements are employees who don't have hierarchy parents. The second SELECT statement, generally known as the recursive member, references the CTE itself. This statement joins the CTE (which contains the base elements) with the Employee table. The resulting set contains all employees having their parent in Emp_CTE. The union of these employees with first base set will build a new base set, extending the old one, ready to be used as input for the next recursive iteration. By iterating the recursive step, the entire Employee hierarchy will be explored, showing the power of recursive CTEs in dealing with hierarchical data.

Exploring the Input Tables at ABC Solutions

Now that you know how recursive CTEs work, let's look at the input tables that will be used for the recursive CTEs at ABC Solutions. As Listing 2 shows, the Employee table simply contains some employees described using the Title and Department attributes.

  1. CREATE TABLE [dbo].[Employee](
  2.   [EmpId] [int] NOT NULL,
  3.   [Title] [nvarchar](50) NULL,
  4.   [Department] [nvarchar](50) NULL,
  6.  ([EmpId] ASC)
  7. )

With those attributes in mind, consider the Boolean expression:

  1. ((Department='Dep1') or (Department like 'Dep2%'))
  2.   and (Title='d')

This expression contains three atomic propositions—(Department='Dep1'), (Department like 'Dep2%'), and (Title='d')—that will be named p1, p2, and p3, respectively. The expression also contains a complex proposition—(p1 or p2)—that will be named p4. Finally, the expression contains a root proposition, p5, defined as (p4 and p3). Without loss of generality, the expression considers only binary operators. (For example, the AND of the three propositions could be decomposed using the associative property of the AND operator.)

Taking all this into account, the Rules table is defined. As Listing 3 shows, the Rules table defines a hierarchical binary tree, where leaf nodes correspond to the atomic propositions. The parent nodes correspond to complex propositions built through logical AND, OR, and NOT operations involving their children. So, it's possible to label each parent node of the tree with a Boolean value, where the label is obtained by applying the node operator on the Boolean labels of the children. (The root label corresponds to the whole expression evaluation.)

  1. CREATE TABLE [dbo].[Rules](
  2.   [RuleId] [int]  NOT NULL,
  3.   [Description] [nvarchar](50),
  4.   [IsAtomic] [bit] NULL
  5.   -- IsAtomic = 1 for atomic propositions
  6.   -- Example: Department = 'Dep1')
  7.   -- IsAtomic = 0 for complex propositions
  8.   -- Example: (p4 AND p3)
  9.   [FieldSelector] [int] NULL,
  10.   -- FieldSelector = NULL for complex propositions
  11.   -- FieldSelector = 0 selection of field Department
  12.   -- Example: Department = 'Dep1'-->FieldSelector=0
  13.   -- FieldSelector = 1 selection of field Title
  14.   -- Example: Title = 'd'-->FieldSelector=1
  15.   [Operator] [int] NULL,
  16.   -- In complex propositions, Operator enumerates
  17.   -- logical operators (0 NOT, 1 AND, 2 OR)
  18.   -- In atomic propositions, Operator enumerates
  19.   -- comparison operators (0 =, 1 LIKE)
  20.   [Expression] [nvarchar](max) NULL,
  21.   -- Expression value is taken into account only for
  22.   -- atomic propositions
  23.   -- Example: Department like 'Dep2%'-->FieldSelector=1,
  24.   -- Operator=1, Expression='Dep2%'
  25.   [LeftRule] [int] NULL,
  26.   -- In complex propositions, LeftRule matches with the
  27.   -- RuleId of the first child proposition
  28.   [RightRule] [int] NULL,
  29.   -- In complex propositions, RightRule matches with the
  30.   -- RuleId of the second child proposition
  32. )

Considering this possibility, your first inclination might be to use the recursive CTE for expression evaluation. After all, it makes sense to define an anchor containing leaf nodes of the Rules table, followed by a recursive member that joins the CTE with the parent nodes. Each step of the recursion would evaluate the Boolean operator of the parent nodes applied to their children. To clarify the key points of this solution, consider this code:

  1. WITH RecursiveCTETree(Evaluation,RuleId)(
  2.   SELECT label(RuleId), RuleId from Rules
  3.   WHERE is_leaf(RuleId)=true
  4.     UNION ALL
  5.     SELECT evaluate(parent.Operator,leftchild.Evaluation,
  6.       rightchild.Evaluation), parent.RuleId
  7.     FROM Rules AS parent
  8.     INNER JOIN RecursiveCTETree AS leftchild
  9.       ON (parent.LeftRule=leftchild.RuleId)
  10.     Inner join RecursiveCTETree as rightchild
  11.       ON (parent.RightRule=rightchild.RuleId)
  12. )

Unfortunately, this solution doesn't work because the recursive member's FROM clause refers to the CTE twice. When defining a CTE's recursive member, one limitation is that the FROM clause can refer to the CTE only one time. There are also other limitations. For example, GROUP BY and HAVING clauses aren't allowed inside a recursive member. For a complete discussion of this topic, see the WITH common_table_expression (Transact-SQL) web page.

Exploring RPN

As you've seen, you can't use recursive CTE alone to solve the problem. You also need the second component: RPN. RPN is a mathematical notation in which every operator follows all of its operands. Also known as the postfix notation, it's parenthesis-free. For example, consider the infix expression:

  1. p1 or ((p2 or p3) and p4) or p5

In RPN, it can be written like this:

  1. p1 p2 p3 or p4 and or p5 or

One interesting feature of RPN is the ability to evaluate a Boolean expression through recursion of literal substitution. Consider the RPN expression 11or0or. The left substring 11or can be substituted using the lookup table shown in Table 1.

Left Substring

Replace With

Table 1: Lookup Table









After substitution, the string 11or0or will be replaced by 10or. Applying the lookup table again, 10or will be replaced by 1, which is the final evaluation of the whole initial expression.

Combining RPN and Recursive CTEs at ABC Solutions

To evaluate the business rules for each employee at ABC Solutions, you need to combine the RPN and recursive CTE components.

  1. -- STEP 1
  2. WITH RecursiveCTETree(RuleId,StatementId,SequenceId) AS (
  3.   SELECT RuleId, StatementId, CAST(CAST(StatementId
  4.     AS binary(4)) AS varbinary(1000)) AS SequenceId
  5.   FROM
  6.   -- Anchor containing root nodes
  7.   (
  8.     SELECT r1.RuleId, r1.RuleId AS StatementId
  9.     FROM dbo.Rules r1
  10.     LEFT OUTER JOIN dbo.Rules r2 ON
  11.     ((r1.Ruleid=r2.RightRule) OR (r1.Ruleid=r2.LeftRule))
  12.     WHERE r2.RuleId IS NULL
  13.   ) t
  14.   UNION ALL
  15.   -- First recursive member
  16.   SELECT t1.LeftRule, StatementId,
  17.     CAST(SequenceId+CAST(0x02 as binary(1))
  18.     AS varbinary(1000))
  19.   FROM RecursiveCTETree t0
  20.   INNER JOIN dbo.Rules t1 ON t0.RuleId=t1.RuleId
  21.   WHERE t1.IsAtomic=0
  22.   UNION ALL
  23.   -- Second recursive member
  24.   SELECT t1.RightRule, StatementId,
  25.     CAST(SequenceId+CAST(0x01 AS binary(1))
  26.     AS varbinary(1000))
  27.   FROM RecursiveCTETree t0
  28.   INNER JOIN dbo.Rules t1 ON t0.RuleId=t1.RuleId
  29.   WHERE t1.IsAtomic=0 AND t1.RightRule IS NOT NULL
  30. )
  32. -- STEP 2
  33. ,ExpressionElements as (
  34.   SELECT t1.StatementId, t1.Position, t0.*
  35.   FROM
  36.   -- Cross product of Rules and Employees
  37.   (
  38.     SELECT r.RuleId, e.EmpId,
  39.     CASE
  40.       WHEN (IsAtomic=0) AND (Operator = 0) THEN 'n'
  41.       WHEN (IsAtomic=0) AND (Operator = 1) THEN 'a'
  42.       WHEN (IsAtomic=0) THEN 'o'
  43.       WHEN (FieldSelector = 0) AND (Operator = 0)
  44.         AND (Department = Expression) THEN '1'
  45.       WHEN (FieldSelector = 0) AND (Operator = 0) THEN '0'
  46.       WHEN (FieldSelector = 1) AND (Operator = 0)
  47.         AND (Title = Expression) THEN '1'
  48.       WHEN (FieldSelector = 1) AND (Operator = 0) THEN '0'
  49.       WHEN (FieldSelector = 0) AND (Operator = 1)
  50.         AND (Department like Expression) THEN '1'
  51.       WHEN (FieldSelector = 0) AND (Operator = 1) THEN '0'
  52.       WHEN (FieldSelector = 1) AND (Operator = 1)
  53.         AND (Title like Expression) THEN '1'
  54.       WHEN (FieldSelector = 1) AND (Operator = 1) THEN '0'
  55.     END AS Value
  56.     FROM dbo.Rules r CROSS JOIN dbo.Employee e
  57.   ) t0
  58.   INNER JOIN(
  59.     SELECT StatementId,RuleId
  60.     ,RANK() OVER (PARTITION BY StatementId
  61.       ORDER BY SequenceId desc) AS Position
  62.     FROM RecursiveCTETree
  63.   )t1 ON t0.RuleId=t1.RuleId
  64. )
  66. --STEP 3
  67. ,RecursiveCTEEvaluation(StatementId,EmpId,Position,Value)
  68.   AS(
  69.   -- Anchor
  70.   SELECT StatementId, EmpId,
  71.     Position, CAST(Value AS varchar(max))
  72.   FROM ExpressionElements
  73.   WHERE Position=1
  74.   UNION ALL
  75.   -- Recursive member
  76.   SELECT t0.StatementId, t0.EmpId, t1.Position,
  77.   CASE
  78.     WHEN t1.value='n' AND t0.Value='1' THEN '0'
  79.     WHEN t1.value='n' AND t0.Value='0' THEN '1'
  80.     WHEN t1.value='a' AND t0.Value LIKE '%00'
  81.       THEN LEFT (t0.value,len(t0.value)-2)+'0'
  82.     WHEN t1.value='a' AND t0.Value LIKE '%01'
  83.       THEN LEFT (t0.value,len(t0.value)-2)+'0'
  84.     WHEN t1.value='a' AND t0.Value LIKE '%10'
  85.       THEN LEFT (t0.value,len(t0.value)-2)+'0'
  86.     WHEN t1.value='a' AND t0.Value LIKE '%11'
  87.       THEN LEFT (t0.value,len(t0.value)-2)+'1'
  88.     WHEN t1.value='o' AND t0.Value LIKE '%00'
  89.       THEN LEFT (t0.value,len(t0.value)-2)+'0'
  90.     WHEN t1.value='o' AND t0.Value LIKE '%01'
  91.       THEN LEFT (t0.value,len(t0.value)-2)+'1'
  92.     WHEN t1.value='o' AND t0.Value LIKE '%10'
  93.       THEN LEFT (t0.value,len(t0.value)-2)+'1'
  94.     WHEN t1.value='o' AND t0.Value LIKE '%11'
  95.       THEN LEFT (t0.value,len(t0.value)-2)+'1'
  96.     ELSE t0.Value+t1.value
  97.   END
  98.   FROM RecursiveCTEEvaluation t0
  99.   INNER JOIN ExpressionElements t1
  100.     ON ((t0.Position+1=t1.Position)
  101.     AND (t0.StatementId=t1.StatementId)
  102.     AND (t0.EmpId=t1.EmpId))
  103. )
  104. SELECT Description AS [Rule], EmpId, Value
  105. FROM
  106. (
  107.   SELECT StatementId,EmpId,Value,Position,max(Position)
  108.     OVER (PARTITION BY StatementId,Empid) AS pos
  109.   FROM RecursiveCTEEvaluation
  110. ) t0
  111. INNER JOIN dbo.Rules t1 ON t0.StatementId=t1.RuleId
  112. WHERE Position=pos
  113. ORDER BY EmpId,StatementId

As Listing 4 shows, the solution involves three steps:

  1. Define a recursive CTE that explores the expression tree contained in the Rules table. The recursive CTE will label each node with a number identifying the order of the node inside the expression rewritten in RPN.
  2. Evaluate the atomic propositions for each employee. The resulting value (true or false) will replace the atomic propositions inside the RPN expression built in the previous step. For example, suppose you have the proposition p1p2and and two employees—p1,p2=0,0 for the first employee and p1,p2=1,1 for the second employee. The substitution process will duplicate the initial expression (p1p2and), after which it will replace the initial (i.e., original) expression with 00and and 11and.
  3. Perform recursive literal substitution for all RPN expressions, as previously explained. Once again, a recursive CTE will be used to help reach the goal.

Let's look at each step in detail.

Examining Step 1

As previously mentioned, the Rules table stores the propositions. Suppose you want to populate the Rules table with two propositions. The first proposition is:

  1. ((Department = 'Dep1') or (Department like 'Dep2%'))
  2.   and ((Title='t1') or (Title like 't2%'))

Expressed in RPN, it turns into:

  1. (Department = 'Dep1') (Department like 'Dep2%')
  2.   or (Title='t1') (Title like 't2%') or and

Listing 5 shows the code to populate the Rules table with this proposition.

  1. -- First expression:
  2. -- ((Department = 'Dep1') or (Department like 'Dep2%'))
  3. -- and ((Title='t1') or (Title like 't2%'))
  5. -- Root AND node, RuleId=1
  6. INSERT [dbo].[Rules] ([RuleId], [Description],
  7.   [IsAtomic], [FieldSelector], [Operator],
  8.   [Expression], [LeftRule], [RightRule])
  9.   VALUES (1, 'First Rule',0, NULL, 1, NULL, 2, 5)
  11. -- Logical OR, RuleId=2
  12. INSERT [dbo].[Rules] ([RuleId], [IsAtomic], [FieldSelector],
  13.   [Operator], [Expression], [LeftRule], [RightRule])
  14.   VALUES (2, 0, NULL, 2, NULL, 3, 4)
  16. -- (Department = 'Dep1'), RuleId=3
  17. INSERT [dbo].[Rules] ([RuleId], [IsAtomic], [FieldSelector],
  18.   [Operator], [Expression], [LeftRule], [RightRule])
  19.   VALUES (3, 1, 0, 0, N'Dep1', NULL, NULL)
  21. -- (Department like 'Dep2%'), RuleId=4
  22. INSERT [dbo].[Rules] ([RuleId], [IsAtomic], [FieldSelector],
  23.   [Operator], [Expression], [LeftRule], [RightRule])
  24.   VALUES (4, 1, 0, 1, N'Dep2%', NULL, NULL)
  26. -- Logical OR, RuleId=5
  27. INSERT [dbo].[Rules] ([RuleId], [IsAtomic], [FieldSelector],
  28.   [Operator], [Expression], [LeftRule], [RightRule])
  29.   VALUES (5, 0, NULL, 2, NULL, 6, 7)
  31. -- (Title='t1'), RuleId=6
  32. INSERT [dbo].[Rules] ([RuleId], [IsAtomic], [FieldSelector],
  33.   [Operator], [Expression], [LeftRule], [RightRule])
  34.   VALUES (6, 1, 1, 0, N't1', NULL, NULL)
  36. -- (Title like 't2%'), RuleId=7
  37. INSERT [dbo].[Rules] ([RuleId], [IsAtomic], [FieldSelector],
  38.   [Operator], [Expression], [LeftRule], [RightRule])
  39.   VALUES (7, 1, 1, 1, N't2%', NULL, NULL)
  41. -- Second expression:
  42. -- not ((Department = 'Dep1') or (Title='t2'))
  44. -- Root NOT node, RuleId=8
  45. INSERT [dbo].[Rules] ([RuleId], [Description],
  46.   [IsAtomic], [FieldSelector], [Operator],
  47.   [Expression], [LeftRule], [RightRule])
  48.   VALUES (8,'Second rule', 0, NULL, 0, NULL, 9, NULL)
  50. -- Logical OR, RuleId=9
  51. INSERT [dbo].[Rules] ([RuleId], [IsAtomic], [FieldSelector],
  52.   [Operator], [Expression], [LeftRule], [RightRule])
  53.   VALUES (9, 0, NULL, 2, NULL, 10, 11)
  55. -- (Department = 'Dep1'), RuleId=10
  56. INSERT [dbo].[Rules] ([RuleId], [IsAtomic], [FieldSelector],
  57.   [Operator], [Expression], [LeftRule], [RightRule])
  58.   VALUES (10, 1, 0, 0, N'Dep1', NULL, NULL)
  60. -- (Title = 't2'), RuleId=11
  61. INSERT [dbo].[Rules] ([RuleId], [IsAtomic], [FieldSelector],
  62.   [Operator], [Expression], [LeftRule], [RightRule])
  63.   VALUES (11, 1, 1, 0, N't2', NULL, NULL)

By reading the comment above each INSERT statement, it's possible to verify that the RPN expression (read from left to right) corresponds to the RuleId sequence of 3,4,2,6,7,5,1.

The second proposition is:

  1. not((Department='Dep1') or (Title='t2'))

Expressed in RPN, it turns into:

  1. (Department='Dep1') (Title='t2') or not

Listing 5 also includes this proposition. Once again, it's possible to verify that the RPN expression (read from left to right) corresponds to the RuleId sequence of 10,11,9,8.

To verify that step 1 is working properly, you can copy and paste the code for step 1 into the following query, then execute it:

  1. -- Put code for step 1 here
  2. SELECT StatementId,RuleId
  3. FROM RecursiveCTETree
  4. ORDER BY StatementId, SequenceId DESC

You should get results like that in Figure 1.

Verifying the Results from Step 1

As you can see, StatementId discriminates the first expression from the second expression. For each StatementId, the order of RuleId matches the expected RPN order.

How does the code in step 1 work? The CTE's anchor query individuates the root nodes of all the propositions contained in the Rules table and labels each root node with a distinct StatementId. The CTE also contains two recursive members. The first member joins all left children to the base node set. The second member joins all right children to the resulting union of the base set with the first member. The resulting union (which consists of the root nodes, left children, and right children) is the new base set for the next recursion step. Please note that the SequenceId field is calculated in a cumulative way through the recursion steps. For root nodes, the SequenceId value is equal to the StatementId value. For the left child nodes in the first recursive member, the SequenceId value is equal to the concatenation of the parent value with 0x02. For the right child nodes in the second recursive member, the SequenceId value is equal to the concatenation of the parent value and 0x01. Applying these rules, the SequenceId values are calculated for the nodes in the first proposition. They are:

  • RuleId=1 is SequenceId=0x01
  • RuleId=2 is SequenceId=0x0102
  • RuleId=3 is SequenceId=0x010202
  • RuleId=4 is SequenceId=0x010201
  • RuleId=5 is SequenceId=0x0101
  • RuleId=6 is SequenceId=0x010102
  • RuleId=7 is SequenceId=0x010101

If you put the nodes in descending SequenceId order, the RuleId order is 3,4,2,6,7,5,1—the same as the RPN order.

Examining Step 2

As Listing 4 shows, step 2 starts by evaluating the cross product of the Rules and Employees tables. For each product couple (r,e), the statement evaluates the Boolean value of the atomic proposition, with key r applied to employee e. The evaluation is stored in the Value field. However, if r is associated to a complex proposition, the Value field is left null.

To reorder the propositions using RPN, you need to find, for each proposition r calculated during the cross product evaluation, the order of r inside the statement found at step 1. This is obtained through the join with RecursiveCTETree.

To verify the results of step 2, let's populate the Employee table by running the code:

  1. INSERT [dbo].[Employee] ([EmpId], [Department], [Title])
  2.   VALUES (1, N'Dep1', N't1')
  3. INSERT [dbo].[Employee] ([EmpId], [Department], [Title])
  4.   VALUES (2, N'Dep3', N't3')

Next, copy and paste the code for step 1 and step 2 into the following query, then execute it:

  1. -- Put code for step 1 here
  2. -- Put code for step 2 here
  3. SELECT EmpId,StatementId,Position,Value
  4. FROM ExpressionElements
  5. ORDER BY EmpId,StatementId,Position

You should get results like that in Figure 2.

Verifying the Results from Step 2

Please note that concatenation of last field partitioned by EmpId,StatementId is: 10o10oa, 10on, 00o00oa, 00on. These strings are RPN expressions ready for literal substitution.

Examining Step 3

Literal substitution is executed through a new recursive CTE. The anchor selects the first element of each sequence partitioned by EmpId,StatementId (as seen in step 2). The recursive member finds the next element of each sequence. If the element is a Boolean value (1 or 0), it's simply concatenated to the value of the previous step. If the element is an operator (o, a, or n), the Boolean values concatenated by the previous steps are replaced with the result of the Boolean operator evaluation.

After the recursive CTE cleans the results from the intermediate steps, the last statement presents the final results. Figure 3 shows those results.

Examining the Final Results

A Powerful Combination

As you've seen, it's possible to evaluate Boolean propositions in a single T-SQL query by combining recursive CTE and Reverse Polish notation. Although I showed you how to use this technique to evaluate business rules for employees, you can generalize and apply it to other situations in which a complex parenthesized expression needs to be evaluated.


Tommaso CapassoTommaso Capasso is an MCSA: SQL Server 2012 certified professional. He currently works as a consultant for Avanade, a joint venture of Microsoft and Accenture. He specializes in Microsoft technologies but in general likes problem solving and algorithms.