如何自下而上遍历树以计算PostgreSQL中节点值的（加权）平均值？

Question

例如，在PostgreSQL中对整个树求和的典型示例是使用WITH
RECURSIVE（公用表表达式）。但是，这些示例通常从上到下，将树展平，并对整个结果集执行汇总功能。对于我要解决的问题，我没有找到合适的示例（在StackOverflow，Google等上）：

考虑一个不平衡的树，其中每个节点可以具有一个关联的值。大多数值都附加到叶节点，但其他值也可能具有值。如果节点（是否有叶子）具有显式附加的值，则可以直接使用该值，而无需进行进一步的计算（然后可以忽略子树）。如果节点没有值，则应将值计算为其直接子级的平均值。

但是，由于不能保证所有节点都附加值，因此我需要自下而上以获得总平均值。简而言之，从叶子开始，我需要应用AVG()到每组兄弟姐妹，并将此（中间）结果用作父节点的值（如果没有）。该父级的（新）值（明确附加或子级的平均值）又用于下一级别的平均值（父级及其同级兄弟的平均值）的计算中。

情况示例：

A
+- B (6)
+- C
   +- D
      +- E (10)
      +- F (2)
+- H (18)
   +- I (102)
   +- J (301)

我需要计算A的平均值，该平均值应为10（因为(6+6+18)/3 = 10和I，J被忽略）。

Answer 1

您的数据可以存储为：

create table tree(id int primary key, parent int, caption text, node_value int);
insert into tree values
(1, 0, 'A', null),
(2, 1, 'B', 6),
(3, 1, 'C', null),
(4, 3, 'D', null),
(5, 4, 'E', 10),
(6, 4, 'F', 2),
(7, 1, 'H', 18),
(8, 7, 'I', 102),
(9, 7, 'J', 301);

自底向上聚合的最简单方法是递归函数。

create or replace function get_node_value(node_id int)
returns int language plpgsql as $$
declare
    val int;
begin
    select node_value
    from tree 
    where id = node_id
    into val;
    if val isnull then
        select avg(get_node_value(id))
        from tree
        where parent = node_id
        into val;
    end if;
    return val;
end;
$$;

select get_node_value(1);

 get_node_value 
----------------
             10
(1 row)

在这里测试。

在sql函数中可以实现相同的目的。函数代码不是很明显，但是可能比plpgsql快一点。

create or replace function get_node_value_sql(node_id int)
returns int language sql as $$
    select coalesce(
        node_value,
        (
            select avg(get_node_value_sql(id))::int
            from tree
            where parent = node_id
        )
    )
    from tree 
    where id = node_id;
$$;

使用cte从下至上查看树并不是特别复杂。在这种特殊情况下，困难在于必须分别计算每个级别的平均值。

with recursive bottom_up(id, parent, caption, node_value, level, calculated) as (
    select 
        *, 
        0, 
        node_value calculated
    from tree t
    where not exists (
        select id
        from tree
        where parent = t.id)
union all
    select 
        t.*, 
        b.level+ 1,
        case when t.node_value is null then b.calculated else t.node_value end
    from tree t
    join bottom_up b on t.id = b.parent
)

select id, parent, caption, avg(calculated)::int calculated
from (
    select id, parent, caption, level, avg(calculated)::int calculated
    from bottom_up
    group by 1, 2, 3, 4
    ) s
group by 1, 2, 3
order by 1;

在这里测试。