存储/访问有向图的最佳方式

Question

我有大约3500个防洪设施,我想将其表示为确定流路径的网络(基本上是有向图).我目前正在使用SqlServer和CTE递归检查所有节点及其上游组件,只要上游路径不分叉,这就可以工作.然而,由于增加了上游复杂性,一些查询比其他查询指数长得多,即使它们在物理上不太远(即两个或三个"下游"段).在某些情况下,我会在杀死查询之前让它超过十分钟.我正在使用一个简单的双列表,一列是设施本身,另一列是第一列中列出的设施的上游设施.

我尝试使用当前工具添加索引以帮助加快速度,但这没有任何区别.并且,对于图中可能的连接,任何节点可以具有多个上游连接,并且可以从多个"下游"节点连接.

当然有可能在数据中有循环,但我还没有找到一种好的方法来验证这一点(除了CTE查询报告最大递归计数命中时;这些很容易修复).

所以,我的问题是,我存储这些信息是错误的吗？有没有比CTE更好的方法来查询上游点？

Answer 1

存储图形的最佳方法当然是使用本机图形db :-)

看看neo4j.它是用Java实现的,并且还有Python和Ruby绑定.

我编写了两个wiki页面,其中包含使用neo4j表示为图形的域模型的简单示例:assembly和roles.在域建模库页面上可以找到更多示例.

Answer 2

我对防洪设施一无所知。但我会选择第一个设施。并使用临时表和 while 循环来生成路径。

-  伪代码
临时表（最后一个节点、当前节点、N）


声明 @intN INT
设置@intN = 1

插入临时表（最后一个节点，当前节点，N）
  -- 在列表中插入第一个项目，没有上游项目...将此称为初始条件
  选择最后一个节点、当前节点、@intN
  从您的餐桌上
  WHERE 节点上游没有任何内容

而@intN <= 3500
开始
     SEt @intN = @intN + 1
    插入临时表（最后一个节点，当前节点，N）
      选择最后一个节点、当前节点、@intN
      从您的餐桌上
      WHERE LastNode IN（从临时表中选择当前节点，其中 N = @intN-1）

IF @@ROWCOUNT = 0
     BREAK


结尾

如果我们假设每个节点都指向一个子节点。那么这应该不会超过 3500 次迭代。如果多个节点具有相同的上游提供商，那么所需时间会更少。但更重要的是，这可以让你做到这一点......

从 TempTable 中选择 LastNode、CurrentNode、N ORDER BY N

这将使您了解您的提供商是否存在任何循环或任何其他问题。顺便说一句，3500 行并不算多，因此即使在每个提供商都指向不同上游提供商的最坏情况下，也不应该花那么长时间。