12

約 3500 の洪水制御施設があり、フロー パスを決定するためにネットワークとして表現したいと考えています (基本的に有向グラフ)。私は現在、SqlServer と CTE を使用して、すべてのノードとその上流コンポーネントを再帰的に調べています。これは、上流パスが多く分岐しない限り機能します。ただし、一部のクエリは、物理的にパスを下っていなくても (つまり、「ダウンストリーム」セグメントが 2 つまたは 3 つ)、アップストリームの複雑さが増すため、他のクエリよりも指数関数的に時間がかかります。場合によっては、クエリを強制終了する前に 10 分以上放置しました。私は単純な 2 列のテーブルを使用しています。1 つの列は施設自体で、もう 1 つは最初の列にリストされている施設の上流にある施設です。

現在の機能を使用してインデックスを追加して高速化を試みましたが、違いはありませんでした。また、グラフで可能な接続に関しては、どのノードも複数の上流接続を持つことができ、複数の「下流」ノードから接続することができます。

データに循環がある可能性は確かにありますが、これを確認する良い方法をまだ見つけていません (CTE クエリが最大再帰カウント ヒットを報告した場合を除き、それらは簡単に修正できました)。

それで、私の質問は、この情報を間違って保存しているのでしょうか? 上流のポイントを照会する CTE 以外のより良い方法はありますか?

4

6 に答える 6

6

もちろん、グラフを保存する最良の方法は、ネイティブのグラフ データベースを使用することです:-)

neo4jを見てください。これは Java で実装されており、Python と Ruby のバインディングも備えています。

私は、neo4j を使用してグラフとして表されたドメイン モデルの簡単な例を含む 2 つの Wiki ページを作成しました: assemblyとroles。その他の例は、ドメイン モデリング ギャラリーページにあります。

于 2008-12-07T10:14:31.133 に答える
4

私は治水施設について何も知りません。しかし、私は最初の施設を利用します。一時テーブルと while ループを使用してパスを生成します。

-- 疑似コード
TempTable (LastNode、CurrentNode、N)



DECLARE @intN INT
SET @intN = 1



INSERT INTO TempTable(LastNode, CurrentNode, N)
  -- アップ ストリーム アイテムのないリストに最初のアイテムを挿入します...この初期条件を呼び出します
  SELECT LastNode、CurrentNode、@intN
  あなたのテーブルから
  WHERE ノードには上流に何もありません



WHILE @intN <= 3500
始める
     SEt @intN = @intN + 1
    INSERT INTO TempTable(LastNode, CurrentNode, N)
      SELECT LastNode、CurrentNode、@intN
      あなたのテーブルから
      WHERE LastNode IN (TempTable から CurrentNode を選択 WHERE N = @intN-1)



IF @@ROWCOUNT = 0
     BREAK




終わり

すべてのノードが 1 つの子を指していると仮定すると、その後、これには 3500 回以上の反復は必要ありません。複数のノードが同じアップストリーム プロバイダーを持っている場合は、時間がかかりません。しかし、もっと重要なことは、これによりこれが可能になることです...

SELECT LastNode、CurrentNode、N FROM TempTable ORDER BY N

これにより、プロバイダーにループやその他の問題があるかどうかを確認できます. ちなみに、3500 行はそれほど多くないため、各プロバイダーが別のアップストリーム プロバイダーを指しているという最悪のケースでも、それほど長くはかからないはずです。

于 2008-10-10T15:57:30.547 に答える
3

従来、グラフは行列またはベクトルで表されていました。マトリックスはより多くのスペースを必要としますが、処理が簡単です (あなたの場合は 3500x3500 エントリ); ベクトルはより少ないスペースを必要とします (3500 エントリ、それぞれに接続先のリストがあります)。

それは役に立ちますか？

于 2008-10-10T15:44:19.293 に答える
2

あなたのデータ構造は（SQL Serverの場合）問題ないと思いますが、CTEはクエリにとって最も効率的なソリューションではないかもしれません。代わりに、一時テーブルをキューとして使用してグラフをトラバースするストアド プロシージャを作成してみてください。これはより効率的です。

一時テーブルを使用して、グラフ内の循環を排除することもできますが、循環を排除することはできません。

于 2008-10-10T15:49:42.607 に答える
1

はい、多分）。あなたのデータセットは比較的小さいように聞こえますが、グラフを隣接行列または隣接リストとしてメモリにロードし、グラフを直接クエリすることができます-プログラムを想定しています。

オンディスク フォーマットに関しては、DOTは移植性が高く、人気があります。次のようなフラット ファイル形式でエッジのリストを保存することもかなり一般的です。

vertex1 vertex2 {edge_label1}+

ファイルの最初の行にはグラフの頂点の数が含まれ、その後の各行にはエッジが記述されています。エッジが有向か無向かは、実装者次第です。明示的な有向辺が必要な場合は、次のような有向辺を使用して記述します。

vertex1 vertex2
vertex2 vertex1
于 2008-10-10T15:51:22.120 に答える
0

あなたが説明したようなものをSQL Serverデータベースに保存した私の経験：

ポイントAからポイントBまでの移動にかかる時間を示す距離行列を保存していました。単純な表現を行い、列A、B、距離、時間の距離と呼ばれるテーブルに直接保存しました。

これは、単純な検索では非常に遅くなります。マトリックス全体をテキストとして保存する方がはるかに優れていることがわかりました。次に、計算の前にそれをメモリに取得し、メモリ内に行列構造を作成してそこで操作します。

いくつかのコードを提供できますが、それは C# になります。

于 2008-12-07T10:58:29.953 に答える