4

我有一个存储在 SQL 服务器中的图形网络。图网络（标记、无向和连接图的集合）存储在 Vertex-Edge 映射方案中（即有 2 个表......一个用于顶点，一个用于边）：

顶点（graphID、vertexID、vertexLabel）

边（graphID、sourceVertex、destinationVertex、edgeLabel）

我正在寻找一种简单的方法来计算该网络中的特定子图。例如：我想知道这个网络中有多少个“ABC”实例：“CDABCEABCF”。我有一些关于如何用 Java 或 C++ 来完成的想法......但我不知道如何使用 SQL 来解决这个问题。有任何想法吗？

一点背景：我不是学生..这是我想从事的一个小项目。我做了很多社交媒体分析（在内存中），但很少有针对 SQL 数据库挖掘图表的经验。

4

1 回答 1

1

我的想法是创建一个存储过程，其输入是一个字符串，如“ABC”或一个预先创建的表，其中顶点按正确顺序（“A”、“B”、“C”）。所以你会有一个循环，你应该一步一步地走过路径'ABC'。为此，您需要一个用于当前步骤顶点的临时表：
1）步骤 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）步骤一

@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）循环后

您的结果将存储在#v。所以子图的数量将是：

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