Have Geek Brain

Ordering a recursive result set in SQL Server

I am having difficulty constructing a query that returns an XML style hierarchy.

We have a database table that contains the URL hierarchy for our website. The table contains columns: ID, URL, DisplayName, ParentID, ItemOrder

The parent id forms a recursive link between the current element and the parent. The item must be positioned below its parent in the hierarchy, and it must also be ordered using the position order against items at the same level in the hierarchy.

I managed to get a recursive query so that it checks the hierarchy sequentially, but I can't seem to order this in order either.

My current request is below:

WITH Parents AS
(
SELECT MenuItemId, URL, ParentItemId, ItemOrder
FROM CambsMenu

UNION ALL

SELECT si.MenuItemId, si.URL, si.ParentItemId, si.ItemOrder
FROM CambsMenu si INNER JOIN Parents p
ON si.ParentItemId = p.MenuItemId
)

SELECT DISTINCT *
FROM Parents
+2


a source to share


6 answers


Is the number of siblings a known value? Is the number of levels known? If so, you can perform operations on the ItemOrder to ensure that each item has a unique ItemOrder, and then simply sort by that value.

For example, suppose there can be no more than 10 child elements in any item (ItemOrder is in the range 0 to 9) and no more than 5 levels. Now I have to make the first parent ItemOrder 10,000 times when it is ordered by the current order, ant it childer the ItemOrder will be 1,000 times the current ItemOrder plus its parent ItemOrder, etc., removing 0 every time you go down a level ...



WITH Parents AS
(
SELECT MenuItemId,
    URL,
    ParentItemId,
    (ItemOrder * 10000) AS ItemOrder,
    10000 AS Multiplier
FROM CambsMenu
WHERE ParentItemId IS NULL

UNION ALL

SELECT si.MenuItemId,
    si.URL,
    si.ParentItemId,
    (p.ItemOrder + si.ItemOrder * p.Multiplier/ 10) as ItemOrder,
    (p.Multiplier / 10) as Multiplier
FROM CambsMenu si INNER JOIN Parents p
ON si.ParentItemId = p.MenuItemId
)

SELECT * FROM Parents ORDER BY ItemOrder

If the number of levels or children is unknown, you can go in a similar way, but instead of creating a numeric ItemOrder, you can construct an ItemOrder string ensuring that string '1.10.20' is less than string '2.1

+2


a source


The usual hierarchical approach:

select *
into emp
from 
(values
(1, 'President', NULL),
(2, 'Vice President', 1),
(3, 'CEO', 2),
(4, 'CTO', 2),
(5, 'Group Project Manager', 4),
(6, 'Project Manager 1', 5),
(7, 'Project Manager 2', 5),
(8, 'Team Leader 1', 6),
(9, 'Software Engineer 1', 8),
(10, 'Software Engineer 2', 8),
(11, 'Test Lead 1', 6),
(12, 'Tester 1', 11),
(13, 'Tester 2', 11),
(14, 'Team Leader 2', 7),
(15, 'Software Engineer 3', 14),
(16, 'Software Engineer 4', 14),
(17, 'Test Lead 2', 7),
(18, 'Tester 3', 17),
(19, 'Tester 4', 17),
(20, 'Tester 5', 17)
) as x(emp_id, emp_name, mgr_id)

Query:

with recursive org(emp_id, emp_name, emp_level, mgr_id, sort) as
(
 select  
  a.emp_id, a.emp_name, 0, a.mgr_id,  
  a.emp_name
 from emp a
 where a.mgr_id is null

 union all

 select 
  b.emp_id, b.emp_name, emp_level + 1, b.mgr_id, 

  sort || ' : ' || b.emp_name 

 from emp b
 join org on org.emp_id = b.mgr_id
)
select 
 emp_id, repeat(' ', emp_level * 2) || emp_name as emp_name, sort 
from org
order by sort

Output:

 emp_id |            emp_name             |                                                        sort                                                        
