主页 / dba / 问题 / 292563
Accepted
Blender
Asked: 2021-06-01 12:36:20 +0800 CST

在循环的情况下如何限制树遍历？

  • 772

所以我想限制树深度遍历（作为最简单的递归杀手工具）。将规范化记录转换为树的示例代码：

CREATE TABLE items (
  item_id     serial PRIMARY KEY,
  title text
);
CREATE TABLE joins (
  id          serial PRIMARY KEY,
  item_id     int,
  child_id    int
);
INSERT INTO items (item_id,title) VALUES
  (1,'PARENT'),
  (2,'LEVEL 2'),
  (3,'LEVEL 3.1'),
  (4,'LEVEL 4.1'),
  (5,'LEVEL 4.2'),
  (6,'LEVEL 3.2');
INSERT INTO joins (item_id, child_id) VALUES
  (1,2),
  (2,3),
  (3,4),
  (3,5),
  (2,6);

WITH RECURSIVE t(item_id, json) AS (
        SELECT item_id, to_jsonb(items)
        FROM items
        WHERE NOT EXISTS (
                SELECT 1
                FROM joins
                WHERE items.item_id = joins.item_id
        )
        UNION ALL
        SELECT parent.item_id, to_jsonb(parent) || jsonb_build_object( 'children', t.json )
        FROM t
        JOIN joins AS j
                ON t.item_id = j.child_id
        JOIN items AS parent
                ON j.item_id = parent.item_id
)
SELECT item_id, jsonb_pretty(json)
FROM t
WHERE item_id = 1;

由于这个美丽的答案，它起作用了。现在想象我们有

INSERT INTO joins (item_id, child_id) VALUES
  (1,2),
  (2,3),
  (3,1);

所以我们得到了一个循环1->2->3->1，我想使用限制器来限制它的输出——我希望我的所有树都不大于我给这个树构造函数设置的深度 X。如何在 postgres 13+ 中做这样的事情？

postgresql recursive

2 个回答

  1. 从您的问题中我并不完全清楚您是否主要想限制深度遍历，或者实际上您是否真的想要一个递归循环的解决方案，如果可能的话。我选择了后者。

    您可以做的是在 rCTE 中添加一个额外的列，它将升序连接在一起。然后检查新项目的递归连接，它已经不在数组中。

    幸运的是，Postgres 有数组，它可以简化事情（否则你需要对所有内容进行字符串化）。

    WITH RECURSIVE t(item_id, json, items) AS (
        SELECT
            item_id,
            to_jsonb(items),
            ARRAY[items.item_id]
        FROM items
        WHERE NOT EXISTS (
                SELECT 1
                FROM joins
                WHERE items.item_id = joins.item_id
        )
        UNION ALL
        SELECT
            parent.item_id,
            to_jsonb(parent) || jsonb_build_object( 'children', t.json ),
            array_append(t.items, parent.item_id)
        FROM t
        JOIN joins AS j
                ON t.item_id = j.child_id
                AND NOT EXISTS (SELECT j.item_id
                                INTERSECT
                                SELECT * FROM unnest(t.items))
        JOIN items AS parent
                ON j.item_id = parent.item_id
)
SELECT item_id, jsonb_pretty(json)
FROM t
WHERE item_id = 1;

    我使用了这个NOT EXISTS条件，因为一个更简单的条件有问题

    AND j.item_id <> ANY(t.items)
-- or
AND j.item_id <> ANY(SELECT * FROM unnest(t.items))

    由于某种原因，这种语法永远递归，我不太明白为什么。

    • 2
  2. Best Answer

    真的很简单：添加递归级别值并对其进行过滤：

    WITH RECURSIVE t(item_id, json, level) AS (
        SELECT item_id, to_jsonb(items), 1
        FROM items
        WHERE NOT EXISTS (
                SELECT 1
                FROM joins
                WHERE items.item_id = joins.item_id
        )
        UNION ALL
        SELECT parent.item_id, to_jsonb(parent) || jsonb_build_object( 'children', t.json ),
               level + 1
        FROM t
        JOIN joins AS j
                ON t.item_id = j.child_id
        JOIN items AS parent
                ON j.item_id = parent.item_id
        WHERE level < 3
)
SELECT item_id, jsonb_pretty(json)
FROM t
WHERE item_id = 1;
    • 2

相关问题