将邻接列表层次结构展平为所有路径的列表

Question

将邻接列表层次结构展平为所有路径的列表

9

我有一个使用邻接列表模型存储分层信息的表格。该表格使用自引用键（如下所示的示例）。这个表格看起来可能很熟悉：链接

category_id name                 parent
----------- -------------------- -----------
1           ELECTRONICS          NULL
2           TELEVISIONS          1
3           TUBE                 2
4           LCD                  2
5           PLASMA               2
6           PORTABLE ELECTRONICS 1
7           MP3 PLAYERS          6
8           FLASH                7
9           CD PLAYERS           6
10          2 WAY RADIOS         6

什么是将上述数据“展平”的最佳方法，使其变成类似以下结构的内容？

category_id lvl1        lvl2        lvl3        lvl4
----------- ----------- ----------- ----------- -----------
1           1           NULL        NULL        NULL
2           1           2           NULL        NULL
6           1           6           NULL        NULL
3           1           2           3           NULL
4           1           2           4           NULL
5           1           2           5           NULL
7           1           6           7           NULL
9           1           6           9           NULL
10          1           6           10          NULL
8           1           6           7           8

每一行都代表从层次结构中通过一个“路径”得到的结果，不仅包括叶节点，还包括每个节点。category_id列表示当前节点，而“lvl”列则代表其祖先。当前节点的值必须也在最右边的lvl列中。lvl1列中的值始终代表根节点，lvl2中的值始终代表lvl1的直接子代，以此类推。

如果可能，生成此输出的方法应该是用SQL，并且适用于n级层次结构。

- Aaron Hoffman

对于n层次结构：n是否事先已知？ - David Berger

不，我希望解决方案足够通用，适用于任何层次结构。但是，如果“n”已知，是否有更优雅的解决方案？ - Aaron Hoffman

4个回答

9

如上所述，SQL没有干净的方法来实现具有动态变化列数的表格。我以前使用过的仅有的两个解决方案是： 1. 固定数量的自连接，给出固定数量的列（根据BobInce） 2. 在单个列中生成结果字符串

第二种方法最初听起来很奇怪；将ID存储为字符串？！但是当输出格式化为XML或其他格式时，人们就不会那么介意了。

同样，在SQL中如果要在结果上进行联接，则此方法几乎没有用处。如果结果要提供给应用程序，则非常适合。然而，我个人更喜欢在应用程序中而不是在SQL中进行展平操作。

我被困在一个10英寸的屏幕上，无法访问SQL，因此无法提供经过测试的代码，但基本方法是以某种方式利用递归； - 递归标量函数可以做到这一点 - MS SQL可以使用递归WITH语句来实现（更有效）

CREATE FUNCTION getGraphWalk(@child_id INT)
RETURNS VARCHAR(4000)
AS
BEGIN

  DECLARE @graph VARCHAR(4000)

  -- This step assumes each child only has one parent
  SELECT
    @graph = dbo.getGraphWalk(parent_id)
  FROM
    mapping_table
  WHERE
    category_id = @child_id
    AND parent_id IS NOT NULL

  IF (@graph  IS NULL)
    SET @graph = CAST(@child_id AS VARCHAR(16))
  ELSE
    SET @graph = @graph + ',' + CAST(@child_id AS VARCHAR(16))

  RETURN @graph

END


SELECT
  category_id                         AS [category_id],
  dbo.getGraphWalk(category_id)       AS [graph_path]
FROM
  mapping_table
ORDER BY
  category_id

我已经有一段时间没有使用递归WITH了，但是我会尝试语法，即使我没有SQL来测试任何东西 :)

递归WITH

WITH
  result (
    category_id,
    graph_path
  )
AS
(
  SELECT
    category_id,
    CAST(category_id AS VARCHAR(4000))
  FROM
    mapping_table
  WHERE
    parent_id IS NULL

  UNION ALL

  SELECT
    mapping_table.category_id,
    CAST(result.graph_path + ',' + CAST(mapping_table.category_id AS VARCHAR(16)) AS VARCHAR(4000))
  FROM
    result
  INNER JOIN
    mapping_table
      ON result.category_id = mapping_table.parent_id
)

SELECT
  *
FROM
  result
ORDER BY
  category_id

编辑 - 输出结果相同：

1   '1'
2   '1,2'
3   '1,2,3'
4   '1,2,4'
5   '1,2,5'
6   '1,6'
7   '1,6,7'
8   '1,6,7,8'
9   '1,6,9'

- MatBailie

谢谢。这两种方法都可以（除了你上面提到的差异），但是 SQL 需要稍微调整一下。如果你有机会，请更新它（并请包括输出）。我想做，但我还不能编辑你的答案。 - Aaron Hoffman

1

遍历任意深度的树通常涉及递归过程代码，除非您利用某些DBMS的特殊功能。

在Oracle中，如果您使用相邻列表（如此处所示），CONNECT BY子句将允许您按深度优先顺序遍历树。

如果您使用嵌套集，则左序列号将为您提供访问节点的顺序。

- Walter Mitty

0

实际上可以在存储过程内使用动态SQL完成。但是，使用存储过程会受到一定的限制。很明显，将结果EXEC到临时表中变成了一个挑战，因为不知道要期望多少列。然而，如果目标是输出到Web页面或其他UI，则可能值得付出努力...

- talkamongstyerselves

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- bobince · Accepted Answer

要在简单的邻接列表中执行多级查询，必然涉及到自连接。很容易制作右对齐的表格：

SELECT category.category_id,
    ancestor4.category_id AS lvl4,
    ancestor3.category_id AS lvl3,
    ancestor2.category_id AS lvl2,
    ancestor1.category_id AS lvl1
FROM categories AS category
    LEFT JOIN categories AS ancestor1 ON ancestor1.category_id=category.category_id
    LEFT JOIN categories AS ancestor2 ON ancestor2.category_id=ancestor1.parent
    LEFT JOIN categories AS ancestor3 ON ancestor3.category_id=ancestor2.parent
    LEFT JOIN categories AS ancestor4 ON ancestor4.category_id=ancestor3.parent;

要像你的示例一样左对齐它有点棘手。我想到的是：

SELECT category.category_id,
    ancestor1.category_id AS lvl1,
    ancestor2.category_id AS lvl2,
    ancestor3.category_id AS lvl3,
    ancestor4.category_id AS lvl4
FROM categories AS category
    LEFT JOIN categories AS ancestor1 ON ancestor1.parent IS NULL
    LEFT JOIN categories AS ancestor2 ON ancestor1.category_id<>category.category_id AND ancestor2.parent=ancestor1.category_id
    LEFT JOIN categories AS ancestor3 ON ancestor2.category_id<>category.category_id AND ancestor3.parent=ancestor2.category_id
    LEFT JOIN categories AS ancestor4 ON ancestor3.category_id<>category.category_id AND ancestor4.parent=ancestor3.category_id
WHERE
    ancestor1.category_id=category.category_id OR
    ancestor2.category_id=category.category_id OR
    ancestor3.category_id=category.category_id OR
    ancestor4.category_id=category.category_id;

对于n层级结构，这种方法是行得通的。

抱歉，在邻接列表模型中无法进行任意深度的查询。如果您经常进行这种查询，您应该将模式更改为存储分层信息的其他模型之一：完整的邻接关系（存储所有祖先-后代关系）、材料化路径或嵌套集。

如果类别不经常移动（这通常是像您的示例店铺一样的情况），我会倾向于使用嵌套集。