如何在 sqlite 数据库中获取一棵树并将节点变成从它到根的路径？

Question

我有一个 SQLite 数据库，其中 table 代表一棵树。 table 中的每一行代表两个节点之间的关系，除了第一个链接到自身的节点。

基本上是这样 table

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;

输出这个table

+------+------------------------------------------------------+
| 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

initial-select 将所有键作为叶、头和路径添加到队列中。后面的 ORDER BY 将 Leaf 转换为整数，head 是当前的 head，path 将逐步扩展：

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

结果包含从叶到根的所有路径，包括所有中间结果。因此，我们只 select 那些以 head/key 值为 1 的根节点结束的那些。

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

或者你也可以只select那些路径最长的。

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;

如何在 sqlite 数据库中获取一棵树并将节点变成从它到根的路径？

How do I take a tree in a sqlite db and turn a node into a path going from it to the root?

sql

sqlite

tree

hierarchy