6

我有一个 SQL 服务器表，其中每一行代表图形网络中的一条边。FromNodeID 和 ToNodeID 是节点表的外键，架构如下所示：

CREATE TABLE #Edges (
  EdgeID int identity (1,1),
  FromNodeID int,
  ToNodeID int
  );

INSERT INTO #Edges (FromNodeID, ToNodeID) VALUES
  (1,2),
  (1,3),
  (1,4),
  (2,3),
  (3,5),
  (4,5),
  (5,6);

现在，如果我认为每条边都是有向的（即单向），那么很容易计算出我可以从任何节点直接到达的所有节点。我会在 FromNodeID 列中添加一个索引，然后运行如下查询：

SELECT ToNodeID FROM #Edges WHERE FromNodeID = 3

结果：5

但是，如果我想将每条边视为单向的，那么构建我的表/查询的最佳方式是什么。即从节点3开始，我想得到结果：

结果：1、2、5

我能想到的最简单的方法是向 ToNodeID 列添加一个附加索引，然后运行如下查询：

SELECT ToNodeID FROM #Edges WHERE FromNodeID = 3 
UNION SELECT FromNodeID FROM #Edges WHERE ToNodeID = 3;

但这显然涉及组合来自两个查询的结果集，并且看起来效率不高 - 有没有更好的方法可以在单个查询中编写它？（请注意，我不想将反向边缘再次插入表中 - 我需要能够在运行时将边缘视为有向或无向）。

感谢您的任何建议！

4

3 回答 3

4

但这显然涉及组合来自两个查询的结果集，并且看起来效率不高 - 有没有更好的方法可以在单个查询中编写它？

这足够有效。

你可以这样做：

SELECT  CASE 3 WHEN FromNodeId THEN ToNodeId ELSE FromNodeId END
FROM    Edges
WHERE   3 IN (FromNodeId, ToNodeId)

但这基本上是相同的（UNION这些索引会在引擎盖下）。

这是一个要测试的脚本：

CREATE TABLE #Edges
        (
        EdgeID INT IDENTITY (1,1) PRIMARY KEY,
        FromNodeID int NOT NULL,
        ToNodeID int NOT NULL
        )
CREATE INDEX ix_edges_from ON #Edges (FromNodeID, ToNodeId)
CREATE INDEX ix_edges_to ON #Edges (ToNodeID, FromNodeId)
;
WITH    q (rn) AS
        (
        SELECT  1
        UNION ALL
        SELECT  rn + 1
        FROM    q
        WHERE   rn < 1000
        )
INSERT
INTO    #Edges (FromNodeId, ToNodeId)
SELECT  q1.rn, q2.rn
FROM    q q1
CROSS JOIN
        q q2
WHERE   (q1.rn + q2.rn) % 37 = 0
OPTION (MAXRECURSION 0)

对于UNION：

SELECT  ToNodeId
FROM    #Edges
WHERE   FromNodeId = 3
UNION
SELECT  FromNodeId
FROM    #Edges
WHERE   ToNodeId = 3


  |--Stream Aggregate(GROUP BY:([Union1006]))
       |--Merge Join(Concatenation)
            |--Index Seek(OBJECT:([tempdb].[dbo].[#Edges]), SEEK:([tempdb].[dbo].[#Edges].[FromNodeID]=(3)) ORDERED FORWARD)
            |--Index Seek(OBJECT:([tempdb].[dbo].[#Edges]), SEEK:([tempdb].[dbo].[#Edges].[ToNodeID]=(3)) ORDERED FORWARD)

对于IN：

  |--Compute Scalar(DEFINE:([Expr1003]=CASE WHEN (3)=[tempdb].[dbo].[#Edges].[FromNodeID] THEN [tempdb].[dbo].[#Edges].[ToNodeID] ELSE [tempdb].[dbo].[#Edges].[FromNodeID] END))
       |--Sort(DISTINCT ORDER BY:([tempdb].[dbo].[#Edges].[EdgeID] ASC))
            |--Concatenation
                 |--Index Seek(OBJECT:([tempdb].[dbo].[#Edges]), SEEK:([tempdb].[dbo].[#Edges].[FromNodeID]=(3)) ORDERED FORWARD)
                 |--Index Seek(OBJECT:([tempdb].[dbo].[#Edges]), SEEK:([tempdb].[dbo].[#Edges].[ToNodeID]=(3)) ORDERED FORWARD)

如您所见，这些计划本质上是相同的：它们都从相应的索引中获取值并将结果连接起来。

UNION查询实际上效率更高一些，因为它使用 a来Merge Join连接结果，并且从合并连接出来的记录自然有序，因此Stream Aggregate不需要排序。

于 2011-01-26T21:08:35.867 回答
1

必须直接从 SQL Server 处理图形吗？如果您真的关心性能，您应该使用专门用于表示和处理图形的数据结构之一。如果我使用通用数据库后端来查阅图表，我对图表所做的大部分工作（我已经做了很多）都是不可行的。

我使用的最有效的表示之一在我拥有的编译器书籍的附录中进行了描述：Engineering a Compiler，作者 Keith Cooper 和 Linda Torczon。

于 2011-01-26T21:18:40.493 回答
0

我能想到三个选项：仅在表中执行，仅在查询中执行，或创建视图。对于表，创建强制对称闭包的触发器（例如，在插入 (a,b) 时，也插入 (b,a)；当将 (a,b) 更新为 (c,d) 时，删除旧的保持对称性 ( b,a) 对，然后插入 (d,c))。请注意，这可能不起作用，因为某些 RDBMS（我不确定 SQL Server 是否是其中之一）不允许插入/更新触发器触发的表。

在查询中，

SELECT CASE FromNodeID WHEN 3 THEN ToNodeId ELSE FromNodeId END
  FROM #Edges 
    WHERE FromNodeID=3 OR ToNodeID=3

对于视图，创建一个原始表的对称闭包。我认为您仍然必须使用 UNION，但它可以简化查询编写。

CREATE VIEW undirected_edges (FirstEdgeID,SecondEdgeId)
  AS (SELECT FromNodeID, ToNodeID FROM #Edges)
  UNION DISTINCT
    (SELECT ToNodeID, FromNodeID FROM #Edges)
于 2011-01-26T21:11:04.880 回答