SQL:查找子图

Question

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

顶点( graphID 、 vertexID 、 vertexLabel )

边( graphID ， sourceVertex ， destinationVertex ，edgeLabel )

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

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

Answer 1

我的想法是创建一个存储过程，它的输入是一个像“A-B-C”这样的字符串或一个预先创建的表，顶点的顺序正确(“A”、“B”、“C”)。所以你会有一个循环，你应该一步一步地走过路径“A-B-C”。为此，您需要一个当前步骤顶点的临时表:
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