图形问题:在SQL服务器中通过NOCYCLE连接之前进行连接？

Question

题:

我有以下(指示)图:

而这张桌子:

CREATE TABLE [dbo].[T_Hops](
    [UID] [uniqueidentifier] NULL,
    [From] [nvarchar](1000) NULL,
    [To] [nvarchar](1000) NULL,
    [Distance] [decimal](18, 5) NULL
) ON [PRIMARY]

GO

而这个内容:

      INSERT INTO [dbo].[T_Hops]             ([UID]             ,[From]             ,[To]             ,[Distance])       VALUES             (newid()              ,'A'              ,'E'              ,10.00000              );   
      INSERT INTO [dbo].[T_Hops]             ([UID]             ,[From]             ,[To]             ,[Distance])       VALUES             (newid()              ,'E'              ,'D'              ,20.00000              );   
      INSERT INTO [dbo].[T_Hops]             ([UID]             ,[From]             ,[To]             ,[Distance])       VALUES             (newid()              ,'A'              ,'B'              ,5.00000              );   
      INSERT INTO [dbo].[T_Hops]             ([UID]             ,[From]             ,[To]             ,[Distance])       VALUES             (newid()              ,'B'              ,'C'              ,10.00000              );   
      INSERT INTO [dbo].[T_Hops]             ([UID]             ,[From]             ,[To]             ,[Distance])       VALUES             (newid()              ,'C'              ,'D'              ,5.00000              );   
      INSERT INTO [dbo].[T_Hops]             ([UID]             ,[From]             ,[To]             ,[Distance])       VALUES             (newid()              ,'A'              ,'F'              ,2.00000              );   
      INSERT INTO [dbo].[T_Hops]             ([UID]             ,[From]             ,[To]             ,[Distance])       VALUES             (newid()              ,'F'              ,'G'              ,6.00000              );   
      INSERT INTO [dbo].[T_Hops]             ([UID]             ,[From]             ,[To]             ,[Distance])       VALUES             (newid()              ,'G'              ,'H'              ,3.00000              );   
      INSERT INTO [dbo].[T_Hops]             ([UID]             ,[From]             ,[To]             ,[Distance])       VALUES             (newid()              ,'H'              ,'D'              ,1.00000              );   

现在我可以查询从点x到点y的最佳连接,如下所示:

WITH AllRoutes 
(
     [UID]
    ,[FROM]
    ,[To]
    ,[Distance]
    ,[Path]
    ,[Hops]
)
AS
(
    SELECT 
         [UID]
        ,[FROM]
        ,[To]
        ,[Distance]
        ,CAST(([dbo].[T_Hops].[FROM] + [dbo].[T_Hops].[To]) AS varchar(MAX)) AS [Path]
        ,1 AS [Hops]
      FROM [dbo].[T_Hops]
      WHERE [FROM] = 'A'

    UNION ALL


    SELECT 
         [dbo].[T_Hops].[UID]
        --,[dbo].[T_Hops].[FROM]
        ,Parent.[FROM]
        ,[dbo].[T_Hops].[To]
        ,CAST((Parent.[Distance] + [dbo].[T_Hops].[Distance]) AS [decimal](18, 5)) AS distance
        ,CAST((Parent.[Path] + '/' + [dbo].[T_Hops].[FROM] + [dbo].[T_Hops].[To]) AS varchar(MAX)) AS [Path]
        ,(Parent.[Hops] + 1) AS [Hops]
     FROM [dbo].[T_Hops]

    INNER JOIN AllRoutes AS Parent 
            ON Parent.[To] = [dbo].[T_Hops].[FROM] 

)

SELECT TOP 100 PERCENT * FROM AllRoutes


/*
WHERE [FROM] = 'A' 
AND [To] = 'D'
AND CHARINDEX('F', [Path]) != 0 -- via F
ORDER BY Hops, Distance ASC
*/

GO

现在我想创建一个无向图,例如,我也可以获得从D到A的路径

我从一个最简单的改变开始,只是反向HD的方向.

INSERT INTO [dbo].[T_Hops]
           ([UID]
           ,[From]
           ,[To]
           ,[Distance])
     VALUES
           (newid() --<UID, uniqueidentifier,>
           ,'D' --<From, nvarchar(1000),>
           ,'H' --<To, nvarchar(1000),>
           ,1 --<Distance, decimal(18,5),>
           )
GO

现在,正如预期的那样,我的查询抛出异常:

超出了无限递归/最大递归级别(100)

因为可能的连接数现在是无限的.

现在在Oracle中,您使用"先通过连接"而不是树来执行相同的操作.如果循环问题(无限递归)是可能的,您只需将NOCYCLE添加到CONNECT BY PRIOR,使其成为"通过NOCYCLE PRIOR连接"

现在在MS-SQL中,我通过添加以下内容修复了该行为:

AND Parent.[Path] NOT LIKE '%' + [dbo].[T_Hops].[FROM] + '/%'

到内连接子句,基本上模拟NOCYCLE.

但是,由于LIKE基本上是strstr(或更差的strcasestr),因此最大程度地比检查父元素数组慢,我非常担心性能.

毕竟,这只是一个例子,我打算基本上为整个国家添加数据.所以最终的结果可能会非常缓慢.

其他人有更好的(=更快)的方法来如何在MS SQL中替换NOCYCLE？

或者这是我没有其他选择,但切换到Oracle(以可接受的速度执行此操作)的点？

注意:任何临时表(大量数据)解决方案都会变慢,因为当没有足够的RAM(绝对确定性)时,临时表将被交换到HardDisk.

使用函数和表值函数的任何解决方案都是如此.

Answer 1

为了提高选择性能，将节点之间的可能路径存储在永久表中

TABLE T_Hops_Path
(
  FromNode,
  ToNode,
  HopCount,
  TotalDistance
)

如果您的树结构不经常更改，您可以编写一个存储过程，每 N 小时生成此表。