Sql Select using CTE to order a recursive data

Question

Please i want a solution for this problem using CTE in SQL Server

Example for the situation

Equation 0 = 0.25*Equation 1
Equation 1 = Equation 2 + Equation 3 + 0.5*Equation 5
Equation 2 = 15 + 40
Equation 3 = Equation 6 + Equation 7
Equation 4 = 10
Equation 5 = 10 + Equation 4
Equation 6 = 10 +5
Equation 7 = Equation 5 + Equation 2

The structure of the tables is

The Element Table

ID     | Name
-------|--------------
0      | Equation 0
1      | Equation 1
2      | Equation 2
3      | Equation 3
4      | Equation 4
5      | Equation 5
6      | Equation 6
7      | Equation 7
---------------------

the table holds all items of each equation

The equation Table

FK     |    Item   |    Type
-------|-----------|------------------
0      |    0.25   |    constant
0      |    *      |    Operator
0      |    1      |    Element
1      |    2      |    Element
1      |    +      |    Operator
1      |    3      |    Element
1      |    +      |    Operator
1      |    0.5    |    constant
1      |    *      |    Operator
1      |    5      |    Element
2      |    15     |    constant
2      |    +      |    Operator
2      |    40     |    constant
…      |           |      
…      |           | 
… etc  |           |        
------------------------------------

if the type is element this means it is an element item

is there any sql statement result to the correct order that i must use to calculate these equations one by one without using recursive functions because it is limited in SQL the alternative is to calculate the last equation without any requirements then calculate the upper ones as when i need an equation i find it calculated already without recursing the equations

i need the sql select statement to produce the following order

Equation 2
Equation 6
Equation 4
Equation 5
Equation 7
Equation 3
Equation 1
Equation 0

i ordered them by eye because it is simple example is there any select statement is used to do so or the user must order them manually ???

---

• ... Update

  1. with a fully working test scenario

The Script to create tables

