在SQL Server中高效查询有向/无向图边的表

Question

我有一个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;

但是这显然涉及到从两个查询中组合结果集，似乎不太高效 - 是否有更好的方法可以在单个查询中编写此操作？（请注意，我不想再将反向边插入表中 - 我需要能够在运行时将边视为有向或无向）。感谢任何建议！

- Clare Nia

---

如果＃Edges从具有FromNodeID = ToNodeID的情况中获得保护，则您的UNION版本将从使用UNION ALL而不是UNION中获胜。即使允许自引用节点，您最好使用SELECT ... WHERE FromNodeID = 3 AND ToNodeID <> 3 UNION ALL SELECT ... WHERE FromNodeID <> 3 AND ToNodeID = 3 UNION ALL SELECT 3 FROM #Edges WHERE FromNodeID = 3 AND ToNodeID = 3，但仅当您不需要对节点进行排序时（否则它似乎比您的版本性能更差）。 - Andriy M

Answer 1

但这显然涉及将两个查询的结果集合并，似乎不太高效-有没有更好的方法在一个查询中编写它？

这已经足够高效了。

你可以这样做：

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查询实际上更加高效，因为它使用了Merge Join来连接结果，并且记录自然有序地出现在合并连接中，因此Stream Aggregate不需要排序。

- Quassnoi

Answer 2

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

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

- Kevin A. Naudé

Answer 3

我能想到三个选项：只在表格中进行、只在查询中进行，或创建一个view。对于表格，创建triggers来强制对称闭包（例如，在插入（a，b）时，也插入（b，a）；在将（a，b）更新为（c，d）时，删除旧的保持对称性的（b，a）对，然后插入（d，c））。请注意，这可能行不通，因为一些RDBMSs（我不确定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)

- outis