MySql 对具有重复节点的闭包表中的分层数据进行排序

Question

我有一个层次结构，我将其表示为闭包表，如Bill Karwin所述。我正在尝试编写一个查询，该查询将返回排序为深度优先遍历的节点。这个回复可以解决我的问题，除了在我的结构中，一些节点出现不止一次，因为它们有多个父节点。

我的示例数据如下所示：

1 2 5

• • 3 5
    • 4
  • • 6
    • 2
  • • 5

如您所见，节点 2 出现两次，既是根的子项，也是根的孙项。节点 5 作为根的孙子出现两次(每次使用不同的父节点(，然后再次作为曾孙出现，因为它的父节点节点 2 重复出现。

这会将数据设置为闭包表：

CREATE TABLE ancestor_descendant (
  ancestor int NOT NULL,
  descendant int NOT NULL,
  path_length int NOT NULL
);
INSERT INTO ancestor_descendant (ancestor, descendant, path_length) VALUES 
    (1,1,0),(2,2,0),(3,3,0),(4,4,0),(5,5,0),(6,6,0),(1,2,1),(1,3,1),(1,4,1),
    (2,5,1),(3,5,1),(4,6,1),(4,2,1),(1,5,2),(1,6,2),(1,2,2),(1,5,3),(4,5,2);

或作为邻接列表：

CREATE TABLE parent_child (
  parent int NOT NULL,
  child int NOT NULL
);
INSERT INTO parent_child (parent, child) VALUES 
    (1,2),(1,3),(1,4),(2,5),(3,5),(4,2),(4,6);

我可以生成广度优先遍历(尽管 5 只作为孙子出现一次(：

SELECT CONCAT(LPAD('', path_length, '-'), ' ', descendant)
FROM ancestor_descendant
WHERE ancestor = 1
ORDER BY path_length;
1
- 2
- 3
- 4
-- 5
-- 6
-- 2
--- 5

但是我尝试使用面包屑进行深度优先遍历失败了(由于GROUP BY a.descendant，它只显示一次重复的节点(：

SELECT a.descendant, GROUP_CONCAT(b.ancestor ORDER BY b.path_length DESC) AS breadcrumbs
FROM ancestor_descendant a 
INNER JOIN ancestor_descendant b ON (b.descendant = a.descendant) 
WHERE a.ancestor = 1
GROUP BY a.descendant 
ORDER BY breadcrumbs;
1   1
2   1,1,4,1,4,1,2,2
5   1,1,4,1,4,1,3,2,3,2,5,5
3   1,3
4   1,4
6   1,4,6

是否可以使用闭包表表示输出深度优先遍历？

我应该使用替代表示形式吗？我不能使用递归 CTE，因为我仅限于 MySql(它不实现它们(。

Answer 1

我建议将节点id分为两个概念。 一个是用于图形属性的唯一 id(即 ancestor_descendant列表(。 第二个是你在输出上显示的内容。

• 1
  • 2
    • 5
  3 50
  • 4
    • 6
    • 20
  • • 51

然后创建一个映射表：

Id      Value
 1        1
 2        2
20        2
 3        3
 4        4
 5        5
50        5
51        5
 6        6

然后，您可以通过联接回映射表并使用value列而不是id列来获取所需的内容。