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

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

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

我一直在网上寻找递归查询的解决方案,但它们似乎都包含使用父ID或物化路径的解决方案,这些都会破坏Rich Hickey’s database as value谈论的结构共享概念.

目前的实施

想象一下,对象表很简单(为简单起见,我们假设整数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,ref from nodes
$$language sql VOLATILE;

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

如果您熟悉,这些对象的数据属性看起来类似于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"}

在这种情况下,聚合路径的最佳方法是什么？我知道当我执行递归查询时,当我调用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的映射,从而为父母在自上而下的树中给孩子们命名的方式,我全都耳朵！

任何帮助表示赞赏！

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,'d','data for d'),(4,6,'c',''),(5,'b',(6,'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)

drop table if exists objects;
create table objects (
    id int primary key,children_ids int[],content text);
insert into objects values
(1,null,array[1],array[2,3],array[4,5],'');
with recursive nodes(id,children,children_ids,content
    from objects
    where id = 6
union all
    select o.id,o.children_ids,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)