自上而下的树postgres的递归路径聚合和CTE查询

Question

我正在尝试编写一个查询,以生成给定根的树中所有节点的列表,以及路径(使用父级给他们孩子的名称)到达那里的路径.我工作的递归CTE是直接来自这里的文档的教科书CTE ,然而,事实证明在这种情况下使路径工作很困难.

在git模型之后,由于遍历树创建的路径,父母会将名称提供给子级.这意味着映射到git的树结构等子id.

我一直在网上寻找递归查询的解决方案,但它们似乎都包含使用父ID或物化路径的解决方案,这些都会破坏Rich Hickey的数据库作为价值谈话的结构共享概念.

目前的实施

想象一下,对象表很简单(为简单起见,我们假设整数id):

drop table if exists objects;
create table objects (
    id INT,
    data jsonb
);

--       A
--     /   \
--    B     C
--   /   \    \
--  D     E    F

INSERT INTO objects (id, data) VALUES
  (1, '{"content": "data for f"}'),  -- F
  (2, '{"content": "data for e"}'),  -- E
  (3, '{"content": "data for d"}'),  -- D
  (4, '{"nodes":{"f":{"id":1}}}'),               -- C
  (5, '{"nodes":{"d":{"id":2}, "e":{"id":3}}}'), -- B
  (6, '{"nodes":{"b":{"id":5}, "c":{"id":4}}}')  -- A
  ;

drop table if exists work_tree;
create table work_tree (
    id INT NOT NULL,
    path text,
    ref text,
    data jsonb,
    primary key (ref, id) -- TODO change to ref, path
);

create or replace function get_nested_ids_array(data jsonb) returns int[] as $$
  select array_agg((value->>'id')::int) as nested_id
  from jsonb_each(data->'nodes')
$$ LANGUAGE sql STABLE;

create or replace function checkout(root_id int, ref text) returns void as $$
  with recursive nodes(id, nested_ids, data) AS (
      select id, get_nested_ids_array(data), data
      from objects
      where id = root_id
      union
      select child.id, get_nested_ids_array(child.data), child.data
      from objects child, nodes parent
      where child.id = ANY(parent.nested_ids)
  )
  INSERT INTO work_tree (id, data, ref)
  select id, data, ref from nodes
$$ language sql VOLATILE;

SELECT * FROM checkout(6, 'master');
SELECT * FROM work_tree;

如果您熟悉,这些对象的data属性看起来类似于git blobs/trees,将名称映射到id或存储内容.所以想象你想创建一个索引,所以,在"checkout"之后,你需要查询节点列表,以及可能生成工作树或索引的路径:

电流输出:

id    path    ref          data
6     NULL    master       {"nodes":{"b":{"id":5}, "c":{"id":4}}}
4     NULL    master       {"nodes":{"d":{"id":2}, "e":{"id":3}}}
5     NULL    master       {"nodes":{"f":{"id":1}}}
1     NULL    master       {"content": "data for d"}
2     NULL    master       {"content": "data for e"}
3     NULL    master       {"content": "data for f"}

期望的输出:

id    path    ref          data
6      /       master      {"nodes":{"b":{"id":5}, "c":{"id":4}}}
4      /b      master      {"nodes":{"d":{"id":2}, "e":{"id":3}}}
5      /c      master      {"nodes":{"f":{"id":1}}}
1      /b/d    master      {"content": "data for d"}
2      /b/e    master      {"content": "data for e"}
3      /c/f    master      {"content": "data for f"}

path在这种情况下聚合的最佳方式是什么？我知道get_nested_ids_array当我进行递归查询时,我在调用时会压缩信息,因此不确定这种自上而下的方法如何正确地与CTE聚合.

编辑用于儿童ID的用例

解释为什么我需要使用子ID而不是父亲:

想象一下这样的数据结构:

      A
    /   \
   B     C
 /   \    \
D     E    F

如果您对其进行了修改F,则只需添加一个新的根节点A'和子节点C',并F'保留旧树:

     A'    A
   /   \ /   \
  C'    B     C
 /     /   \    \
