[アーティクル]
08/19/2015

この記事は機械翻訳されたものです。

テストの実行

SQL を使ったグラフベースの最短経路分析 (機械翻訳)

David McCaffrey このコラムではグラフベースを実装する方法について説明最短-パス分析グラフのデータを SQL データベースに格納し、ネイティブの T-SQL 言語処理を使用する状況で。最短パスの従来のアプローチでは、マシンのメモリのデータ構造でグラフ表現が格納されていることと仮定します。しかしは社会的なネットワークを表すなどの大きなグラフが頻繁ので格納およびそれらの処理のメモリに適合 SQL を使用して 1 つのオプションです。どこに向かっているを理解する最良の方法の例のグラフで見ることです図 1、およびデモのスクリーンショットを実行 図 2。

Demo Graph for Shortest-Path Analysis 図 1 デモグラフの最短パス解析

Shortest-Path Analysis with T-SQL
図 2 最短パス解析 T-SQL で

示すグラフ図 1 人工的に小さなであり (頂点または頂点と呼ばれる） 8 つのノード Id 111 と 888 を介して。ノードの人々やコンピューターを表すことを想像できます。 (エッジと通常呼ばれます) 方向の矢印のノード間の関係です。矢印 2 つのノード間の電子メールの交換を表すことを想像することができます。この例では、グラフのエッジ 1.0 または 2.0 の値によって示される重みがあります。エッジの重みは特定の問題のシナリオに応じて異なる意味を持つことができます。たとえば、ウェイト社会的アフィニティまたはメッセージが送信されたときの指標のいくつかの測定を表すことができます。

用語「最短パス」は異なる意味を持つことができます。あなたはユーザー 222 と 444 のユーザー間の最短経路に興味を持っていると仮定します。これは 222 から 444 に 4 （333 に 222) 666 777 444 になる取得するホップの最小数を意味するかもしれません。または、最短パスの 222 と 444 日間の重みの最小合計 5.0 (1.0 + 1.0 + 1.0 + 2.0) になる可能性があります。

左側のウィンドウで図 2、私が dbShortPathDemo と呼ばれる SQL Server Management Studio でデータベースが働いて見ることができます。右ウィンドウで私を定義し、デモデータベースのグラフに対応する情報を格納する ShortestPath.sql という名前の T-SQL スクリプトがある図 1、および usp_ShortestPath という名前のストアドプロシージャを定義するコード。ストアドプロシージャは、ユーザー 222 と 444 のユーザー間の最短経路を分析するだけ呼び出されています。右下のウィンドウに結果を参照してくださいすることができます。最短パス文字列で与えられる「444 777; 666 333; 222」重量の面での最短経路（なし 10 進表示) 5.0 です。画像の右下部分最短パスコードの実装の鍵です tblAlgorithmData という名前のテーブルの最終的な状態を示しています。

このセクションでは、私はあなたのスクリーンショットで生成された T-SQL コードを介して歩くよ図 2 あなた自身の問題のシナリオを満たすためにコードを適応することができますので。私は主に非 SQL 開発者（あなたが最もよく使用する c# またはいくつか他の手続き型プログラミング言語の意味）するいると仮定していますが、いくつかの基本的な SQL の知識を持って。この記事で説明したすべての T-SQL コードを提示; コードはまた利用で archive.msdn.microsoft.com/mag201212TestRun。

デモデータベースのセットアップ

SQL Server Management Studio を起動し、私のサーバーマシンに接続されてデモデータベースを作成するには。 SQL Server 2008 を使用が少し変更を加えるには、ここで提示コードほとんど以前、すべて新しいバージョンの SQL Server で動作するはずです。接続した後、ファイルをクリックして |編集ウィンドウを取得する新しいクエリ [私のダミーのデータベースを作成する T-SQL コードを入力しました。

    use master
    go
    if exists(select * from sys.sysdatabases 
      where name='dbShortPathDemo')
    drop database dbShortPathDemo
    go
    create database dbShortPathDemo
    go
    use dbShortPathDemo
    go

ここで、create database ステートメントの既定のパラメーター値を使用します。既存のデータベースを実際のデータを操作するでしょう多くのシナリオで、小さなデモデータベースとの実験をお勧めします。私はほとんどの部分は、小文字の T-SQL コードを使用する、SQL の純粋主義者を怒らせる可能性があります好みます。これら 9 つの行のコードを選択し、それらを実行する F5 キーを押してマウスを使用します。デモデータベースが作成されたを確認した後、ShortestPath.sql としてスクリプトを保存します。

次に、分析するグラフを定義するデータを保持するには、デモデータベース内でテーブルを作成しました。

    create table tblGraph
    (
    fromNode bigint not null,
    toNode bigint not null,
    edgeWeight real not null
    )
    go

（私は前の行を再実行しないだろうように) ちょうどこれら 7 行のコードを強調表示するために、マウス使用し、テーブルを作成するには、f5 キーを押します。ノード Id 型 bigint 型を使用します。あなたが出くわすかもしれない他一般的なノード ID 種類 int 比較的単純な従業員 ID および varchar (11) の社会保障番号 xxx xx xxxx 形式でもあります。私型実列 edgeWeight を使用します。 T-SQL 型実は、便利なエイリアスを float(24)、ちょうど c# 型二重と同様です。多くのシナリオで、明示的な辺重み、ノード間がありません、edgeWeight 列を省略できます。

