在带有标记节点的树上遍历给定路径

Question

假设我们有一棵带有标记节点的树，其中每个节点都有一个unique id和一个non-unique标签。树上的路径可以通过标签的有序集合来描述。例如，带有路径描述符，P = ['', 'a', 'a.1', 'a.1.3'] = "/a/a.1/a.1.3"（类似于Unix下的路径）。目的是找到与该路径相对应的节点ID。例如P = 1 -> 2 -> 5 -> 8。

让我们在SQLite中做一个最小的例子，如下：

-- define the nodes
CREATE TABLE nd
    (uid INTEGER PRIMARY KEY,
     label TEXT);

-- note that some nodes might have similar labels (here, 2 and 9) 
INSERT INTO nd
    VALUES (1, '' ), (4, 'd'),
           (3, 'b'), (9, 'a'),
           (2, 'a'), (5, 'a.1'),
           (6, 'a.1.1'), (7, 'a.1.2'), (8, 'a.1.3');

-- define the tree structure (adjacency list)
CREATE TABLE tr
    (child INTEGER REFERENCES nd (uid),
     parent INTEGER REFERENCES nd (uid));

INSERT INTO tr
    VALUES (1, NULL), (4, 1),
            (3, 1), (9, 3), 
            (2, 1), (5, 2),
            (6, 5), (7, 5), (8, 5);


/* Tree structure (+ indicates a node)

       + 1:root
       |
---------------
|      |      |
+ 4:d  + 3:b  + 2:a
       |      |
       + 9:a  + 5:a.1
              |
       ---------------
       |      |      |
       +      +      +
       8      7      6
     a.1.3  a.1.2  a.1.1
*/

一个可以轻松找到id = 1的节点的直接子代]

SELECT tr.child AS uid, nd.label AS label
    FROM tr
    JOIN nd
    ON tr.child = nd.uid
    WHERE tr.parent = 1;

或找到节点1的直接子代'b'的ID：

SELECT tr.child AS uid, nd.label AS label
    FROM tr
    JOIN nd
    ON (tr.parent = 1 AND nd.label = 'b'
        AND tr.child = nd.uid);

现在，我们定义路径描述符P = "/a/a.1/a.1.3"：

CREATE TABLE P (label TEXT);
INSERT INTO P VALUES
    (''), ('a'), ('a.1'), ('a.1.3'); -- path 1/2/5/8

我组成（或想像）一个递归查询以找到相应的uid：

WITH RECURSIVE
trPath (uid, label, depth) AS (
    -- first (uid, label) from the path descriptor
    SELECT nd.uid, nd.label, 1 FROM nd
    WHERE nd.label = (SELECT label FROM P WHERE P.ROWID = 1)

    UNION ALL

    WITH
    -- next uid from path descriptor (only a single element)
    parentLabel (uid) AS (
    SELECT uid FROM nd
    WHERE nd.label = (SELECT P.label FROM P, trPath WHERE P.ROWID = trPath.depth + 1)
    LIMIT 1
    ),
    -- uids of children of current parent 
    childrenIds (uid) AS (
    SELECT child FROM tr
    WHERE tr.parent = (SELECT uid FROM parentLabel)
    ),
    -- uid, label of children of current parent 
    children (uid, label) AS (
    SELECT chl.uid, nd.label FROM childrenIds
    JOIN nd ON (nd.uid = childrenIds.uid)
    )
    SELECT uid, label, trPath.depth + 1 from children, trPath
)
SELECT * FROM trPath;

结果应该是一个类似表的表>

uid | label | depth
1|''|1
2|a|2
5|a.1|3
8|a.1.3|4
但是，它实际上不是有效的SQLite查询，因​​此不起作用。一个人应该如何在SQLite中执行这样的查询？

假设我们有一棵带有标签节点的树，其中每个节点都有唯一的ID和不唯一的标签。树上的路径可以通过标签的有序集合来描述。例如，使用路径描述符，P = ...

Answer 1

这适用于您的示例数据（需要Sqlite 3.25或更高版本：]