--------+---------------------------------+--------------------------------------------------------------------------------------------------------------------
      1 | President                       | President
      2 |   Vice President                | President : Vice President
      3 |     CEO                         | President : Vice President : CEO
      4 |     CTO                         | President : Vice President : CTO
      5 |       Group Project Manager     | President : Vice President : CTO : Group Project Manager
      6 |         Project Manager 1       | President : Vice President : CTO : Group Project Manager : Project Manager 1
      8 |           Team Leader 1         | President : Vice President : CTO : Group Project Manager : Project Manager 1 : Team Leader 1
      9 |             Software Engineer 1 | President : Vice President : CTO : Group Project Manager : Project Manager 1 : Team Leader 1 : Software Engineer 1
     10 |             Software Engineer 2 | President : Vice President : CTO : Group Project Manager : Project Manager 1 : Team Leader 1 : Software Engineer 2
     11 |           Test Lead 1           | President : Vice President : CTO : Group Project Manager : Project Manager 1 : Test Lead 1
     12 |             Tester 1            | President : Vice President : CTO : Group Project Manager : Project Manager 1 : Test Lead 1 : Tester 1
     13 |             Tester 2            | President : Vice President : CTO : Group Project Manager : Project Manager 1 : Test Lead 1 : Tester 2
      7 |         Project Manager 2       | President : Vice President : CTO : Group Project Manager : Project Manager 2
     14 |           Team Leader 2         | President : Vice President : CTO : Group Project Manager : Project Manager 2 : Team Leader 2
     15 |             Software Engineer 3 | President : Vice President : CTO : Group Project Manager : Project Manager 2 : Team Leader 2 : Software Engineer 3
     16 |             Software Engineer 4 | President : Vice President : CTO : Group Project Manager : Project Manager 2 : Team Leader 2 : Software Engineer 4
     17 |           Test Lead 2           | President : Vice President : CTO : Group Project Manager : Project Manager 2 : Test Lead 2
     18 |             Tester 3            | President : Vice President : CTO : Group Project Manager : Project Manager 2 : Test Lead 2 : Tester 3
     19 |             Tester 4            | President : Vice President : CTO : Group Project Manager : Project Manager 2 : Test Lead 2 : Tester 4
     20 |             Tester 5            | President : Vice President : CTO : Group Project Manager : Project Manager 2 : Test Lead 2 : Tester 5
(20 rows)

Now let's override sorting in group project managers, let's make Project Manager 2 to 1, and Project Manager 1 after Project Manager 2. Let's also make tester 4 to 3, and tester 3 after tester 4

alter table emp add column order_override int null;

update emp set order_override = 1 where emp_id = 7; -- PM 2
update emp set order_override = 2 where emp_id = 6; -- PM 1

update emp set order_override = 1 where emp_id = 19; -- Tester 4
update emp set order_override = 2 where emp_id = 18; -- Tester 3

Query:

with recursive org(emp_id, emp_name, emp_level, mgr_id, sort) as
(
 select  
  a.emp_id, a.emp_name, 0, a.mgr_id,  
  a.emp_name
 from emp a
 where a.mgr_id is null

 union all

 select 
  b.emp_id, b.emp_name, emp_level + 1, b.mgr_id, 

  sort || ' : ' || coalesce( lpad(order_override::text, 10, '0'), b.emp_name )
 from emp b
 join org on org.emp_id = b.mgr_id
)
select 
 emp_id, repeat(' ', emp_level * 2) || emp_name as emp_name, sort 
from org
order by sort

Output:

 emp_id |            emp_name             |                                                    sort                                                     
--------+---------------------------------+-------------------------------------------------------------------------------------------------------------
      1 | President                       | President
      2 |   Vice President                | President : Vice President
      3 |     CEO                         | President : Vice President : CEO
      4 |     CTO                         | President : Vice President : CTO
      5 |       Group Project Manager     | President : Vice President : CTO : Group Project Manager
      7 |         Project Manager 2       | President : Vice President : CTO : Group Project Manager : 0000000001
     14 |           Team Leader 2         | President : Vice President : CTO : Group Project Manager : 0000000001 : Team Leader 2
     15 |             Software Engineer 3 | President : Vice President : CTO : Group Project Manager : 0000000001 : Team Leader 2 : Software Engineer 3
     16 |             Software Engineer 4 | President : Vice President : CTO : Group Project Manager : 0000000001 : Team Leader 2 : Software Engineer 4
     17 |           Test Lead 2           | President : Vice President : CTO : Group Project Manager : 0000000001 : Test Lead 2
     19 |             Tester 4            | President : Vice President : CTO : Group Project Manager : 0000000001 : Test Lead 2 : 0000000001
     18 |             Tester 3            | President : Vice President : CTO : Group Project Manager : 0000000001 : Test Lead 2 : 0000000002
     20 |             Tester 5            | President : Vice President : CTO : Group Project Manager : 0000000001 : Test Lead 2 : Tester 5
      6 |         Project Manager 1       | President : Vice President : CTO : Group Project Manager : 0000000002
      8 |           Team Leader 1         | President : Vice President : CTO : Group Project Manager : 0000000002 : Team Leader 1
      9 |             Software Engineer 1 | President : Vice President : CTO : Group Project Manager : 0000000002 : Team Leader 1 : Software Engineer 1
     10 |             Software Engineer 2 | President : Vice President : CTO : Group Project Manager : 0000000002 : Team Leader 1 : Software Engineer 2
     11 |           Test Lead 1           | President : Vice President : CTO : Group Project Manager : 0000000002 : Test Lead 1
     12 |             Tester 1            | President : Vice President : CTO : Group Project Manager : 0000000002 : Test Lead 1 : Tester 1
     13 |             Tester 2            | President : Vice President : CTO : Group Project Manager : 0000000002 : Test Lead 1 : Tester 2
