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

Question

我有大约 3500 个防洪设施，我想将它们表示为一个网络来确定流动路径(本质上是一个有向图)。我目前正在使用 SqlServer 和 CTE 来递归检查所有节点及其上游组件，只要上游路径没有 fork 很多，这就会起作用。然而，由于增加了上游的复杂性，一些查询比其他查询花费的时间呈指数级增长，即使它们在路径上的物理距离并不远(即“下游”的两个或三个段)；在某些情况下，在终止查询之前，我已经让它运行了十多分钟。我使用的是一个简单的两列表，一列是设施本身，另一列是第一列中所列设施的上游。

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

数据中当然可能存在循环，但我还没有想出一个很好的方法来验证这一点(除了当 CTE 查询报告最大递归计数命中时；那些很容易修复)。

所以，我的问题是，我存储这些信息是错误的吗？除了 CTE 之外，还有更好的方法来查询上游点吗？

Answer 1

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

-- Pseudo CodeTempTable (LastNode, CurrentNode, N)
DECLARE @intN INTSET @intN = 1
INSERT INTO TempTable(LastNode, CurrentNode, N)  -- Insert first item in list with no up stream items...call this initial condition  SELECT LastNode, CurrentNode, @intN  FROM your table  WHERE node has nothing upstream
WHILE @intN <= 3500BEGIN     SEt @intN = @intN + 1    INSERT INTO TempTable(LastNode, CurrentNode, N)      SELECT LastNode, CurrentNode, @intN      FROM your table      WHERE LastNode IN (SELECT CurrentNode FROM TempTable WHERE N = @intN-1)
IF @@ROWCOUNT = 0
     BREAK

结尾

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

选择最后一个节点，当前节点，N
从临时表
按 N 订购

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