分享方式:


SHORTEST_PATH (Transact-SQL)

適用于: SQL Server 2019 (15.x) 和更新版本的 Azure SQL Database Azure SQL 受控實例

指定以遞迴或重複方式搜尋的圖表搜尋條件。 在 SELECT 語句中,SHORTEST_PATH可以搭配圖形節點和邊緣資料表在 MATCH 內使用。

Transact-SQL 語法慣例

最短路徑

SHORTEST_PATH函式可讓您找到:

  • 兩個指定節點/實體之間的最短路徑
  • 單一來源最短路徑(s)。
  • 從多個來源節點到多個目標節點的最短路徑。

它會採用任意長度模式作為輸入,並傳回兩個節點之間存在的最短路徑。 此函式只能在 MATCH 內使用。 函式只會傳回任兩個指定節點之間的最短路徑。 如果有任何來源和目的地節點之間相同長度的兩個或多個最短路徑,則函式只會傳回周遊期間第一個找到的一個路徑。 任意長度模式只能在SHORTEST_PATH函式內指定。

如需完整的語法,請參閱 MATCH (SQL Graph)。

FOR PATH

FOR PATH 必須與 FROM 子句中的任何節點或邊緣資料表名稱搭配使用,該子句會參與任意長度模式。 FOR PATH 會告知引擎節點或邊緣資料表傳回已排序的集合,代表沿著路徑周遊找到的節點或邊緣清單。 這些資料表中的屬性無法直接投影在 SELECT 子句中。 若要從這些資料表投影屬性,必須使用圖表路徑彙總函式。

任意長度模式

此模式包含必須重複周遊的節點和邊緣,直到下列其中一項:

  • 達到所需的節點。
  • 符合模式中指定的反復專案數目上限。

支援下列兩種模式數量詞:

  • '+' :重複模式 1 次或多次。 在找到最短路徑後立即終止。
  • {1,n}:模式 1 重複 n 次。 在找到最短時立即終止。

LAST_NODE

LAST_NODE() 函式允許鏈結兩個任意長度周遊模式。 其可用於下列案例:

  • 查詢中會使用一個以上的最短路徑模式,一個模式會從上一個模式的 LAST 節點開始。
  • 兩個最短的路徑模式會在相同的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>  }

平均

傳回出現在周遊路徑中之提供的節點/邊緣屬性值或運算式的平均值。

最小值

從所提供之節點/邊緣屬性值或出現在周遊路徑中的運算式,傳回最小值。

最大值

從所提供之節點/邊緣屬性值或出現在周遊路徑中的運算式,傳回最大值。

備註

  • SHORTEST_PATH函式只能在 MATCH 內使用。
  • LAST_NODE函式僅在SHORTEST_PATH內支援。
  • SHORTEST_PATH函式會 傳回節點之間的任何 最短路徑。 它目前不支援傳 回節點之間的所有最短路徑 ;它也不支援傳 回節點之間的所有路徑
  • SHORTEST_PATH實作會尋找未加權的最短路徑。
  • 在某些情況下,可能會針對具有較高躍點數目的查詢產生不正確的計畫,這會導致查詢執行時間較高。 評估 OPTION (HASH JOIN) 和 / 或 OPTION (MAXDOP 1) 等查詢提示是否有協助。

範例

針對此處顯示的範例查詢,我們使用在 SQL Graph 範例中建立的 節點和邊緣資料表

A. 尋找兩個人之間的最短路徑

在下列範例中,我們發現 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. 尋找從指定節點到圖形中所有其他節點的最短路徑。

下列範例會尋找雅各在圖表中連接的所有人員,以及從雅各到所有這些人最短的路徑。

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. 計算周遊的躍點/層級數目,以從圖表中的一個人到另一個人。

下列範例會尋找雅各和 Alice 之間的最短路徑,並列印從 Jacob 到 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 跳離指定人員的人

下列範例會尋找雅各與雅各在圖表中連接的最短路徑,從他身邊一到三個躍點。

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. 尋找離指定人員只有兩個躍點的人

下列範例會尋找雅各與圖表中離他只有兩個躍點的人之間的最短路徑。

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'

下一步