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

Question

我有一个使用邻接列表模型存储分层信息的表。 （使用自参照关键 - 比如下面这张表可能看起来familiar）：

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层层次结构。

Answer 1

跨越简单邻接列表执行多级查询总是涉及自左连接。制作右对齐表格很容易：

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层层次的工作。

对不起，任意深度查询在邻接列表模型中是不可能的。如果您正在进行这种查询，您应该将模式更改为other models of storing hierarchical information：完整邻接关系（存储所有祖先后代关系），物化路径或嵌套集合之一。

如果类别不会移动很多（这对于像您的示例这样的商店通常是这种情况），我会倾向于嵌套。

Answer 2

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

在Oracle中，如果您使用邻接列表，那么CONNECT BY子句将允许您按照第一顺序遍历树。

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

Answer 3

如前所述，SQL没有干净的方式来实现具有动态变化列数的表。我以前已经使用的仅有的两个解决方案是： 1.一种固定数量的自联接，给列的固定数量（AS每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 

我的天堂”虽然我在这里没有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' 

Answer 4

其实可以用一个商店的过程中的动态SQL来完成。然后，您将受限于存储过程可以做什么。显然，将EXEC结果转化为临时表格是一项挑战，不知道有多少列需要。但是，如果目标是输出到网页或其他用户界面，那么它可能是值得的努力...