/****** Object:  Table [dbo].[Element]    Script Date: 26/03/2017 11:10:10 م ******/
SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
CREATE TABLE [dbo].[Element](
    [Id] [int] NOT NULL,
    [Name] [nvarchar](50) NOT NULL,
 CONSTRAINT [PK_Element] PRIMARY KEY CLUSTERED 
(
    [Id] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY]

GO
/****** Object:  Table [dbo].[Equation]    Script Date: 26/03/2017 11:10:10 م ******/
SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
CREATE TABLE [dbo].[Equation](
    [fk] [int] NOT NULL,
    [Item] [nvarchar](50) NOT NULL,
    [Type] [nvarchar](50) NOT NULL
) ON [PRIMARY]

GO
INSERT [dbo].[Element] ([Id], [Name]) VALUES (0, N'Equation 0')
INSERT [dbo].[Element] ([Id], [Name]) VALUES (1, N'Equation 1')
INSERT [dbo].[Element] ([Id], [Name]) VALUES (2, N'Equation 2')
INSERT [dbo].[Element] ([Id], [Name]) VALUES (3, N'Equation 3')
INSERT [dbo].[Element] ([Id], [Name]) VALUES (4, N'Equation 4')
INSERT [dbo].[Element] ([Id], [Name]) VALUES (5, N'Equation 5')
INSERT [dbo].[Element] ([Id], [Name]) VALUES (6, N'Equation 6')
INSERT [dbo].[Element] ([Id], [Name]) VALUES (7, N'Equation 7')
INSERT [dbo].[Equation] ([fk], [Item], [Type]) VALUES (0, N'0.25', N'constant')
INSERT [dbo].[Equation] ([fk], [Item], [Type]) VALUES (0, N'*', N'Operator')
INSERT [dbo].[Equation] ([fk], [Item], [Type]) VALUES (0, N'1', N'Element')
INSERT [dbo].[Equation] ([fk], [Item], [Type]) VALUES (1, N'2', N'Element')
INSERT [dbo].[Equation] ([fk], [Item], [Type]) VALUES (1, N'+', N'Operator')
INSERT [dbo].[Equation] ([fk], [Item], [Type]) VALUES (1, N'3', N'Element')
INSERT [dbo].[Equation] ([fk], [Item], [Type]) VALUES (1, N'+', N'Operator')
INSERT [dbo].[Equation] ([fk], [Item], [Type]) VALUES (1, N'0.5', N'constant')
INSERT [dbo].[Equation] ([fk], [Item], [Type]) VALUES (1, N'*', N'Operator')
INSERT [dbo].[Equation] ([fk], [Item], [Type]) VALUES (1, N'5', N'Element')
INSERT [dbo].[Equation] ([fk], [Item], [Type]) VALUES (2, N'15', N'constant')
INSERT [dbo].[Equation] ([fk], [Item], [Type]) VALUES (2, N'+', N'Operator')
INSERT [dbo].[Equation] ([fk], [Item], [Type]) VALUES (2, N'40', N'constant')
INSERT [dbo].[Equation] ([fk], [Item], [Type]) VALUES (3, N'6', N'Element')
INSERT [dbo].[Equation] ([fk], [Item], [Type]) VALUES (3, N'+', N'Operator')
INSERT [dbo].[Equation] ([fk], [Item], [Type]) VALUES (3, N'7', N'Element')
INSERT [dbo].[Equation] ([fk], [Item], [Type]) VALUES (4, N'10', N'Constant')
INSERT [dbo].[Equation] ([fk], [Item], [Type]) VALUES (5, N'10', N'Constant')
INSERT [dbo].[Equation] ([fk], [Item], [Type]) VALUES (5, N'+', N'Operator')
INSERT [dbo].[Equation] ([fk], [Item], [Type]) VALUES (5, N'4', N'Element')
INSERT [dbo].[Equation] ([fk], [Item], [Type]) VALUES (6, N'10', N'Constant')
INSERT [dbo].[Equation] ([fk], [Item], [Type]) VALUES (6, N'+', N'Operator')
INSERT [dbo].[Equation] ([fk], [Item], [Type]) VALUES (6, N'5', N'Constant')
INSERT [dbo].[Equation] ([fk], [Item], [Type]) VALUES (7, N'5', N'Element')
INSERT [dbo].[Equation] ([fk], [Item], [Type]) VALUES (7, N'+', N'Operator')
INSERT [dbo].[Equation] ([fk], [Item], [Type]) VALUES (7, N'2', N'Element')

---

2. *

@Gordon Linoff

• ... Thanks a lot for your care but i found some errors using the provided script that i cant solve as it is the first time for me to use CTE

The second script gives me some errors that i cant solve

the first script gives me errors as well that i cant solve

Answer 1

You can try it like this:

WITH Related AS
(
    SELECT *
    FROM Equation AS eq
    LEFT JOIN Element AS e ON eq.[Type]='Element' AND eq.Item=CAST(e.Id AS VARCHAR(10))
    WHERE eq.[Type]='Element' 
)
,Dependecies AS
(
    SELECT e.*
          ,ISNULL(r.Name,'') AS DepName 
    FROM Element AS e
    LEFT JOIN Related AS r ON e.Id=r.fk
)
,recCTE AS
(
    SELECT 1 AS lvl,d.Id,d.Name,d.DepName
    FROM Dependecies AS d
    WHERE d.Name NOT IN(SELECT x.DepName FROM Dependecies AS x)

    UNION ALL

    SELECT r.lvl+1,d.Id,d.Name,d.DepName
    FROM recCTE AS r
    INNER JOIN Dependecies AS d ON r.DepName=d.Name

)
,Ranked AS
(
    SELECT Name
            ,DENSE_RANK() OVER(ORDER BY CASE WHEN DepName='' THEN 1000 ELSE lvl END DESC) AS Rnk
    FROM recCTE
)
SELECT Name,MIN(Rnk) AS Rnk
FROM Ranked
GROUP BY Name
ORDER BY Min(Rnk)

The result

Equation 2  1
Equation 4  1
Equation 6  1
Equation 5  2
Equation 7  3
Equation 3  4
Equation 1  5
Equation 0  6

Explanation

There is a list of CTEs:

• The first CTE will bind the Elements to Equation rows, where the type is Element.
• The second will list all Elements with their dependencies
• The third CTE is a recursive CTE, starting with the element without any dependecies, working down the dependency path
• The next CTE uses DENSE_RANK() OVER() to get the calls ordered

The final SELECT returns each element and the earliest moment it is needed.

Answer 2

Oh, it would be swell if we could express this as:

with cte as (
      select e.fk, 1 as lev
      from equation e
      group by e.fk
      having sum(case when type = 'Element' then 1 else 0 end) = 0
      union all
      select e.fk, max(cte.lev) + 1
      from equation e left join
           cte
           on e.fk = cte.fk
      group by e.fk
      having count(*) = count(cte.fk)
     )

But that is not possible. So, we have to think in terms of string manipulation (I think). This results in putting the dependencies in a string and repeatedly chopping elements off of the string. If I have this right:

with eq as (
       select e.fk,
              stuff( (select ',' + e2.item
                      from equation e2
                      where e2.fk = e.fk and e2.type = 'Element'
                      order by e2.item
                      for xml path ('')
                     ), 1, 1, '') as elements 
       from (select distinct e.fk from equation e) e
      )
      select e.fk, '' as elements_found, 1 as lev
      from eq
      where elements = ''
      union all
      select eq.fk, substring(elements_found, charindex(',', elements_found + ',') + 1), 2 as lev
      from eq join
           cte
           on cte.elements_found like eq.fk + ',%' and eq.fk = cte.fk
      where eq.type = 'Element'
     )
select cte.fk, max(lev)
from cte
group by cte.fk
order by max(lev);