次に、私はテーブル tblGraph を入力する、強調表示、これら 15 行のコードを実行する移入。

    insert into tblGraph values(111,222,1.0)
    insert into tblGraph values(111,555,1.0)
    insert into tblGraph values(222,111,2.0)
    insert into tblGraph values(222,333,1.0)
    insert into tblGraph values(222,555,1.0)
    insert into tblGraph values(333,666,1.0)
    insert into tblGraph values(333,888,1.0)
    insert into tblGraph values(444,888,1.0)
    insert into tblGraph values(555,111,2.0)
    insert into tblGraph values(555,666,1.0)
    insert into tblGraph values(666,333,2.0)
    insert into tblGraph values(666,777,1.0)
    insert into tblGraph values(777,444,2.0)
    insert into tblGraph values(777,888,1.0)
    go

参照する場合図 1、各 insert ステートメントは、グラフ中の矢印のいずれかに対応していることがわかります。

次に、プロシージャのアクセス数グラフデータの最短パスを格納するときにパフォーマンスを向上させる tblGraph の fromNode と toNode の列インデックス作成しました。

    create nonclustered index idxTblGraphFromNode on tblGraph(fromNode)
    go
    create nonclustered index idxTblGraphToNode on tblGraph(toNode)
    go
    I then created and populated a table to hold a list of unique node IDs:
    create table tblNodes
    (
    nodeID bigint primary key
    )
    go
    insert into tblNodes
    select distinct fromNode from tblGraph
    union
    select distinct toNode from tblGraph
    go

ちょうどノード Id の表が最短パス解析では、必須ではありませんが、エラー、開始ノードでチェックを実行し、ノードの入力パラメーターを最短パスのストアドプロシージャを終了する場合に便利です。 NodeID 列にプライマリキー句を適用することによって、私は暗黙的にその列にクラスター化インデックスを作成します。 2 つ以上の個別選択ステートメントで使用する、SQL union ステートメントをテーブルから一意の値の一覧を取得する便利な方法です。

アルゴリズムデータテーブル

理解し、この記事で示す最短パスストアドプロシージャを変更するキー情報を tblAlgorithmData という名前のテーブルを理解しています。これらの T-SQL ステートメントを実行することによって、テーブルを作成できます。

    create table tblAlgorithmData
    (
    nodeID bigint not null,
    dist real not null,
    pred bigint not null,
    inQueue bit not null
    )
    go
    create index idxTblAlgorithmDataNodeID on tblAlgorithmData(nodeID)
    create index idxTblAlgorithmDataDist on tblAlgorithmData(dist)
    create index idxTblAlgorithmDataPred on tblAlgorithmData(pred)
    create index idxTblAlgorithmDataInQueue on tblAlgorithmData(inQueue)
    go

テーブルがあります (せいぜい) 1 行各一意のノードには、グラフのデータテーブルの例この資料では、持っているので 8 行 (せいぜい)。 NodeID は、一意の識別子であるため、主キー列として定義したに可能性があります。 Dist 列 nodeID を持つノード開始ノードから現在の距離です。ストアドプロシージャが実行されますが、ストアドプロシージャが終了すると最終的な距離を保持としてこの dist 値を変更します。見れば図 2、ストアドプロシージャが終了ノード 444、終了ノードの dist 値 5.0 ユニットであることを見ることができます。

Pred 列パラメーター開始ノードを最後のノードから即時の前任者が持つ nodeID 最短パスのノードを保持します。たとえば、 図 2、終了ノードは 444 です。前任者 777 です。 777 の前身は 666 です。 666 の前身は 333 です。 333 の前身は、222、開始ノードです。これらの pred の値を一緒に入れて最短パスノードを開始するには、終了ノードからを与える：444 777 を 666 に 222 333 にするには。私は使用するアルゴリズムは 2 つまたはより多くのパスと同じ最短距離合計位置状況でもちょうど 1 つの最短経路を与えることに注意してください; この例では、パス 444 に 777 555 222 を 666 に総距離 5.0 単位も利用できます。