F'    D     E    F

如果你进行了删除,你只需要添加一个A"只指向的新根,如果你需要时间旅行B你仍然拥有A它(并且它们共享相同的对象,就像git一样!):

 A"  A
  \ /   \
   B     C
 /   \    \
D     E    F

因此,实现这一目标的最佳方式似乎是儿童艾滋病,因此儿童可以拥有多个父母 - 跨越时空!如果您认为还有另一种方法可以实现这一目标,请告诉我!

编辑#2案例不使用parent_ids

使用parent_ids具有级联效果,需要编辑整个树.例如,

      A
    /   \
   B     C
 /   \    \
D     E    F

如果您进行了修改F,您仍然需要一个新的根A'来维护不变性.如果我们使用parent_ids,那么这意味着既B和C现在有一个新的母公司.因此,您可以看到它如何在整个树中涟漪,需要触及每个节点:

      A              A' 
    /   \          /   \
   B     C        B'     C'
 /   \    \      /   \    \
D     E    F    D'    E'   F'

编辑#3使用案例为父母给孩子们起名字

我们可以进行一个递归查询,其中对象存储自己的名称,但我问的问题是关于构建一个路径,其中名称是从父母那里给孩子的.这是建模一个类似于git树的数据结构,例如,如果你看到下图所示的这个git图,在第3次提交中有一个树(一个文件夹)bak指向原始根,它表示所有文件的文件夹.第一次提交.如果该根对象具有自己的名称,则无法实现此目的,只需添加引用即可.这就是git的美妙之处,就像对哈希进行引用并为其命名一样简单.

这就是我正在建立的关系,这就是jsonb数据结构存在的原因,它是提供从名称到id的映射(在git的情况下为hash).我知道它并不理想,但它确实提供了哈希映射.如果有另一种方法可以创建名称到id的映射,从而为父母在自上而下的树中给孩子们命名的方式,我全都耳朵!

任何帮助表示赞赏!

Answer 1

存储节点的父节点而不是其子节点。这是一个更简单、更清晰的解决方案，您不需要结构化数据类型。

这是一个示例模型，其数据与问题中的数据相同：

create table objects (
    id int primary key,
    parent_id int,
    label text,
    content text);

insert into objects values
(1, 4, 'f', 'data for f'),
(2, 5, 'e', 'data for e'),
(3, 5, 'd', 'data for d'),
(4, 6, 'c', ''),
(5, 6, 'b', ''),
(6, 0, 'a', '');

还有一个递归查询：

with recursive nodes(id, path, content) as (
    select id, label, content
    from objects
    where parent_id = 0
union all
    select o.id, concat(path, '->', label), o.content
    from objects o
    join nodes n on n.id = o.parent_id
)
select *
from nodes
order by id desc;

 id |  path   |  content   
----+---------+------------
  6 | a       | 
  5 | a->b    | 
  4 | a->c    | 
  3 | a->b->d | data for d
  2 | a->b->e | data for e
  1 | a->c->f | data for f
(6 rows)

带有 的变体children_ids。

drop table if exists objects;
create table objects (
    id int primary key,
    children_ids int[],
    label text,
    content text);
insert into objects values
(1, null, 'f', 'data for f'),
(2, null, 'e', 'data for e'),
(3, null, 'd', 'data for d'),
(4, array[1], 'c', ''),
(5, array[2,3], 'b', ''),
(6, array[4,5], 'a', '');
with recursive nodes(id, children, path, content) as (
    select id, children_ids, label, content
    from objects
    where id = 6
union all
    select o.id, o.children_ids, concat(path, '->', label), o.content
    from objects o
    join nodes n on o.id = any(n.children)
)
select *
from nodes
order by id desc;

 id | children |  path   |  content   
----+----------+---------+------------
  6 | {4,5}    | a       | 
  5 | {2,3}    | a->b    | 
  4 | {1}      | a->c    | 
  3 |          | a->b->d | data for d
  2 |          | a->b->e | data for e
  1 |          | a->c->f | data for f
(6 rows)