如何在sqlite數據庫中創建樹並將節點轉變爲從其到根的路徑？

Question

我有一個SQLite數據庫和一個表，表示一棵樹。表中的每一行都表示除了鏈接到自身的第一個節點之外的兩個節點之間的關係。

基本上給這個表

BEGIN TRANSACTION; 
CREATE TABLE "unnamed" (key TEXT PRIMARY KEY, value TEXT); 
INSERT INTO `unnamed` (key,value) VALUES ('1','1'); 
INSERT INTO `unnamed` (key,value) VALUES ('2','1'); 
INSERT INTO `unnamed` (key,value) VALUES ('3','10'); 
INSERT INTO `unnamed` (key,value) VALUES ('10','5'); 
INSERT INTO `unnamed` (key,value) VALUES ('5','16'); 
INSERT INTO `unnamed` (key,value) VALUES ('16','8'); 
INSERT INTO `unnamed` (key,value) VALUES ('8','4'); 
INSERT INTO `unnamed` (key,value) VALUES ('4','2'); 
INSERT INTO `unnamed` (key,value) VALUES ('6','3'); 
INSERT INTO `unnamed` (key,value) VALUES ('7','22'); 
INSERT INTO `unnamed` (key,value) VALUES ('22','11'); 
INSERT INTO `unnamed` (key,value) VALUES ('11','34'); 
INSERT INTO `unnamed` (key,value) VALUES ('34','17'); 
INSERT INTO `unnamed` (key,value) VALUES ('17','52'); 
INSERT INTO `unnamed` (key,value) VALUES ('52','26'); 
INSERT INTO `unnamed` (key,value) VALUES ('26','13'); 
INSERT INTO `unnamed` (key,value) VALUES ('13','40'); 
INSERT INTO `unnamed` (key,value) VALUES ('40','20'); 
INSERT INTO `unnamed` (key,value) VALUES ('20','10'); 
INSERT INTO `unnamed` (key,value) VALUES ('9','28'); 
INSERT INTO `unnamed` (key,value) VALUES ('28','14'); 
INSERT INTO `unnamed` (key,value) VALUES ('14','7'); 
COMMIT; 

輸出此表

+------+------------------------------------------------------+ 
| Node | Path             | 
+------+------------------------------------------------------+ 
| 1 | 1             | 
| 2 | 2-1             | 
| 3 | 3-10-5-16-8-4-2-1         | 
| 4 | 4-2-1            | 
| 5 | 5-16-8-4-2-1           | 
| 6 | 6-3-10-5-16-8-4-2-1         | 
| 7 | 7-22-11-34-17-52-26-13-40-20-10-5-16-8-4-2-1   | 
| 8 | 8-4-2-1            | 
| 9 | 9-28-14-7-22-11-34-17-52-26-13-40-20-10-5-16-8-4-2-1 | 
| 10 | 10-5-16-8-4-2-1          | 
| 11 | 11-34-17-52-26-13-40-20-10-5-16-8-4-2-1    | 
| 13 | 13-40-20-10-5-16-8-4-2-1        | 
| 14 | 14-7-22-11-34-17-52-26-13-40-20-10-5-16-8-4-2-1  | 
| 16 | 16-8-4-2-1           | 
| 17 | 17-52-26-13-40-20-10-5-16-8-4-2-1     | 
| 20 | 20-10-5-16-8-4-2-1         | 
... 

我一直在閱讀有關WITH和WITH RECURSIVE，但我不能讓我的頭周圍他們如何工作。

Answer 1

該解決方案構建的路徑從葉根：

WITH RECURSIVE 
    queue(leaf,head,path) AS (
    SELECT CAST(key AS INTEGER) AS leaf, key AS head, key AS path 
     FROM unnamed 
    UNION 
    SELECT queue.leaf AS leaf, unnamed.value AS head, (queue.path||'-'||unnamed.value) AS path 
     FROM unnamed, queue 
     WHERE unnamed.value != queue.head AND unnamed.key = queue.head 
) 
SELECT leaf AS node, path AS path 
    FROM queue 
    WHERE head = 1 
    -- WHERE length(path) = (SELECT MAX(LENGTH(path)) FROM queue AS q WHERE q.leaf = queue.leaf) 
    ORDER BY leaf; 

請點擊這裏閱讀文檔：http://www.sqlite.org/lang_with.html

的初始選擇將所有的密鑰到隊列葉和頭部和路徑。葉被強制轉換爲整數的ORDER BY以後，頭是當前磁頭和路徑將被擴展步驟通過步驟：

SELECT CAST(key AS INTEGER) AS leaf, key AS head, key AS path 
    FROM unnamed 

對於數據庫被查詢以在朝向所述頭部延伸的路徑中的每個隊列項樹的根。 因此，隊列項目的頭部必須匹配一個鍵，而不是樹的根。

WHERE unnamed.value != queue.head AND unnamed.key = queue.head 

兩者的組合路徑延伸以短劃線和添加到隊列：

SELECT queue.leaf AS leaf, unnamed.value AS head, (queue.path||'-'||unnamed.value) AS path 
    FROM unnamed, queue 
    WHERE unnamed.value != queue.head AND unnamed.key = queue.head 

結果包含從葉到根的所有路徑包括所有的中間結果。 所以我們只選擇那些，這在根節點頭/鍵值1.

SELECT leaf AS node, path AS path 
    FROM queue 
    WHERE head = 1 
    ORDER BY leaf; 

結束或者你也可以只選擇那些具有最長的路徑。

SELECT leaf AS node, path AS path 
    FROM queue 
    WHERE length(path) = (SELECT MAX(LENGTH(path)) FROM queue AS q WHERE q.leaf = queue.leaf) 
    ORDER BY leaf;