4

これはこのフォーラムでの最初の質問なので、明確にしておきます。

entity次のデータを含む1つのテーブルがあります。

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

確かに、reqリクエストを指定する方法としての CTE は少しハックですが、その部分を希望どおりにきれいにすることができると確信しています。また、これは常に「外側」から「内側」ではなく、「上」から「下」への道を示していますが、それがあなたにとって重要だったかどうかはわかりません. とにかく、これはあなたが望むものにぶつかるのに十分近いはずです.

于 2012-04-05T16:12:58.107 に答える
0

まず、ツリーのレベルをintegernot as (冗長で不適切) として保存します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 に答える