深度优先树遍历在具有兄弟排序器的父子表中，用于总体“顺序器”

huangapple
go评论102阅读模式
英文:

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

问题

我使用的系统在父子表（相邻表）中存储分层数据：

代码 父代码 排序器 标题
A (NULL) 0 ...
B A 0 ...
C A 1 ...
D C 0 ...
E D 0 ...
F C 1 ...
G C 2 ...

"排序器"列确定兄弟节点的顺序。代码 D、F、G 是兄弟节点（相同父节点的子节点），排序器可能会更改，例如，如果插入新行并要将其放在最后一个兄弟节点之前。例如，最后一个兄弟节点可以是类别，如“其他”，当然，无论稍后插入了更详细的类别，"其他"始终是最后一个兄弟节点。

简而言之：树可能会增长和变化。

对于下游系统，我需要一个树的“排序器” - 一个深度优先树遍历，从节点1（第一个根节点）到最后一个枚举行。这是否可以仅使用T-SQL（SQL Server 2016）来完成？

我之前尝试过一些使用CTE的实验，例如，我成功地创建了一个用于计算级别和完整路径的CTE。但是这些数据对于兄弟排序器没有影响；如果第一个和最后一个兄弟节点互换位置，级别和完整路径不会改变。排序器必须改变。

作为备用方案，我成功地在C#应用程序中使用Infragistics UltraTree绘制了树形结构，然后进行了递归迭代。这种方法有效，但不是SQL方法。SQL能否独自完成这项工作？

英文:

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?

答案1

得分: 0

以下是翻译好的代码部分：

Solution 1: 使用CTE查询 - 将dt_code设置在WHERE子句中以从层次结构中提取根值...

  1. WITH cte ( code, parent_code, level, path )
  2. AS
  3. (
  5. -- 锚定成员 ...
  6. SELECT dt_code, dt_parent_code, 1 AS level,
  7.  CAST( dt_sorter AS VARCHAR( MAX ) ) AS path
  8.  FROM data_table
  9.  WHERE dt_code = 'A'
  11. UNION ALL
  13. -- 递归成员 ...
  14. SELECT dt_code, dt_parent_code, cte.level + 1 AS level,
  15.  CAST( cte.path + '.' + CAST( dt_sorter AS VARCHAR ) AS VARCHAR( MAX ) ) AS path
  16. FROM data_table, cte
  17. WHERE dt_parent_code = cte.code
  18. )
  19. SELECT code, parent_code, level, path
  20.  FROM cte
  21.  WHERE code = cte.code
  22.  ORDER BY path;

Solution 2: 使用ROW_NUMBER()和PARTITION - 也处理大于0-9的排序号码：

  1. WITH cte ( code, parent_code, level, path )
  2. AS
  3. (
  5. -- 锚定成员 ...
  6. SELECT dt_code, dt_parent_code, 1 AS level,
  7.  CAST( RIGHT( '00000' + CONVERT( VARCHAR, ROW_NUMBER() OVER( PARTITION BY dt_parent_code ORDER BY dt_sorter ) ), 6 ) AS VARCHAR( MAX ) ) AS path
  8.  FROM data_table
  9.  WHERE dt_code = 'A'
  11. UNION ALL
  13. -- 递归成员 ...
  14. SELECT dt_code, dt_parent_code, cte.level + 1 AS level,
  15.  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
  16. FROM data_table, cte
  17. WHERE dt_parent_code = cte.code
  18. )
  19. SELECT code, parent_code, level, path
  20.  FROM cte
  21.  WHERE code = cte.code
  22.  ORDER BY path;
英文:

This might help you get started:

  1. CREATE TABLE data_table (
  2.     dt_code VARCHAR(2) NOT NULL,
  3.     dt_parent_code VARCHAR(2),
  4.     dt_sorter INT
  5. );
  7. INSERT data_table VALUES ( 'A', NULL, 0 );
  8. INSERT data_table VALUES ( 'B', 'A',  0 );
  9. INSERT data_table VALUES ( 'C',	'A',  1 );
  10. INSERT data_table VALUES ( 'D', 'C',  0 );
  11. INSERT data_table VALUES ( 'E',	'D',  0 );
  12. INSERT data_table VALUES ( 'F',	'C',  1 );
  13. 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 ...

  1. WITH cte ( code, parent_code, level, path )
  2. AS
  3. (
  5. -- Anchor member ...
  6. SELECT dt_code, dt_parent_code, 1 AS level,
  7.  CAST( dt_sorter AS VARCHAR( MAX ) ) AS path
  8.  FROM data_table
  9.  WHERE dt_code = 'A'
  11. UNION ALL
  13. -- Recursive member ...
  14. SELECT dt_code, dt_parent_code, cte.level + 1 AS level,
  15.  CAST( cte.path + '.' + CAST( dt_sorter AS VARCHAR ) AS VARCHAR( MAX ) ) AS path
  16. FROM data_table, cte
  17. WHERE dt_parent_code = cte.code
  18. )
  19. SELECT code, parent_code, level, path
  20.  FROM cte
  21.  WHERE code = cte.code
  22.  ORDER BY path;

Output:

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

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

  1. WITH cte ( code, parent_code, level, path )
  2. AS
  3. (
  5. -- Anchor member ...
  6. SELECT dt_code, dt_parent_code, 1 AS level,
  7.  CAST( RIGHT( '00000' + CONVERT( VARCHAR, ROW_NUMBER() OVER( PARTITION BY dt_parent_code ORDER BY dt_sorter ) ), 6 ) AS VARCHAR( MAX ) ) AS path
  8.  FROM data_table
  9.  WHERE dt_code = 'A'
  11. UNION ALL
  13. -- Recursive member ...
  14. SELECT dt_code, dt_parent_code, cte.level + 1 AS level,
  15.  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
  16. FROM data_table, cte
  17. WHERE dt_parent_code = cte.code
  18. )
  19. SELECT code, parent_code, level, path
  20.  FROM cte
  21.  WHERE code = cte.code
  22.  ORDER BY path;

Output:

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

huangapple
  • 本文由 发表于 2023年8月4日 01:50:51
  • 转载请务必保留本文链接：https://go.coder-hub.com/76830499.html
  • common-table-expression
  • parent-child
  • sql-server
  • tsql
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定