图形问题:在SQL Server中通过NOCYCLE进行连接，然后进行替换吗? [英] Graph problems: connect by NOCYCLE prior replacement in SQL server?
问题描述
问题:
我有以下(定向)图:
I have the following (directed) graph:
和这张桌子:
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的最佳连接:
Now I can query the best connection from point x to point y like this:
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的路径
Now I want to create an undirected graph, for that I can, for example, also get the path from D to A
我从一个最简单的变化开始，然后向高清方向相反.
I start with a most simple change, and just ad the reverse direction for 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
现在，正如预期的那样，我的查询引发了异常:
Now, as expected, my query throws an exception:
无限递归/超过最大递归级别(100)
Infinite recursion / max recursion level (100) exceeded
因为现在可能的连接数是无限的.
Because the number of possible connections is now infinite.
现在在Oracle中，您可以使用按先连接"而不是树来执行相同的操作. 如果可能出现循环问题(无限递归)，则只需添加 按优先级连接的Nocycle，使其成为按优先级连接的"
Now in Oracle you do the same thing with "connect by prior" instead of a tree. And if a cycle problem (infinite recursion) is possible, you just add NOCYCLE to CONNECT BY PRIOR, making it "CONNECT BY NOCYCLE PRIOR"
现在在MS-SQL中，我通过添加以下内容修复了该行为:
Now in MS-SQL, I fixed that behaviour by adding:
AND Parent.[Path] NOT LIKE '%' + [dbo].[T_Hops].[FROM] + '/%'
到内部join子句，本质上是模仿NOCYCLE.
to the inner join clause, essentially emulating NOCYCLE.
但是，由于LIKE基本上是strstr(或更糟的strcasestr)， 因此，这比检查父元素数组要慢得多， 我非常担心表现.
However, as LIKE is basically strstr (or worse strcasestr), and thus maximally slower than checking an array of parent elements, I am extremely worried about performance.
毕竟，这只是一个例子，我打算基本上添加数据 整个国家 因此最终结果可能会非常缓慢.
After all, this is just an example, and I intend to basically add data for an entire country. So the end result would potentially be extremely slow.
还有其他人有一种更好(=更快)的方法来替换MS SQL中的NOCYCLE吗?
Anybody else has a better (=faster) method of how to replace NOCYCLE in MS SQL ?
或者这是我别无选择，只能切换到Oracle(以可接受的速度执行此操作)的地方吗?
Or is this the point where I simply have no other option but switching to Oracle (for doing this in an acceptable speed) ?
注意: 任何临时表(大量数据)的解决方案都会变慢， 因为临时表将被交换到硬盘 当内存不足(绝对确定)时.
Note: Any temp tables (large amount of data) solution will be slower, because the temp tables will be swapped to the HardDisk when there is not enough RAM (absolute certainty).
对于使用函数和表值函数的任何解决方案都一样.
Same goes for any solution using functions and table-valued functions.
推荐答案
为提高选择性能，在永久表中存储节点之间的可能路径
To improve select performance store possible paths between nodes in a permanent table
TABLE T_Hops_Path
(
FromNode,
ToNode,
HopCount,
TotalDistance
)
如果树结构不经常更改，则可以编写一个存储过程，每N小时生成一次此表.
If your tree structure does not change often you can write a stored procedure that generates this table every N hours.
这篇关于图形问题:在SQL Server中通过NOCYCLE进行连接，然后进行替换吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