InQueue 列は、最短パスの一部として、関連付けられたノードが再検討されるべきかどうかを示すビット値 (c# 型ブール値機能的に類似) を保持します。 InQueue の値が 1 の場合は、別の言い方をすれば、関連付けられたノードは、アルゴリズムによって現在のノードは、アルゴリズムで隣人として検討する必要があります。 InQueue の値が 0 の場合は、関連付けられたノードは隣人として検討する必要はありません。 IsActive などの名の使用を検討したいと思うかもしれないので、アルゴリズムは本当に、明示的なキューを使用しないので、列名の inQueue はやや誤解を招くです。私は手続き型プログラミング言語の実装の最短パスアルゴリズムで、明示的なキューはしばしば使用されるので、名前はやや伝統的なです名 inQueue を使用します。

アルゴリズム

この資料でを提示アルゴリズムは、ダイクストラの最短パス（DSP）アルゴリズムのバリエーションです。 SQL 以外の疑似コードでは、私は使用する DSP アルゴリズムのバリエーションで提示される図 3。

図 3 最短経路アルゴリズム

set dist of startNode to 0.0
set pred of startNode to undefined
set inQueue of startNode to true
while there are any nodes with inQueue = true
  set u = node with smallest dist and inQueue = true
  if dist of u is infinity break
  if u = endNode break
  fetch all neighbors of u
  foreach neighbor v that has inQueue = true
    if v has not been seen before then
      set dist of v to infinity
      set pred of v to undefined
      set inQueue of v to true
    end if
  end foreach
  set inQueue of u = false
  foreach neighbor v of u
    if ((dist from startNode to u) + (dist from u to v) <
      curr dist to v) then
        set dist of v to (dist from startNode to u) + (dist from u to v)
        set pred of v to u
    end if
  end foreach
end while
if (u != endNode) then
  path from startNode to endNode is unreachable
else
  retrieve path using pred values
  shortest path distance = dist of endNode
end if

コンピューター科学の最も有名なアルゴリズムの DSP アルゴリズムであるし、インターネット上の多くの痛いほど詳細な説明が、SQL を使用する非常に少数の完全な実装を見つけることができます。短いが、DSP アルゴリズムルゴリズムが非常に難しいと私は完全に理解することができた唯一の方法は紙と鉛筆を使用していくつかの例をトレースするでした。アルゴリズムの本質は、与えられたノード u では、u に、開始ノードから現在の最短距離を知っているよです。その後、u のすべての隣人を検索します。隣人ノードごとに、v、v への開始ノードから現在の距離を知っています。飛距離アップ u から v へ見ることができます。 U に開始からの距離プラス u から v までの距離が v に開始から現在の距離よりも短い場合に、スタートから v への短いパスを発見したを知っています。 InQueue 変数は、そのノードを再訪も短いパスを見つけるいないことが判明すると、ノードの再訪からアルゴリズムを防ぎます。

ストアドプロシージャ

T-SQL ストアドプロシージャとして最短経路を実装しました。ストアドプロシージャの定義を開始します。

    create procedure usp_ShortestPath
      @startNode bigint,
      @endNode bigint,
      @path varchar(5000) output,
      @totDist real output
    as
    begin
      ...

システムストアドプロシージャの拡張ストアドプロシージャ ("xp"）（"sp") と CLR ストアドプロシージャ ("csp") からストアドプロシージャ usp_ShortestPath 名"usp それを区別するために"(ユーザー定義のストアドプロシージャ) を追加します。パラメーター @startNode と @endNode は入力パラメーターです。ストアドプロシージャでは、2 つの結果の出力パラメーター、@path @totDist しています。 Varchar (5000) を入力する、@path は任意に設定です — ノード ID を使用しているとあなたが期待する最大のパスの種類に応じて、5000 の最大サイズを増やす必要があります。

次に、開始ノードの情報とテーブル tblAlgorithmData を初期化します。

    truncate table tblAlgorithmData
    insert into tblAlgorithmData
    values (@startNode, 0.0, -1, 1)
    ...

Truncate ステートメント tblAlgorithmData usp_ShortestPath 任意以前の呼び出しからの内容を消去します。 NodeID dist、pred、inQueue tblAlgorithmData の列をいるを思い出してください。自体には、開始ノードからの距離は 0.0 になります、開始ノードの前身-1 に示す未定義、設定され、inQueue ビットが 1 に設定である true を示します。

このコードでは、恒久的なテーブルとして現在のデータベースでその tblAlgorithmData が既に作成されている想定しています。いくつかの状況では、テーブルの作成に必要なセキュリティのアクセス許可可能性があります。ことができますこれらの状況でそうあなたのために適切なデータベースの管理者に問い合わせてくださいまたはおそらく temp テーブルまたはテーブル変数として tblAgorithmData 内部ストアドプロシージャを作成できます。

また、このコードでは、@startNode と @endNode の両方の値が有効であることも前提にしています。すべてのノード Id の表がある場合は、このための線に沿ってチェックできる：

    if not exists(select nodeID from tblNodes where @startNode = nodeID)
      // Error out in some way //

次に、メインの処理ループの準備をします。

    declare @u bigint
    declare @d real = 0.0
    declare @done bit = 0
    while @done = 0
    begin
    ...

ここ @u アルゴリズムで現在のノードのノード ID です。可変 @d 利便性であり、（tblAlgorithmData に格納されている) ノードの @u に @startNode からの距離を保持しています。 @ やった変数ですダミーループコントロール変数。ループのイテレーション、最大ホップ数または最大合計パスの距離の最大数などの他の明示的な停止基準を置きたくなるかもしれません。

