4

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

我有 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
ATTR3ANULL
ATTR4

现在的问题：

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

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

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

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

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

4

2 回答 2

2

像这样创建表：

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);

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

于 2012-04-05T16:12:58.107 回答
0

首先，将树的级别保存为integernot as (redundant and inappropriate) text。
该表如下所示：

CREATE TABLE entity (
  name   text NOT NULL PRIMARY KEY
 ,level  int  NOT NULL
 ,parent text
 ,cost   int  NOT NULL);

询问：

WITH RECURSIVE val(root, leaf) AS (
    VALUES                          -- provide values here
     ('A'::text, 'D'::text)
    ,('D',       'P')
    ), x AS (
    SELECT v.root   AS name
          ,v.root   AS path
          ,r.cost   AS total
          ,1        AS path_len
          ,l.level - r.level AS len -- as break condition
    FROM   val    v
    JOIN   entity r ON r.name = root
    JOIN   entity l ON l.name = leaf

    UNION  ALL
    SELECT e.name                -- AS parent
          ,x.path || '-' || e.name -- AS path
          ,x.total + e.cost      -- AS total
          ,x.path_len + 1        -- AS path_len
          ,x.len                 -- AS len
    FROM   x
    JOIN   entity e ON e.parent = x.name
    WHERE  x.path_len <= x.len
    )
SELECT x.path, x.total
FROM   x
JOIN   val v ON x.name = v.leaf AND x.path_len > 1
ORDER  BY x.total DESC
LIMIT  1;

结果：

path  | total
------+-------
A-B-D | 101

在 sqlfiddle 演示。

要点

  • VALUES提供值更快/更简单/更直观。

  • 使用UNION ALL代替UNION，否则递归联合必须检查（在这种情况下不存在）重复每次迭代。

  • 不包括列root，leaf在递归 CTE 中，它们是自重的。

  • 不需要嵌套WITH子句。您可以在WITH RECURSIVE子句中使用普通的 CTE。

  • 对性能最重要的是：在您的模型中，您事先知道路径的长度。将其用作中断条件，并且不要计算所有通往苦尽头的路径——这对于大树来说可能非常昂贵。

  • finalSELECT也可以大大简化，不需要聚合函数。加入您的价值观并选择正确的道路。这样，您可以根据需要轻松地在结果中显示任何或所有列。

于 2012-06-03T14:42:11.197 回答