SHORTEST_PATH (Transact-SQL)

[アーティクル]
01/02/2025

適用対象: SQL Server 2019 (15.x) 以降のバージョン Azure SQL Database Azure SQL Managed Instance Sql データベース

再帰的または繰り返し検索されるグラフの検索条件を指定します。 SHORTEST_PATHは、SELECT ステートメントで、グラフノードとエッジテーブルと共に MATCH 内で使用できます。

最短パス

SHORTEST_PATH関数を使用すると、次を見つけることができます。

指定された 2 つのノード/エンティティ間の最短パス
単一ソース最短パス。
複数のソースノードから複数のターゲットノードへの最短パス。

入力として任意の長さのパターンを受け取り、2 つのノード間に存在する最短パスを返します。この関数は MATCH 内でのみ使用できます。この関数は、指定された 2 つのノード間の最短パスを 1 つだけ返します。ソースノードと宛先ノードのペアの間に同じ長さの最短パスが 2 つ以上存在する場合、この関数はトラバーサル中に最初に見つかったパスを 1 つだけ返します。任意の長さのパターンは、SHORTEST_PATH関数内でのみ指定できます。

完全な構文については、 MATCH (SQL Graph) を参照してください。

FOR PATH

FOR PATH は、任意の長さのパターンに含まれる FROM 句内の任意のノードまたはエッジテーブル名と共に使用する必要があります。 FOR PATH は、ノードまたはエッジテーブルが、走査されたパスに沿って見つかったノードまたはエッジの一覧を表す順序付きコレクションを返すようにエンジンに指示します。これらのテーブルの属性を SELECT 句に直接投影することはできません。これらのテーブルから属性を射影するには、グラフパス集計関数を使用する必要があります。

任意の長さのパターン

このパターンには、次のいずれかになるまで繰り返し走査する必要があるノードとエッジが含まれます。

目的のノードに到達します。
パターンで指定されたイテレーションの最大数が満たされます。

次の 2 つのパターン量指定子がサポートされています。

'+': パターンを 1 回以上繰り返します。最短パスが見つかったらすぐに終了します。
{1,n}: パターンを 1 から n 回繰り返します。最短が見つかったらすぐに終了します。

LAST_NODE

LAST_NODE() 関数を使用すると、2 つの任意の長さのトラバーサルパターンをチェーンできます。これは、次のようなシナリオで使用できます。

1 つのクエリで複数の最短パスパターンが使用され、前のパターンの LAST ノードから 1 つのパターンが開始されます。
2 つの最短パスパターンが同じ LAST_NODE() でマージされます。

グラフパスの順序

グラフパスの順序は、出力パス内のデータの順序を指します。出力パスの順序は、常にパターンの非回復部分から始まり、その後に再帰部分に表示されるノード/エッジが続きます。クエリの最適化/実行中にグラフが走査される順序は、出力に出力される順序とは関係ありません。同様に、再帰パターンの矢印の方向もグラフパスの順序には影響しません。

グラフパス集計関数

任意の長さのパターンに関係するノードとエッジは、そのパスで走査されたノードとエッジのコレクションを返すので、ユーザーは、従来の tablename.attributename 構文を使用して属性を直接投影することはできません。中間ノードまたはエッジテーブルから属性値を射影する必要があるクエリの場合は、走査されたパスで、グラフパス集計関数 (STRING_AGG、LAST_VALUE、SUM、AVG、MIN、MAX、COUNT) を使用します。 SELECT 句でこれらの集計関数を使用する一般的な構文は次のとおりです。

<GRAPH_PATH_AGGREGATE_FUNCTION>(<expression> , <separator>)  <order_clause>

    <order_clause> ::=
        { WITHIN GROUP (GRAPH PATH) }

    <GRAPH_PATH_AGGREGATE_FUNCTION> ::=
          STRING_AGG
        | LAST_VALUE
        | SUM
        | COUNT
        | AVG
         | MIN
        | MAX

STRING_AGG

STRING_AGG関数は、式と区切り記号を入力として受け取り、文字列を返します。ユーザーは SELECT 句でこの関数を使用して、通過したパス内の中間ノードまたはエッジから属性を投影できます。

LAST_VALUE

走査されたパスの最後のノードから属性を投影するには、集計関数LAST_VALUE使用できます。この関数への入力としてエッジテーブルのエイリアスを指定するとエラーになります。ノードテーブル名またはエイリアスのみを使用できます。

最後のノード: 最後のノードは、MATCH 述語の矢印の方向に関係なく、走査されたパスの最後に表示されるノードを参照します。 (例: MATCH(SHORTEST_PATH(n(-(e)->p)+) ))。パスの最後のノードは、最後にアクセスした P ノードです。

MATCH(SHORTEST_PATH((n<-(e)-)+p)) パターンでは、最後のノードは最後にアクセスされた N 個のノードです。