(20 rows)


Without sort column in data projection:

with recursive org(emp_id, emp_name, emp_level, mgr_id, sort) as
(
 select  
  a.emp_id, a.emp_name, 0, a.mgr_id,  
  a.emp_name
 from emp a
 where a.mgr_id is null

 union all

 select 
  b.emp_id, b.emp_name, emp_level + 1, b.mgr_id, 

  sort || ' : ' || coalesce( lpad(order_override::text, 10, '0'), b.emp_name )
 from emp b
 join org on org.emp_id = b.mgr_id
)
select 
 emp_id, repeat(' ', emp_level * 2) || emp_name as emp_name
from org
order by sort

Output:

 emp_id |            emp_name             
--------+---------------------------------
      1 | President
      2 |   Vice President
      3 |     CEO
      4 |     CTO
      5 |       Group Project Manager
      7 |         Project Manager 2
     14 |           Team Leader 2
     15 |             Software Engineer 3
     16 |             Software Engineer 4
     17 |           Test Lead 2
     19 |             Tester 4
     18 |             Tester 3
     20 |             Tester 5
      6 |         Project Manager 1
      8 |           Team Leader 1
      9 |             Software Engineer 1
     10 |             Software Engineer 2
     11 |           Test Lead 1
     12 |             Tester 1
     13 |             Tester 2
(20 rows)

Project Manager 2 comes before Project Manager 1. Tester 4 comes before Tester 3

The method is wrapped in numeric text substitution for b.name if order_override (non-null) is present:

sort || ' : ' || coalesce( lpad(order_override::text, 10, '0'), b.emp_name )

Above Postgres code, to convert to Sql Server, remove the word RECURSIVE

, change REPEAT

to REPLICATE

, ||

to +

.

Equivalent...

lpad(order_override::text, 10, '0')

... there is:

RIGHT( REPLICATE('0',10) + CONVERT(VARCHAR, order_override), 10)
+9


a source


Thanks for all your answers!

Just for completeness, here is the final solution I came up with. It creates a string that is split into dot intersections. The solution below only supports up to 9999 items in the root node, but you can easily extend it by increasing the number of leading zeros simply by changing the number in the STR command (ItemOrder, 4)

WITH Parents AS
(
SELECT MenuItemId,
    URL,
    ParentItemId,
    DisplayName,
    OpenInNewWindow,
    ItemOrder,
    CAST((REPLACE(STR(ItemOrder,4),' ','0')) AS nvarchar(max)) AS OrderString
FROM CambsMenu
WHERE ParentItemId IS NULL

UNION ALL

SELECT si.MenuItemId,
    si.URL,
    si.ParentItemId,
    si.DisplayName,
    si.OpenInNewWindow,
    si.ItemOrder,
    (p.OrderString + '.' + CAST((REPLACE(STR(si.ItemOrder,4),' ','0')) AS nvarchar(max))) AS OrderString
FROM CambsMenu si INNER JOIN Parents p
ON si.ParentItemId = p.MenuItemId
)

SELECT * FROM Parents ORDER BY OrderString ASC
+4


a source 


