9

質問：

次の（有向）グラフがあります。 グラフ

そして、このテーブル：

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 がない場合 (絶対確実) に一時テーブルがハードディスクにスワップされるため、遅くなります。

関数とテーブル値関数を使用するソリューションについても同様です。

4

1 に答える 1

1

パフォーマンスを向上させるには、ノード間の可能なパスを永続テーブルに保存します

TABLE T_Hops_Path
(
  FromNode,
  ToNode,
  HopCount,
  TotalDistance
)

ツリー構造が頻繁に変更されない場合は、N 時間ごとにこのテーブルを生成するストアド プロシージャを作成できます。

于 2011-09-13T04:00:57.057 に答える