限制递归查询（with 语句）的初始（锚点）值

Question

假设我们通过树的邻接关系table递归查询获取某个树节点的子节点，但只获取单个子树.

例如，我们将树的邻接关系 table 创建为

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

你似乎想要的不是路径，而是一棵子树，根节点（仅）是超级树根的 children 之一...

您可以通过使用 NOT EXISTS 和子查询选择该根的所有 children 来限制超级树根的 child，它们在数值方面较小。这样只选择children中最小值的child。

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

Answer 2

您可以使用 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

限制递归查询（with 语句）的初始（锚点）值

Limit the initial (anchor) values of a recursive query (with statement)

sqlite

subtree

limit

recursive-query

with-statement