WITH Parents AS
(
SELECT MenuItemId, URL, ParentItemId, ItemOrder, 0 AS Level, Cast((ItemOrder+1000) as Varchar(MAX)) as MatPath
FROM CambsMenu
WHERE ParentItemId IS NULL

UNION ALL

SELECT si.MenuItemId, si.URL, si.ParentItemId, si.ItemOrder, Level + 1, MathPath + '.' CAST((si.ItemOrder+1000) as Varchar(MAX)
FROM CambsMenu si INNER JOIN Parents p
ON si.ParentItemId = p.MenuItemId
)

SELECT DISTINCT *
FROM Parents
ORDER BY MatPath

EDIT: Answer updated, initially sorting by Level, which was not asked about. Also, the answer is not verified. Updated again, seed query is not filtered to IS NULL

EDIT2: Here's an update that will use floats and a subquery to get the maximum number of leaves / branches; the ItemOrder is supposed to go back from 1, no holes, and restart for each parent. This could be converted back to using integers, since then it would be more obvious how the sort can overflow / lose precision with the number of levels.

WITH Hierarchy AS
(
  SELECT MenuItemID, 
         URL, 
         ParentItemId, 
         ItemOrder,
         0 as level, 
         cast(1 as float) as hord
  FROM CambsMenu
  WHERE ParentItemId IS NULL 
UNION ALL
  SELECT r.MenuItemId, 
         r.URL, 
         r.PrentItemId,
         r.ItemOrder, 
         h.level + 1, 
         h.hord + r.ItemOrder/power(
           (SELECT MAX(n)+1 
            FROM (SELECT count(*) AS n 
                  FROM CambsMenu 
                  GROUP BY ParentItemId) t), h.level+1)
  FROM CambsMenu r INNER JOIN Hierarchy h
  ON r.ParentItemId = h.MenuItemId
)
SELECT *
FROM Hierarchy
ORDER BY hord;
+1


a source


Even though this is an old post, I haven't seen the answer to this question yet, and it doesn't seem to have the flaws that some of the other answers have. I recommend using the RANK () function to properly order the recursive result set. This method is a little more forgiving with wilder data. This solution assumes that you will have no more than 99 subproblems under any recursion result, but it can be easily extended if you have thousands, millions, or even more. Modify it to work with your dataset.

WITH    Forms
          AS (
              SELECT    FormId,
                        CAST(Caption AS VARCHAR(MAX)) AS Caption,
                        1 AS Depth,
                        CAST('01' AS VARCHAR(MAX)) AS [Rank]
              FROM      fx_NavTree
              WHERE     ParentFormId IS NULL
              UNION ALL
              SELECT    nt.FormId,
                        CAST(SPACE(f.Depth * 2) + nt.Caption AS VARCHAR(MAX)) AS Caption,
                        f.Depth + 1 AS Depth,
                        f.[Rank] + '-' + RIGHT('00' + CAST(RANK() OVER (PARTITION BY f.[Rank] ORDER BY nt.SortOrder) AS VARCHAR(MAX)), 2) AS [Rank]
              FROM      fx_NavTree AS nt
              INNER JOIN Forms AS f ON nt.ParentFormId = f.FormId
             )
    SELECT  *
    FROM    Forms
    ORDER BY Forms.[Rank];

In Ben's case, it will try RANK () the ItemOrder column. His solution should look something like this:

WITH Parents AS
(
SELECT MenuItemId,
       CAST(URL as VARCHAR(MAX)) as URL,
       ParentItemId,
       CAST(ItemOrder AS VARCHAR(MAX)) as ItemOrder
FROM CambsMenu

UNION ALL

SELECT si.MenuItemId,
       CAST(si.URL AS VARCHAR(MAX)) as URL,
       si.ParentItemId,
       p.ItemOrder + '-' + RIGHT('00' + CAST(RANK() OVER (PARTITION BY 
p.ItemOrder ORDER BY si.ItemOrder) AS VARCHAR(MAX)), 2) AS ItemOrder
FROM CambsMenu si INNER JOIN Parents p
ON si.ParentItemId = p.MenuItemId
)

SELECT DISTINCT *
FROM Parents
+1


a source


SQL does not support the type "hierarchy" or "tree" or "graph" as the SQL / relational model was essentially invented to extract (need) these obsolete types.

You wrote a query that computes what is known in mathematical terms as "transitive closure". I doubt this is really what you want. If the relation ("table") has pairs (1 2) and (2 3), then your query will include the result pair (1 3). However (in this example) I suspect that you do not want the result of your XML style to include a tag containing number 3 as direct child number 1 ...

I suspect what you most likely want to achieve is using the GROUP operator of relational algebra. Caveat: this is not the same as "GROUP BY" (relational algebra's GROUP statement creates tables containing columns whose value is the table itself, for example a table containing all the direct children of some parent) and it is likely that your particular DBMS does not support it, in which case you will be largely "abandoned by your DBMS" and "with no choice but to code all the jokes (by which I mean recursion in particular) yourself."

0


a source






More articles:


All Articles