Обход заданного пути в дереве с помеченными узлами

Предположим, что у нас есть дерево с помеченными узлами, где каждый узел имеет уникальный идентификатор и неуникальную метку. Путь в дереве можно описать упорядоченным набором меток; например, с дескриптором пути P = ['', 'a', 'a.1', 'a.1.3'] = "/a/a.1/a.1.3" (аналогично пути в Unix). Цель состоит в том, чтобы найти идентификаторы узлов, которые соответствуют этому пути; например, 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;

Или найдите идентификатор прямого дочернего элемента «b» узла 1:

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?


sqlite recursive-query tree
person AlQuemist    schedule 23.11.2019    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Это работает для ваших образцов данных (требуется Sqlite 3.25 или новее):

WITH RECURSIVE tree AS
  (SELECT child, parent, '' AS label, 1 AS depth FROM tr WHERE parent IS NULL
   UNION ALL
   SELECT tr.child, tr.parent, nd.label, t.depth + 1
   FROM tr
   JOIN tree AS t ON tr.parent = t.child
   JOIN nd ON tr.child = nd.uid)
, path AS (SELECT label, row_number() OVER (ORDER BY label) AS depth FROM p)
SELECT t.child AS uid, t.label, t.depth
FROM tree AS t
JOIN path ON t.label = path.label AND t.depth = path.depth
ORDER BY t.depth;

производство

uid         label       depth     
----------  ----------  ----------
1                       1         
2           a           2         
5           a.1         3         
8           a.1.3       4

Для достижения наилучших результатов создайте индексы для P(label) и tr(parent, child) (или сделайте их первичными ключами).

person Shawn    schedule 24.11.2019
comment
tree воспроизводит все пути в дереве? - person AlQuemist; 24.11.2019
comment
path AS (SELECT label, row_number() OVER (ORDER BY label) AS depth FROM p) перенумеровывает строки P? - person AlQuemist; 24.11.2019
comment
@AlQuemist Нужно пройти по дереву, чтобы вычислить глубину каждого узла, а другой CTE вычисляет глубину каждого сегмента пути. - person Shawn; 24.11.2019
comment
Я думаю, что ключом здесь является несколько JOIN! Я нашел более простое решение. - person AlQuemist; 24.11.2019

arrow_upward
0
arrow_downward

С подсказкой из ответа @Shawn я нашел более простой ответ, который не нуждается в оконных функциях. и использует несколько JOIN:

WITH RECURSIVE
pathT (uid, label, parent, pstr, idx) AS (
    SELECT uid, label, NULL AS parent, CAST(uid AS TEXT) AS pstr, 1 AS idx
    FROM (SELECT * FROM P LIMIT 1) --> take the 1st element of the path descriptor
    JOIN nd USING(label) --> uid of the current label

UNION ALL

    SELECT tr.child, pathT.uid, nd.label,
           pathT.pstr || "/" || CAST(tr.child AS TEXT),
           pathT.idx + 1
    FROM pathT
    JOIN tr ON (pathT.uid = tr.parent) --> uid of a child node
    JOIN nd ON (tr.child = nd.uid) --> label of the child node
    JOIN P  ON (P.label = nd.label) --> label of the child must match that of the current label
    WHERE P.ROWID = pathT.idx + 1 --> take the next element of the path descriptor
)
SELECT * FROM pathT;

который дает:

1|||1|1
2|1|a|1/2|2
5|2|a.1|1/2/5|3
8|5|a.1.3|1/2/5/8|4

Обратите внимание, что для этого не требуется получать все пути в дереве (см. ответ Шона).

Этот приведенный выше запрос эквивалентен

WITH RECURSIVE
pathT (uid, label, parent, pstr, idx) AS (
    SELECT uid, label, NULL AS parent,
           CAST(uid AS TEXT) AS pstr, 1 AS idx
    FROM (SELECT * FROM lP LIMIT 1) --> take the 1st element of the path descriptor
    JOIN nd USING(label) --> uid of the current label

UNION ALL

    SELECT tr.child, pathT.uid, nd.label,
           pathT.pstr || "/" || CAST(tr.child AS TEXT),
           pathT.idx + 1
    FROM pathT, tr, nd, lP
    WHERE pathT.uid = tr.parent --> uid of a child node
      AND tr.child = nd.uid --> label of the child node
      AND lP.label = nd.label --> label of the child must match that of the current label
      AND lP.ROWID = pathT.idx + 1 --> take the next element of the path descriptor
)
SELECT * FROM pathT;

где JOIN заменены фильтром WHERE с несколькими предикатами.

Мне все еще не хватает в SQL правильной for-конструкции, которую можно найти в функциональных языках, таких как Scheme, Racket (Lisp) или Haskell, чтобы можно было легко написать, например:

WITH pathT (uid, label, parent, pstr) AS 
FOR P.label FROM P (
    SELECT tr.child, pathT.uid, nd.label,
           pathT.pstr || "/" || CAST(tr.child AS TEXT)
        FROM pathT
        JOIN tr ON (pathT.uid = tr.parent) --> uid of a child node
        JOIN nd ON (tr.child = nd.uid) --> label of the child node
        JOIN P  ON (P.label = nd.label) --> label of the child must match that of the current label
)
SELECT * FROM pathT;

без какой-либо явной ссылки на индексы строк.

person AlQuemist    schedule 24.11.2019