メインの処理ループ内で、最初のステップは @u の値を見つけることです — 現在のノードのノード ID。これは最小の dist の列の値で tblAlgorithmData と inQueue がありますノードです = 1。

    select top 1 @u = nodeID, @d = dist from tblAlgorithmData
    where inQueue = 1
    order by dist asc
    ...

この時点でストアドプロシージャは 2 つのループ終了条件をチェックします。

    if @d = 2147483647.0 break
    if @u = @endNode break
    ...

@U (@d に格納) に開始ノードからの距離がやや神秘的な探して 2147483647.0 の値に等しい場合は、終了ノードが開始ノードから到達可能でないことを意味します。 2147483647.0 の値に代役を立てインフィニティ用です。実際には距離として表示することはできません任意の大きい値を使用できます。 SQL 型 int の最大値は 2147483647 (小数) なしですので、2147483647.0 を選んだブレーク条件は、単に終了ノードに達しているかどうかを確認します。方法のため、アルゴリズムは終了ノードに当れば、幅優先のアプローチを使用してグラフを検索最短パス発見されています。

次に、各隣人は現在のノードの @u のストアドプロシージャをチェックし、隣人の前に見たされていない場合は、隣人 tblAlgorithmData に初期化されます。

    insert into tblAlgorithmData
    select toNode, 2147483647.0, -1, 1 from tblGraph where fromNode = @u
    and not exists (select * from tblAlgorithmData where nodeID = toNode)
    ...

この SQL コードはめったに SQL を使用するプログラマーをしている場合はちょっと微妙です。 Insert ステートメントは条件付きにはない存在として解釈することができます、ステートメント"近隣ノード ID (toNode 値) で tblAlgorithmData （として nodeID) されていない場合"条件が true の場合、insert ステートメント tblAlgorithmData 隣人の nodeID、無限大 (2147483647.0) としての dist 値で初期化します各隣接ノードの前身未定義 (-1 として) と、true (1) としての inQueue。手続き型プログラミング言語でと同じように、ループを使用してコレクションを反復するのではなく、操作する SQL ステートメントでのデータのセットに基づいて働いて困難パラダイムをマスターすることができます。

ときに最初の隣人ノードとして表示されますこのアルゴリズムでは、ノードが初期化されます。重要な代替アプローチは、アルゴリズムの非常に初めのすべてのグラフのノードを初期化するためにです。このアプローチの問題は、大きなグラフの tblAlgorithmData おそらくの何百万のノードを設定する時間のビットをかなり取ることができることです。

この時点で、ストアドプロシージャは現在のノードが処理としてマークします。

    update tblAlgorithmData set inQueue = 0
    where nodeID = @u
    ...

次に、ストアドプロシージャ、隣人への新しいより短いパス発見されており、場合は、tblAlgorithmData をその近隣ノードのエントリが更新されるかどうかを参照してくださいに各隣人を現在のノードをチェックします。

    update tblAlgorithmData
      set dist = @d + tblGraph.edgeWeight, pred = @u
      from tblAlgorithmData inner join tblGraph on 
        tblAlgorithmData.
    nodeID = tblGraph.toNode
      where tblGraph.fromNode = @u and tblAlgorithmData.inQueue = 1
        and (@d + tblGraph.edgeWeight) < tblAlgorithmData.dist
    end -- loop
    ...

