Ограничить начальные (якорные) значения рекурсивного запроса (с оператором)

Question

Предположим, что мы выполняем рекурсивный запрос, чтобы получить дочерние элементы определенного узла дерева через таблицу смежности дерева, но достаточно получить только одно поддерево .

В качестве примера, давайте создадим таблицу смежности дерева как

CREATE TABLE Tree
       (parent INTEGER,
        child  INTEGER);

INSERT INTO Tree
       VALUES -- (parent -> child)
              (1, 2), (1, 3), (1, 4),
              (2, 5), (2, 11), (3, 9),
              (5, 6), (5, 7),  (5, 8),
              (9, 10), (11, 12);

, а затем сделаем рекурсивный запрос, чтобы получить дочерние элементы узла 2:

WITH RECURSIVE children_i (parent, child)
AS (
   -- anchor/initial values
   VALUES (NULL, 2)
   -- SELECT parent, child FROM Tree WHERE parent = 2 LIMIT 1
   UNION ALL
   -- recursion
   SELECT children_i.child, Tree.child FROM Tree, children_i
   WHERE Tree.parent = children_i.child
   )
SELECT * FROM children_i;

, который выдаст

|2
2|5
2|11
5|6
5|7
5|8
11|12

Теперь, как мы можем ограничить приведенный выше запрос следующим только одиночным поддеревом (скажем, только 2-> 5 -> {6, 7, 8}, а не 2->11)? Я попытался добавить LIMIT к части привязки рекурсии,

WITH RECURSIVE children_i (parent, child)
AS (
   -- anchor/initial values
   SELECT parent, child FROM Tree WHERE parent = 2 LIMIT 1
   UNION ALL
   -- recursion
   SELECT children_i.child, Tree.child FROM Tree, children_i
   WHERE Tree.parent = children_i.child
   )
SELECT * FROM children_i;

, но все же выдает синтаксическую ошибку LIMIT clause should come after UNION ALL not before (SQLite 3.16.2).

Какможно ли достичь этого в SQLite?

Answer 1

Вы можете использовать LIMIT, но вам нужно извлечь его, чтобы отделить cte:

WITH anchor AS (
  SELECT parent, child
  FROM tree
  WHERE parent = 2
  -- ORDER BY ...
  LIMIT 1
), children_i(parent,child) AS (
  -- anchor/initial values
  SELECT parent, child
  FROM anchor
  UNION ALL
  -- recursion
  SELECT c1.child, t1.child
  FROM tree t1
  JOIN children_i c1
    ON t1.parent = c1.child
)
SELECT * FROM children_i;

db <> fiddle demo

Answer 2

То, что вам нужно, это не путь, а поддерево с корневым узлом, являющимся (только) одним из дочерних элементов корня супердерева ...

Вы можете ограничить дочерний элементкорня супердерева с помощью NOT EXISTS и подзапроса, выбирающего все дочерние элементы этого корня, которые меньше в числовом выражении. Например, выбирается только тот ребенок с минимальным значением среди детей.

WITH RECURSIVE children_i
               (parent,
                child)
AS (
-- anchor/initial values
SELECT t1.parent,
       t1.child
       FROM tree t1
       WHERE t1.parent = 2
             AND NOT EXISTS (SELECT *
                                    FROM tree t2
                                    WHERE t2.parent = t1.parent
                                          AND t2.child < t1.child)
UNION ALL
-- recursion
SELECT c1.child,
       t1.child
       FROM tree t1
            INNER JOIN children_i c1
                       ON t1.parent = c1.child)
SELECT *
       FROM children_i;

db <> fiddle