合計

この関数は、走査されたパスに表示された指定されたノード/エッジ属性値または式の合計を返します。

COUNT

この関数は、パス内の指定されたノード/エッジ属性の null 以外の値の数を返します。 COUNT 関数は、 * 演算子をサポートしていません。 * を使用しようとすると構文エラーが発生します。

{  COUNT( <expression> )  <order_clause>  }

AVG

走査されたパスに表示された、指定されたノード/エッジ属性値または式の平均を返します。

MIN

走査パスに表示された指定されたノード/エッジ属性値または式から最小値を返します。

MAX

走査パスに表示された、指定されたノード/エッジ属性値または式から最大値を返します。

解説

SHORTEST_PATH関数は MATCH 内でのみ使用できます。
LAST_NODE関数は、SHORTEST_PATH内でのみサポートされます。
SHORTEST_PATH関数は、ノード間 最短パス 返します。現在、ノード間 最短のパス を返すことはできません。また、ノード間で すべてのパス を返すこともできます。
SHORTEST_PATH実装では、重み付けされていない最短パスが見つかります。
ホップ数が多いクエリに対して不適切なプランが生成され、クエリの実行時間が長くなる場合があります。 OPTION (HASH JOIN) や OPTION (MAXDOP 1) ヘルプなどのクエリヒントを評価します。

例

ここで示すクエリの例では、 SQL Graph サンプルで作成したノードテーブルとエッジテーブルを使用します

A. 2 人の間の最短のパスを見つける

次の例では、ジェイコブとアリスの間の最短パスを見つけます。 SQL Graph サンプルから作成されたPerson ノードとfriendOfエッジが必要です。

SELECT PersonName, Friends
FROM (
    SELECT
        Person1.name AS PersonName,
        STRING_AGG(Person2.name, '->') WITHIN GROUP (GRAPH PATH) AS Friends,
        LAST_VALUE(Person2.name) WITHIN GROUP (GRAPH PATH) AS LastNode
    FROM
        Person AS Person1,
        friendOf FOR PATH AS fo,
        Person FOR PATH  AS Person2
    WHERE MATCH(SHORTEST_PATH(Person1(-(fo)->Person2)+))
    AND Person1.name = 'Jacob'
) AS Q
WHERE Q.LastNode = 'Alice'

B. 特定のノードからグラフ内の他のすべてのノードへの最短パスを検索します。

次の例では、Jacob が接続されているすべてのユーザーをグラフで検索し、そのすべての人々に対して、ジェイコブから始まる最短のパスを見つけます。

SELECT
    Person1.name AS PersonName,
    STRING_AGG(Person2.name, '->') WITHIN GROUP (GRAPH PATH) AS Friends
FROM
    Person AS Person1,
    friendOf FOR PATH AS fo,
    Person FOR PATH  AS Person2
WHERE MATCH(SHORTEST_PATH(Person1(-(fo)->Person2)+))
AND Person1.name = 'Jacob'

C: グラフ内の 1 人のユーザーから別のユーザーに移動するために走査されたホップ/レベルの数をカウントします。

次の例では、Jacob と Alice の間の最短パスを検索し、ジェイコブから Alice に移動するために必要なホップの数を出力します。

 SELECT PersonName, Friends, levels
FROM (
    SELECT
        Person1.name AS PersonName,
        STRING_AGG(Person2.name, '->') WITHIN GROUP (GRAPH PATH) AS Friends,
        LAST_VALUE(Person2.name) WITHIN GROUP (GRAPH PATH) AS LastNode,
        COUNT(Person2.name) WITHIN GROUP (GRAPH PATH) AS levels
    FROM
        Person AS Person1,
        friendOf FOR PATH AS fo,
        Person FOR PATH  AS Person2
    WHERE MATCH(SHORTEST_PATH(Person1(-(fo)->Person2)+))
    AND Person1.name = 'Jacob'
) AS Q
WHERE Q.LastNode = 'Alice'

D. 特定のユーザーから 1 ~ 3 ホップ離れた人を見つける

次の例では、1 ~ 3 ホップ離れたグラフで、ジェイコブと、ジェイコブが接続されているすべての人々の間の最短のパスを検索します。

SELECT
    Person1.name AS PersonName,
    STRING_AGG(Person2.name, '->') WITHIN GROUP (GRAPH PATH) AS Friends
FROM
    Person AS Person1,
    friendOf FOR PATH AS fo,
    Person FOR PATH  AS Person2
WHERE MATCH(SHORTEST_PATH(Person1(-(fo)->Person2){1,3}))
AND Person1.name = 'Jacob'

E. 特定のユーザーから 2 ホップ離れた場所にあるユーザーを見つける

次の例では、ジェイコブと、グラフ内で彼からちょうど 2 ホップ離れている人々の間の最短のパスを見つけます。

