sql - パスを取得するクエリ

Question

次のデータを含むテーブルがあります。

Source | Destination
-------------------
46      47
47      49
48      49
49      50

パスリストを返すSQLを書きたいと思います。つまり、入力クエリとして46,50の場合、出力として46,47,49,50を返す必要があります。

Answer 1

SQL Serverでは、次のように再帰共通テーブル式（CTE）を使用できます。

declare @table Table(child int, parent int)

insert into @table(child, parent)
Values  
    (46, 47),
    (47, 49),
    (48, 49),
    (49, 50)


declare @start int
set @start = 46
;

with t1(child, parent) as (
select child, parent from @table t2
where child = @start
union all
select t.child,t.parent
from @table as t
join t1 on t1.parent = t.child
)
select parent from t1
union
select child from @table
where child = @start 

上記のクエリの結果は次のとおりです。

(4 row(s) affected)
parent
-----------
46
47
49
50

(4 row(s) affected)

Answer 2

共通テーブル式の使用に関する Derek Greer による上記の解決策は、いくつかの理由で正しくありません。単純なものは次の 2 つです。

1. 目標は開始点と終了点を提供することでしたが、彼のソリューションには開始点しかないため、元の質問には答えません。
2. サンプル テーブルの 2 行目 (47、49) を削除すると、47 から 50 への可能なパスがすべて削除され、NULL 値が返されます。代わりに、提供されたコードは誤ったパス (46、47、48、49) を提供します。

以下のたまごの解決策も機能しません。質問で要求した (46, 50) の例を含むいくつかの単純なケースを試してみてください。うまくいかないことがわかります。

答えは、これは巡回セールスマン問題と呼ばれるコンピューター サイエンスの古典的な問題です。詳細については、http://en.wikipedia.org/wiki/Travelling_salesman_problemの Wikipedia を参照してください。

このテーマについては、すでに多くのアルゴリズムが公開されています。実装する最も簡単な方法は、考えられるすべての順列を検索することですが、可能性の数が多いため、小さなデータ セットでしか機能しません。より高度なアルゴリズムは実装に時間がかかりますが、はるかに大きなデータ セットで機能します。

おおよその解を探すことも検討できます。はるかに大きなデータセットで機能する近似アルゴリズムがあり、それらは有効なパスを返しますが、最短のパスを見つけられない場合があります。

Answer 3

これが WHILE ループ (疑似 / 未テスト) です。再帰的な CTE を試すこともできます。

--INPUT VARS
@path_begin int
@path_end int

--FUNCTION OR PROC
DECLRE @source int
DECLRE @destination int
DECLRE @path varchar(max)
SET @path = 'No Path Exists'

SELECT @source = source FROM table WHERE source = @path_begin
SELECT @destination = destination FROM table WHERE destination = @path_end

IF @source is not null AND @destination is not null
BEGIN
   SET @path = @source
   WHILE @source < @destination
   BEGIN
      SELECT @source = min(source) FROM table WHERE source > @source AND @source < destination
      SET @path = @path + ',' + @source
   END
   SET @path = @source + ',' + @destination
END

RETURN @path