SHORTEST_PATH (Transact-SQL)

[アーティクル]
06/29/2023

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

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

最短パス

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

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

入力として任意の長さのパターンを受け取り、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 つのクエリで複数の最短パスパターンが使用され、1 つのパターンが前のパターンの LAST ノードから始まります。
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 ノードです。

[SUM]

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

[COUNT]

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

{  COUNT( <expression> )  <order_clause>  }

AVG

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

[MIN]

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

[MAX]

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

注釈

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

例

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

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

次の例では、Jacob と Alice の間の最短パスを見つけます。 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 が接続されているすべてのユーザーをグラフで検索し、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

[SUM]

[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

[SUM]

[COUNT]

AVG

[MIN]

[MAX]

注釈

例

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

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

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

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

E. 特定の人からちょうど 2 ホップ離れた人を見つける

F. 特定の人から 1 から 3 ホップ離れた人を見つける。特定のレストランも好きです

G. 特定のノードからグラフ内の他のすべてのノードへの最短パス ("ループ" を除く) を見つける

次のステップ

フィードバック

その他のリソース

グラフパスの順序

グラフパス集計関数