Проблемы с графикой: подключайте NOCYCLE до замены на SQL-сервере?

Вопрос:

У меня есть следующий (направленный) график:

И эта таблица:

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 вы делаете то же самое с "connect by prior" вместо дерева. И если проблема цикла (бесконечная рекурсия) возможна, вы просто добавляете NOCYCLE CONNECT BY PRIOR, что делает его "СОЕДИНЯТЬСЯ ПРИНЦИПОМ NOCYCLE"

Теперь в MS-SQL я исправил это поведение, добавив:

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

к предложению внутреннего соединения, по существу эмулирующему NOCYCLE.

Однако, поскольку LIKE является в основном strstr (или хуже strcasestr), и, следовательно, максимально медленнее, чем проверка массива родительских элементов, Я очень беспокоюсь о производительности.

В конце концов, это всего лишь пример, и я намерен в основном добавлять данные для всей страны. Таким образом, конечный результат может быть чрезвычайно медленным.

У кого-нибудь есть лучший (= более быстрый) способ замены NOCYCLE в MS SQL?

Или это точка, в которой у меня просто нет другого выбора, кроме переключения на Oracle (для этого с приемлемой скоростью)?

Примечание: Любые временные таблицы (большое количество данных) будут медленнее, потому что временные таблицы будут заменены на HardDisk когда нет достаточной ОЗУ (абсолютная уверенность).

То же самое относится к любому решению с использованием функций и табличных функций.

Ответ 1