4

SQLサーバーにグラフネットワークを保存しています。グラフネットワーク（ラベル付き、無向、接続されたグラフのコレクション）は、頂点-エッジマッピングスキームに格納されます（つまり、2つのテーブルがあります。1つは頂点用、もう1つはエッジ用です）：

頂点（graphID、vertexID、vertexLabel）

エッジ（graphID、sourceVertex、destinationVertex、edgeLabel）

このネットワークで特定のサブグラフを数える簡単な方法を探しています。例：このネットワークに存在する「ABC」のインスタンスの数を調べたい：「CDABCEABCF」。JavaやC++などでこれを行う方法についていくつかのアイデアがありますが、SQLを使用してこの問題に取り組む方法がわかりません。何か案は？

少し背景：私は学生ではありません。これは私が追求したい小さなプロジェクトです。私は（メモリ内で）多くのソーシャルメディア分析を行っていますが、SQLデータベースに対してグラフをマイニングした経験はほとんどありません。

4

1 に答える 1

1

my idea is to create a stored procedure which input is a string like 'A-B-C' or a precreated table with vertices in proper order ('A', 'B', 'C'). So you will have a loop and step by step you should walk through the path 'A-B-C'. For this you need a temp table for vertices on current step:
1)step 0

@currentLabel = getNextVertexLabel(...) --need to decide how to do this
select 
  * 
into #v
from Vertices 
where 
  vertexLabel = @currentLabel

--we need it later
select 
  * 
into #tempV 
from #v 
where 
  0 <> 0

2)step i

@currentLabel = getNextVertexLabel(...)

insert #tempV
select
  vs.*
from #v v
join Edges e on
  e.SourceVertex = v.VertexID
  and e.graphID = v.graphID
join Vertices vs on
  e.destinationVertex = vs.VertexID
  and e.graphID = vs.graphID
where
  vs.vertexLabel = @currentLabel

truncate table #v
insert #v
select * from #tempV

truncate table #tempV

3)after loop

You result will store at #v. So the number of subgraphs will be:

select count(*) from #v
于 2012-11-08T08:15:42.750 に答える