sql - 树木 : Calculate the cost of 2 paths and determine which is more expensive

这是我在这个论坛上的第一个问题，所以我会尽量保持清楚。

我有 1 个表 entity，其中包含以下数据:

ATTR1                ATTR2                 ATTR3                 ATTR4

A                    Level 1                null                   35
B                    Level 2                 A                     34
C                    Level 2                 A                     33
D                    Level 3                 B                     32
E                    Level 3                 B                     31
F                    Level 3                 C                     30
G                    Level 3                 C                     29
H                    Level 4                 D                     28
I                    Level 4                 D                     27
J                    Level 4                 E                     26
K                    Level 4                 E                     25
L                    Level 4                 F                     24
M                    Level 4                 F                     23
N                    Level 4                 G                     22
O                    Level 4                 G                     21
P                    Level 5                 H                     20
Q                    Level 5                 H                     19
R                    Level 5                 H                     18
S                    Level 5                 O                     17

其中 ATTR1 是节点的名称。它也是主键。
其中 ATTR2 是节点的级别。
其中 ATTR3 是节点的父节点的名称。 A 是根，它没有父节点，因此 NULL 。
其中 ATTR4 是节点的成本。

现在的问题是:

给定任何部分 X 和叶节点 Y(即 Y 是 X 的后代)，从根到 X 或 X 的直接后代到 Y 的最昂贵的路径是什么？

换句话说，假设 X 节点是 D ，Y 节点是 P 。从节点到根的路径是 D-B-A 而从叶子到节点的路径是 P-H-D 。

如何计算每条路径的总成本并能够说出哪个更昂贵？

我的方法是做 2 个递归查询，每个路径 1 个查询以找到每个路径的 SUM。问题是我被迫创建了 2 个表并尝试将它们的所有数据放在 1 中。我觉得我已经走到了死胡同，它开始看起来有点长而且不可行。

任何帮助表示赞赏，最好是在 PostgreSQL 语法中。

最佳答案

像这样创建表:

create table entity (attr1 text not null primary key,
                     attr2 text not null,
                     attr3 text,
                     attr4 int not null);

...并用上面显示的数据填充它，你在寻找这样的东西吗？:

with recursive cst as (
with req as (
select 'A'::text as top, 'D'::text as bottom
union all
select 'D'::text, 'P'::text
)
select
    top,
    bottom,
    top as last,
    top as path,
    attr4 as cost
  from req
  join entity on (top = attr1)
union
select
    top,
    bottom,
    attr1,
    path || '-' || attr1,
    cost + attr4
  from cst
  join entity on (attr3 = last)
), res as (
select * from cst where bottom = last
)
select path from res
   where cost = (select max(cost) from res);

诚然，req CTE 作为指定请求的一种方式有点麻烦，但我相信您可以按照自己的意愿来修饰那部分。此外，这总是显示从“上”到“下”而不是“外”到“内”的路径，但我不确定这对您是否重要。无论如何，我认为这应该足够接近你想要的东西。

关于sql - 树木 : Calculate the cost of 2 paths and determine which is more expensive，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10025007/