12

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

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

数据中肯定有可能存在循环，但我还没有找到验证这一点的好方法（除了 CTE 查询报告最大递归计数命中；这些很容易修复）。

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

4

6 回答 6

6

存储图形的最佳方式当然是使用原生图形数据库 :-)

看看neo4j。它是用 Java 实现的，并且还具有 Python 和 Ruby 绑定。

我编写了两个 wiki 页面，其中包含使用 neo4j 以图形表示的域模型的简单示例：程序集和角色。更多示例可在域建模库页面上找到。

于 2008-12-07T10:14:31.133 回答
4

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

-- 伪代码
临时表（LastNode、CurrentNode、N）



声明@intN INT
设置@intN = 1



INSERT INTO TempTable(LastNode, CurrentNode, N)
  -- 在列表中插入第一个项目，没有上游项目...调用这个初始条件
  选择最后一个节点，当前节点，@intN
  从你的桌子上
  WHERE 节点上游没有任何内容



而@intN <= 3500
开始
     SEt @intN = @intN + 1
    INSERT INTO TempTable(LastNode, CurrentNode, N)
      选择最后一个节点，当前节点，@intN
      从你的桌子上
      WHERE LastNode IN（从 TempTable 中选择 CurrentNode，其中 N = @intN-1）



IF @@ROWCOUNT = 0
     BREAK




结尾

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

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

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

于 2008-10-10T15:57:30.547 回答
3

传统上，图要么用矩阵表示，要么用向量表示。矩阵占用更多空间，但更容易处理（在您的情况下为 3500x3500 个条目）；向量占用更少的空间（3500 个条目，每个条目都有一个他们连接到谁的列表）。

这对你有帮助吗？

于 2008-10-10T15:44:19.293 回答
2

我认为您的数据结构很好（对于 SQL Server），但 CTE 可能不是您查询的最有效解决方案。您可以尝试使用临时表作为队列来创建一个遍历图形的存储过程，这应该更有效。

临时表也可以用来消除图中的循环，尽管不应该有任何

于 2008-10-10T15:49:42.607 回答
1

也许吧）。您的数据集听起来相对较小，您可以将图形作为邻接矩阵或邻接列表加载到内存并直接查询图形 - 假设您进行编程。

就磁盘格式而言，DOT是相当可移植/流行的。以平面文件格式存储边列表似乎也很常见，例如：

vertex1 vertex2 {edge_label1}+

文件的第一行包含图中顶点的数量，之后的每一行都描述了边。边缘是有向还是无向取决于实现者。如果您想要明确的有向边，请使用有向边来描述它们，例如：

vertex1 vertex2
vertex2 vertex1
于 2008-10-10T15:51:22.120 回答
0

我在 SQL Server 数据库中存储您所描述的内容的经验：

我正在存储一个距离矩阵，告诉从 A 点到 B 点需要多长时间。我已经完成了简单的表示，并将它们直接存储到一个名为距离的表中，列有 A、B、距离、时间。

这在简单的检索中非常缓慢。我发现将整个矩阵存储为文本要好得多。然后在计算之前将其检索到内存中，在内存中创建一个矩阵结构并在那里使用它。

我可以提供一些代码，但它会是 C#。

于 2008-12-07T10:58:29.953 回答