3

有向グラフのノードを表す次のデータセットがあります。

CREATE TABLE nodes (NODE_FROM VARCHAR2(10),
                    NODE_TO VARCHAR2(10));

INSERT INTO nodes VALUES('GT','TG');
INSERT INTO nodes VALUES('GG','GC');
INSERT INTO nodes VALUES('AT','TG');
INSERT INTO nodes VALUES('TG','GC');
INSERT INTO nodes VALUES('GC','CG');
INSERT INTO nodes VALUES('TG','GG');
INSERT INTO nodes VALUES('GC','CA');
INSERT INTO nodes VALUES('CG','GT');

視覚的表現： http ：//esser.hopto.org/temp/image1.JPG

このデータセットを使用して、ユーザーにレベル（2など）を入力してもらいます。これにより、特定のノードから2「ホップ」離れたすべてのノードが返されます。

NODE_FROM  NODE_TO

TG        GC
TG        GG
AT        TG
GT          TG

http://esser.hopto.org/temp/image2.JPG

私の現在の試みは次のようになります。

SELECT node_from, node_to
  FROM nodes
  WHERE level <= 2   -- Display nodes two "hops" from 'AT'
START WITH node_from = 'AT'
CONNECT BY NOCYCLE PRIOR node_to = node_from
    OR    node_to = PRIOR node_from
GROUP BY node_from, node_to;

http://esser.hopto.org/temp/image3.JPG

ご覧のとおり、GT->TGの関係がありません。

4

2 に答える 2

3

したがって、グラフは次のようになります。

代替テキスト OracleのSTART WITH/CONNECT BY機能を使用して、必要なことを実行できます。ノードGAから開始すると、以下に示すように、グラフ内のすべてのノードに到達できます。

CREATE TABLE edges (PARENT VARCHAR(100), CHILD VARCHAR(100));

insert into edges values ('AT', 'TG');
insert into edges values ('CG', 'GT');
insert into edges values ('GA', 'AT');
insert into edges values ('GC', 'CA');
insert into edges values ('GC', 'CG');
insert into edges values ('GG', 'GC');
insert into edges values ('GT', 'TG');
insert into edges values ('TG', 'GA');
insert into edges values ('TG', 'GC');
insert into edges values ('TG', 'GG');
COMMIT;

SELECT *
  FROM edges
START WITH CHILD = 'GA'
CONNECT BY NOCYCLE PRIOR CHILD = PARENT;

出力：

    PARENT  CHILD
1   TG      GA
2   GA      AT
3   AT      TG
4   TG      GC
5   GC      CA
6   GC      CG
7   CG      GT
8   CG      GT
9   GC      CA

注 グラフにはサイクルがあるため、のNOCYCLE構文を使用することが重要CONNECT BYです。そうしないと、これは機能しません。

OPによる最新の編集に基づく編集された回答

まず、現在のクエリでは。を使用しているため、「2ホップ」とは「最大2ホップ」を意味すると思いますlevel <= 2。正確に2ホップが必要な場合は、である必要がありますlevel = 2。

更新されたグラフ（image2.JPG）には、2ホップかかるATからGTへのパスがないため、クエリは期待どおりの結果を返します。ATからGTまで、移動できますがAT->TG->GC->CG->GT、これは4ホップであり、2より大きいため、その結果が返されません。

2ホップでATからGTに到達できることを期待している場合は、次のようにTGとGTの間にエッジを追加する必要があります。

INSERT INTO nodes VALUES('TG','GT');

これで、クエリを実行すると、次のデータが返されます。

NODE_FROM NODE_TO AT TG TG GC TG GG TG GT

START WITH/CONNECT BYこれは、ノード間にパスがある場合にのみ機能することを忘れないでください。グラフ（上記の新しいエッジを追加する前）には、のパスがAT->TG->GTないため、結果が返されません。

ここで、エッジを追加するTG->ATと、パスが作成されますGT->TG->AT。したがって、その場合、ATはGTから2ホップ離れています（つまり、GTから始まり、ATで終わるという逆の方向に進んでいます）。ただし、これらのパスを見つけるには、START WITH node_from='GT'を設定する必要があります。

開始ノードからレベル<=2ホップ以下のターゲットノードまでのすべてのパスを見つけることが目標である場合は、上記が機能するはずです。

ただし、あるターゲットノードからソースノードに戻るすべてのパスをすべて検索する場合（つまり、からの逆の例GT->TG->AT）、ここでは機能しません。グラフ内のすべてのノードに対してクエリを実行する必要があります。

深さ優先探索START WITH/CONNECT BYを行うと考えてください。開始ノードから可能な限りどこにでも移動します。しかし、それ以上のことはしません。

概要：

上記の制約を考えると、クエリは正常に機能すると思います。パスが返されない理由を説明したGT-TGので、それが理にかなっていることを願っています。

ただし、リバースパスもトラバースしようとしている場合は、すべてのノードをループしてクエリを実行し、毎回ノードを変更する必要があることに注意してくださいSTART WITH。

于 2010-10-18T12:26:56.557 に答える
0

SQLforSmartiesでJoeCelkoのツリーと階層のコピーを取得する必要があるようです。

于 2010-10-18T10:27:35.443 に答える