SELECT PersonName, Friends
FROM (
    SELECT
        Person1.name AS PersonName,
        STRING_AGG(Person2.name, '->') WITHIN GROUP (GRAPH PATH) AS Friends,
        COUNT(Person2.name) WITHIN GROUP (GRAPH PATH) AS levels
    FROM
        Person AS Person1,
        friendOf FOR PATH AS fo,
        Person FOR PATH  AS Person2
    WHERE MATCH(SHORTEST_PATH(Person1(-(fo)->Person2){1,3}))
    AND Person1.name = 'Jacob'
) Q
WHERE Q.levels = 2

F. 特定の人から 1 ~ 3 ホップ離れた、特定のレストランが好きな人を見つける

次の例では、1 から 3 ホップ離れたグラフで、ジェイコブと彼が接続しているすべての人々の間の最短パスを検索します。また、このクエリでは、特定のレストランで接続されているユーザーの好みに合わせてフィルター処理を行います。次のサンプルでは、 LAST_NODE(Person2) は最短パスごとに最後のノードを返します。その後、LAST_NODEから取得した "最後の" Person ノードを "チェーン" して、さらにトラバーサルを行い、好きなレストランを見つけることができます。

SELECT
    Person1.name AS PersonName,
    STRING_AGG(Person2.name, '->') WITHIN GROUP (GRAPH PATH) AS Friends,
    Restaurant.name
FROM
    Person AS Person1,
    friendOf FOR PATH AS fo,
    Person FOR PATH  AS Person2,
    likes,
    Restaurant
WHERE MATCH(SHORTEST_PATH(Person1(-(fo)->Person2){1,3}) AND LAST_NODE(Person2)-(likes)->Restaurant )
AND Person1.name = 'Jacob'
AND Restaurant.name = 'Ginger and Spice'

G. 特定のノードからグラフ内の他のすべてのノードへの最短パスを検索します ("ループ" を除く)

次の例では、Alice が接続されているすべてのユーザーをグラフで検索し、Alice からそれらのすべてのユーザーへの最短パスを検索します。この例では、パスの開始ノードと終了ノードが同じである "ループ" を明示的にチェックします。

SELECT PersonName, Friends
FROM (
    SELECT
        Person1.name AS PersonName,
        STRING_AGG(Person2.name, '->') WITHIN GROUP (GRAPH PATH) AS Friends,
        LAST_VALUE(Person2.name) WITHIN GROUP (GRAPH PATH) AS LastNode
    FROM
        Person AS Person1,
        friendOf FOR PATH AS fo,
        Person FOR PATH  AS Person2
    WHERE MATCH(SHORTEST_PATH(Person1(-(fo)->Person2)+))
    AND Person1.name = 'Alice'
) AS Q
WHERE Q.LastNode != 'Alice'

次の方法で共有

SHORTEST_PATH (Transact-SQL)

最短パス

FOR PATH

任意の長さのパターン

LAST_NODE

グラフパスの順序

グラフパス集計関数

STRING_AGG

LAST_VALUE

合計

COUNT

AVG

MIN

MAX

解説

例

A. 2 人の間の最短のパスを見つける

B. 特定のノードからグラフ内の他のすべてのノードへの最短パスを検索します。

C: グラフ内の 1 人のユーザーから別のユーザーに移動するために走査されたホップ/レベルの数をカウントします。

D. 特定のユーザーから 1 ~ 3 ホップ離れた人を見つける

E. 特定のユーザーから 2 ホップ離れた場所にあるユーザーを見つける

F. 特定の人から 1 ~ 3 ホップ離れた、特定のレストランが好きな人を見つける

G. 特定のノードからグラフ内の他のすべてのノードへの最短パスを検索します ("ループ" を除く)

次のステップ

フィードバック

その他のリソース

次の方法で共有

SHORTEST_PATH (Transact-SQL)

最短パス

FOR PATH

任意の長さのパターン

LAST_NODE

グラフ パスの順序

グラフ パス集計関数

STRING_AGG

LAST_VALUE

合計

COUNT

AVG

MIN

MAX

解説

例

A. 2 人の間の最短のパスを見つける

B. 特定のノードからグラフ内の他のすべてのノードへの最短パスを検索します。

C: グラフ内の 1 人のユーザーから別のユーザーに移動するために走査されたホップ/レベルの数をカウントします。

D. 特定のユーザーから 1 ~ 3 ホップ離れた人を見つける

E. 特定のユーザーから 2 ホップ離れた場所にあるユーザーを見つける

F. 特定の人から 1 ~ 3 ホップ離れた、特定のレストランが好きな人を見つける

G. 特定のノードからグラフ内の他のすべてのノードへの最短パスを検索します ("ループ" を除く)

次のステップ

フィードバック

その他のリソース

グラフパスの順序

グラフパス集計関数