题:
我有以下(指导)图:
和这个表:
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],'D',20.00000 ); INSERT INTO [dbo].[T_Hops] ([UID],'B',5.00000 ); INSERT INTO [dbo].[T_Hops] ([UID],'C','F',2.00000 ); INSERT INTO [dbo].[T_Hops] ([UID],'G',6.00000 ); INSERT INTO [dbo].[T_Hops] ([UID],'H',3.00000 ); INSERT INTO [dbo].[T_Hops] ([UID],1.00000 );
现在我可以查询从点x到点y的最佳连接,如下所示:
WITH AllRoutes ( [UID],[FROM],[Distance],[Path],[Hops] ) AS ( SELECT [UID],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],[Distance]) VALUES (newid() --<UID,uniqueidentifier,>,'D' --<From,nvarchar(1000),'H' --<To,1 --<Distance,decimal(18,5),> ) GO
现在,正如预期的那样,我的查询引发了一个异常:
超过无限递归/最大递归等级(100)
因为可能连接的数量现在是无限的.
现在在Oracle中,您也可以使用“先前连接”而不是树来做同样的事情.
如果一个循环问题(无限递归)是可能的,你只需要添加
NOCYCLE先前连接,使其“通过NOCYCLE优先连接”
AND Parent.[Path] NOT LIKE '%' + [dbo].[T_Hops].[FROM] + '/%'
到内部连接子句,基本上模拟NOCYCLE.
然而,由于LIKE基本上是strstr(或更差的strcasestr),
并且因此比检查父元素的数组最快,
我非常担心演出.
毕竟这只是一个例子,我打算基本上添加数据
为整个国家.
所以最终的结果可能会很慢.
任何人有更好的(=更快)的方法如何替换NOCYCLE在MS sql?
或者这是我没有别的选择,但是切换到Oracle(以可接受的速度进行)?
注意:
任何临时表(大量数据)解决方案都会更慢,
因为临时表将被交换到硬盘
当没有足够的RAM(绝对确定性)时.