これは断然最短パス実装のトリッキーな部分です。すべてのデータ更新ステートメントで使用できるようにテーブル tblGraph tblAlgorithmData に参加しています。現在のノードの ID @u で格納され、この値が tblGraph で fromNode に対応します。近所の人に @u toNode tblAlgorithmData の nodeID にリンクされている tblGraph に格納されます。その @d 開始ノードから現在のノードの @u までの距離を保持を思い出してください。 EdgeWeight 列の値は、隣人に @u からの距離を開催します。これら 2 つの距離の合計区。列に格納される隣人は、開始ノードから現在の距離から可能な限り新しい短いパスです。新しい短い距離を見つけた場合は、dist 列とその新しい短い距離更新され、@u として、現在のノードの近隣ノードの前身が記録されます。開始ノードと終了ノード間のホップ数が最も少ないことを意味する最短パスを定義する状況では、dist を置き換えるだろう = @d + dist が tblGraph.edgeWeight = @d + 1。

この時点でメインの処理ループが終了したし、出口の原因をチェックできます。

    if (@u != @endNode)
      begin
        set @path = 'NOT REACHABLE'
        set @totDist = -1.0
      end
      else
      begin
        set @path = ''
        declare @currNode bigint
        set @currNode = @endNode
      ...

@U の値が [終了] ノードの ID の場合は、[終了] ノードがされているが見つかりました; @u が終了ノードの ID 以外の場合は、終了ノードを見つける前にループが終了します。この場合、パスの文字列 '到達できません' に設定し、任意の最短パス総距離到達を示さない-1.0 を割り当てます。終了ノードが実際に発見された場合は、最短パス文字列を空の文字列を初期化し、ローカル変数 @currNode を最短パス文字列を構築する tblAlgorithmData を通じて反復処理を設定します。

ストアドプロシージャ定義のコードは、最短パス文字列を構築、最短パスの合計距離を割り当てることによって終わります。

    ...
    while @currNode != @startNode
        begin
          set @path = @path + cast(@currNode as varchar(19)) + ';'
          set @currNode = (select pred from tblAlgorithmData 
            where nodeID = @currNode)
        end
        set @path = @path + cast(@startNode as varchar(19))
        select @totDist = dist from tblAlgorithmData 
          where nodeID = @endNode
      end -- else
    end -- usp_ShortestPath definition
    go

ここで T SQL 文字列の連結を使用「+」演算子。私 nodeID 種類 bigint の最大値 9223372036854775807、19 桁を持っているので varchar(19) を使用します。

作成されたストアドプロシージャを 2 つのノード間の最短経路を見つけることができます; たとえば。

    declare @startNode bigint
    declare @endNode bigint
    declare @path varchar(5000)
    declare @totDist real
    set @startNode = 222
    set @endNode = 444
    exec usp_ShortestPath @startNode, @endNode, 
      @path output, @totDist output
    select @path
    select @totDist

まとめ

企業のデータ収集量が増え、そのデータがクラウド環境に保存されるようになるに従い、最短経路のグラフ分析は重要度を増しているようです。コードとこの記事で提示説明上のデータを最短経路分析の実行を開始するための強固な基盤を与える必要があります。この資料に記載されているネイティブの T-SQL 言語アプローチに代わる重要な CLR ストアドプロシージャを使用することです。私の経験に基づいて、CLR ストアドプロシージャはあなたを与えることができる最短パス解析を用いた複雑さの増加を犠牲にしてパフォーマンスが向上します。今後の記事でグラフの最短パス解析の CLR ストアドプロシージャのアプローチを紹介します。

Dr.James McCaffreyボルト情報科学株式会社は、彼はマイクロソフトのレドモンド、ワシントン州でキャンパス働くソフトウェアエンジニアの技術トレーニングを管理するために動作します。これまでに、Internet Explorer、MSN サーチなどの複数のマイクロソフト製品にも携わってきました。McCaffrey は、「.NET テストオートメーションレシピ」（Apress、2006年）の著者です。彼は到達することができます jammc@microsoft.com。

この記事のレビュー、次技術専門家のおかげで：シェーン・ウィリアムズ

テストの実行

SQL を使ったグラフ ベースの最短経路分析 (機械翻訳)

デモ データベースのセットアップ

アルゴリズム データ テーブル

アルゴリズム

ストアド プロシージャ

まとめ

その他のリソース

SQL を使ったグラフベースの最短経路分析 (機械翻訳)

デモデータベースのセットアップ

アルゴリズムデータテーブル

ストアドプロシージャ