將鄰接列表層次結構展平爲所有路徑列表

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結果轉化爲臨時表格是一項挑戰，不知道有多少列需要。但是，如果目標是輸出到網頁或其他用戶界面，那麼它可能是值得的努力...