Vấn đề về đồ thị: kết nối bằng NOCYCLE trước khi thay thế trong máy chủ SQL?

Question

câu hỏi:

tôi có như sau (đạo diễn) graph:

Và bảng này:

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

GO 

Và nội dung này:

 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    ); 

Bây giờ tôi có thể truy vấn kết nối tốt nhất từ ​​điểm x đến điểm y như sau:

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 

Bây giờ tôi muốn tạo ra một đồ thị vô hướng, cho rằng tôi có thể, ví dụ, cũng có được con đường từ D đến A

Tôi bắt đầu với một sự thay đổi đơn giản nhất, và chỉ quảng cáo theo hướng ngược lại cho 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 

Bây giờ, như mong đợi, truy vấn của tôi ném một ngoại lệ:

Infinite mức đệ quy/max đệ quy (100) vượt

Bởi vì số lượng kết nối có thể bây giờ là vô hạn.

Bây giờ trong Oracle bạn làm điều tương tự với "kết nối bằng trước" thay vì cây. Và nếu một vấn đề chu kỳ (vô hạn đệ quy) là có thể, bạn chỉ cần thêm NOCYCLE để CONNECT BY TRƯỚC, làm cho nó "CONNECT BY NOCYCLE TRƯỚC"

Bây giờ trong MS-SQL, tôi cố định hành vi đó bằng cách thêm:

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

đến mệnh đề nối bên trong, về cơ bản mô phỏng NOCYCLE.

Tuy nhiên, như LIKE về cơ bản là strstr (hoặc tệ hơn strcasestr), và do đó tối đa chậm hơn kiểm tra một mảng các phần tử cha, Tôi vô cùng lo lắng về hiệu suất.

Sau khi tất cả, đây chỉ là một ví dụ và tôi dự định sẽ thêm dữ liệu cho toàn bộ quốc gia. Vì vậy, kết quả cuối cùng sẽ rất chậm.

Bất kỳ ai khác có phương pháp tốt hơn (= nhanh hơn) về cách thay thế NOCYCLE trong MS SQL?

Hoặc đây có phải là điểm mà tôi không có lựa chọn nào khác ngoài việc chuyển sang Oracle (để thực hiện điều này với tốc độ chấp nhận được)?

Lưu ý: Bất kỳ bảng tạm thời (số lượng lớn các dữ liệu) giải pháp sẽ chậm hơn, vì các bảng tạm thời sẽ được hoán đổi cho đĩa cứng khi không có đủ RAM (chắc chắn tuyệt đối).

Cùng đi với bất kỳ giải pháp nào bằng cách sử dụng hàm và hàm có giá trị bảng.

Answer 1

Để cải thiện cửa hàng chọn thực hiện con đường có thể giữa các nút trong một bảng vĩnh viễn

TABLE T_Hops_Path 
(
    FromNode, 
    ToNode, 
    HopCount, 
    TotalDistance 
) 

Nếu cấu trúc cây của bạn không thay đổi thường xuyên bạn có thể viết một stored procedure mà tạo ra bảng này mỗi N giờ.