问题:
I have the following (directed) graph:
![Graph](https://i.stack.imgur.com/cmMiF.png)
还有这张表:
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,使其成为“CONNECT BY NOCYCLE PRIOR”
现在在 MS-SQL 中,我通过添加以下内容修复了该行为:
AND Parent.[Path] NOT LIKE '%' + [dbo].[T_Hops].[FROM] + '/%'
到内部连接子句,本质上是模拟 NOCYCLE。
然而,由于 LIKE 基本上是 strstr (或更糟糕的 strcasestr),
因此比检查父元素数组要慢得多,
我非常担心表现。
毕竟这只是一个例子,我基本上是打算添加数据
对于整个国家。
因此最终结果可能会非常慢。
还有其他人有更好(=更快)的方法来替换 MS SQL 中的 NOCYCLE 吗?
或者这是我除了切换到 Oracle(以可接受的速度执行此操作)之外别无选择的地方?
笔记:
任何临时表(大量数据)解决方案都会变慢,
因为临时表将被交换到硬盘
当没有足够的 RAM 时(绝对确定)。
对于使用函数和表值函数的任何解决方案也是如此。