CODEWITHSUNDEEP
sql-servert-sqlparent-childcommon-table-expression
Atrus2711
Atrus2711

Reputation: 13

Depth-first tree walk in parent-child table with sibling sorter for a total "sequencer"

A system I use stores hierarchical data in a parent-child table (adjacency table):

Code ParentCode Sorter Caption
A (NULL) 0 ...
B A 0 ...
C A 1 ...
D C 0 ...
E D 0 ...
F C 1 ...
G C 2 ...

The Sorter column determines the sequence of siblings. Codes D, F, G are siblings (= children of same parent), and the sorter may change, e.g. if a new row is inserted and is to be placed before the last sibling. E.g., the last sibling could be a category like "other", and of course "other" is always the last sibling, even if more detailed categories are inserted later.

In short: the tree may grow and change.

For a downstream system, I'd need a "sequencer" of this tree - a depth-first tree-walk that enumerates the rows from node 1 (first root) to last. Can this be done in T-SQL (SQL Server 2016) alone?

I did some earlier experiments with CTE, I managed e.g. to make a CTE for calculating level and FullPath. But these data are unaffected on the sibling sorter; level and Fullpath do not change if first and last sibling changed places. The Sequencer would have to.

As a fall-back, I managed to draw the tree in an Infragistics UltraTree in a C# app, which I then iterated recursively. This works, but is a non-SQL-approach. Can SQL do this job on its own?

Upvotes: 0

Views: 52

Answers (1)

bdcoder
bdcoder

Reputation: 3892

This might help you get started:

CREATE TABLE data_table (
    dt_code VARCHAR(2) NOT NULL,
    dt_parent_code VARCHAR(2),
    dt_sorter INT
);

INSERT data_table VALUES ( 'A', NULL, 0 );
INSERT data_table VALUES ( 'B', 'A',  0 );
INSERT data_table VALUES ( 'C', 'A',  1 );
INSERT data_table VALUES ( 'D', 'C',  0 );
INSERT data_table VALUES ( 'E', 'D',  0 );
INSERT data_table VALUES ( 'F', 'C',  1 );
INSERT data_table VALUES ( 'G', 'C',  2 );

Solution 1: Using a CTE to query - set the dt_code in the WHERE clause to the root value you want to extract from the hierarchy ...

WITH cte ( code, parent_code, level, path )
AS
(

-- Anchor member ...
SELECT dt_code, dt_parent_code, 1 AS level,
 CAST( dt_sorter AS VARCHAR( MAX ) ) AS path
 FROM data_table
 WHERE dt_code = 'A'

UNION ALL

-- Recursive member ...
SELECT dt_code, dt_parent_code, cte.level + 1 AS level,
 CAST( cte.path + '.' + CAST( dt_sorter AS VARCHAR ) AS VARCHAR( MAX ) ) AS path
FROM data_table, cte
WHERE dt_parent_code = cte.code
)
SELECT code, parent_code, level, path
 FROM cte
 WHERE code = cte.code
 ORDER BY path;

Output:

code    parent_code level   path
----    ----------- -----   ----
A       (null)         1    0
B       A              2    0.0
C       A              2    0.1
D       C              3    0.1.0
E       D              4    0.1.0.0
F       C              3    0.1.1
G       C              3    0.1.2

Solution 2: Using ROW_NUMBER() and PARTITION - also handle sorter numbers greater than 0-9:

WITH cte ( code, parent_code, level, path )
AS
(

-- Anchor member ...
SELECT dt_code, dt_parent_code, 1 AS level,
 CAST( RIGHT( '00000' + CONVERT( VARCHAR, ROW_NUMBER() OVER( PARTITION BY dt_parent_code ORDER BY dt_sorter ) ), 6 ) AS VARCHAR( MAX ) ) AS path
 FROM data_table
 WHERE dt_code = 'A'

UNION ALL

-- Recursive member ...
SELECT dt_code, dt_parent_code, cte.level + 1 AS level,
 CAST( cte.path + '.' + RIGHT( '00000' + CONVERT( VARCHAR, ROW_NUMBER() OVER( PARTITION BY dt_parent_code ORDER BY dt_sorter ) ), 6 ) AS VARCHAR( MAX ) ) AS path
FROM data_table, cte
WHERE dt_parent_code = cte.code
)
SELECT code, parent_code, level, path
 FROM cte
 WHERE code = cte.code
 ORDER BY path;

Output:

code    parent_code     level   path
----    -----------     ------  ----
A       (null)             1    000001
B       A                  2    000001.000001
C       A                  2    000001.000002
D       C                  3    000001.000002.000001
E       D                  4    000001.000002.000001.000001
F       C                  3    000001.000002.000002
G       C                  3    000001.000002.000003

Upvotes: 0

Related Questions