[pgsql-jp: 33794] Re: 効率的なSQL について

[Mao Morimoto]

もりもとです。

アルゴリズムは苦手なんですが・・
以前同じようなことを（ＳＱＬではなくてオンメモリで）やったことがあるので、
それを元に少々・・

まず、ノード同士の直接の接続を表すデータを用意します。

  <<table T_NODE>>
GEN  LEFT  RIGHT  HOP
---------------------
1    A     B      1
1    B     C      1
1    B     D      1
1    C     E      1

GENは接続の世代番号、HOPは接続の中継数(+1)です。
ここに、第１世代のRIGHTと第１世代以上のLEFTがおなじ物同士を結びつけた、
第２世代のレコードを作成します。こんなＳＱＬで。

INSERT INTO T_NODE
       ( GEN, LEFT, RIGHT, HOP )
SELECT 2, T1.LEFT, T2.RIGHT, T1.HOP + T2.HOP
FROM   T_NODE T1, T_NODE T2
WHERE  T1.RIGHT = T2.LEFT AND
       T2.GEN >= 1

これで、追加されるレコードは３レコード

GEN  LEFT  RIGHT  HOP
---------------------
2    A     C      2
2    A     D      2
2    B     E      2

次に、第１世代のRIGHTと第２世代以上のLEFTがおなじ物同士を結びつけた、
第３世代のレコードを作成します。こんなＳＱＬで。（上のＳＱＬと２文字違うだけ
です）

INSERT INTO T_NODE
       ( GEN, LEFT, RIGHT, HOP )
SELECT 3, T1.LEFT, T2.RIGHT, T1.HOP + T2.HOP
FROM   T_NODE T1, T_NODE T2
WHERE  T1.RIGHT = T2.LEFT AND
       T2.GEN >= 2

これで、追加されるレコードは１レコード

GEN  LEFT  RIGHT  HOP
---------------------
3    A     E      3

これを、結合するレコードがなくなるまで延々と繰り返します。
繰り返す回数は、中継する回数の最大までなので、１個１個つながりをみていくより
は
だいぶ効率的・・かと。ただし、ループがあると無限ループになってしまうので、
その辺は別途考慮が必要かも・・。
これが全部終われば、ノード間のすべての接続を表すデータができあがるので、
その後でノード間の接続を調べるのは、ずっと効率的、になります。。

- Mao Morimoto
http://blog.yamamaya.com/