SHORTEST_PATH (T-SQL)

Artikel
06/29/2023

Berlaku untuk: SQL Server 2019 (15.x) dan azure SQL Database Azure SQL Managed Instance yang lebih baru

Menentukan kondisi pencarian untuk grafik, yang dicari secara rekursif atau berulang. SHORTEST_PATH dapat digunakan di dalam MATCH dengan simpul grafik dan tabel tepi, dalam pernyataan SELECT.

Konvensi sintaks transact-SQL

Jalur terpendek

Fungsi SHORTEST_PATH memungkinkan Anda menemukan:

Jalur terpendek antara dua simpul/entitas yang diberikan
Jalur terpendek sumber tunggal.
Jalur terpendek dari beberapa simpul sumber ke beberapa simpul target.

Dibutuhkan pola panjang arbitrer sebagai input dan mengembalikan jalur terpendek yang ada di antara dua simpul. Fungsi ini hanya dapat digunakan di dalam MATCH. Fungsi ini hanya mengembalikan satu jalur terpendek antara dua simpul yang diberikan. Jika ada, dua atau lebih jalur terpendek dengan panjang yang sama antara sepasang node sumber dan tujuan, fungsi hanya mengembalikan satu jalur yang ditemukan terlebih dahulu selama traversal. Pola panjang arbitrer hanya dapat ditentukan di dalam fungsi SHORTEST_PATH.

Untuk sintaks lengkap, lihat MATCH (SQL Graph).

UNTUK JALUR

FOR PATH harus digunakan dengan node atau nama tabel edge apa pun dalam klausul FROM, yang berpartisipasi dalam pola panjang arbitrer. FOR PATH memberi tahu mesin bahwa simpul atau tabel tepi mengembalikan koleksi yang diurutkan yang mewakili daftar simpul atau tepi yang ditemukan di sepanjang jalur yang dilalui. Atribut dari tabel ini tidak dapat diproyeksikan langsung dalam klausa SELECT. Untuk memproyeksikan atribut dari tabel ini, fungsi agregat jalur grafik harus digunakan.

Pola panjang arbitrer

Pola ini mencakup simpul dan tepi yang harus dilalui berulang kali hingga:

Simpul yang diinginkan tercapai.
Jumlah maksimum perulangan seperti yang ditentukan dalam pola terpenuhi.

Dua kuantifer pola berikut didukung:

'+': Ulangi pola 1 atau lebih kali. Hentikan segera setelah jalur terpendek ditemukan.
{1,n}: Ulangi pola 1 hingga n kali. Hentikan segera setelah terpendek ditemukan.

LAST_NODE

fungsi LAST_NODE() memungkinkan penautan dua pola traversal panjang arbitrer. Ini dapat digunakan dalam skenario di mana:

Lebih dari satu pola jalur terpendek digunakan dalam kueri dan satu pola dimulai pada simpul TERAKHIR dari pola sebelumnya.
Dua pola jalur terpendek bergabung pada LAST_NODE() yang sama.

Urutan jalur grafik

Urutan jalur grafik mengacu pada urutan data di jalur output. Urutan jalur output selalu dimulai pada bagian pola yang tidak aman diikuti oleh simpul/tepi yang muncul di bagian rekursif. Urutan di mana grafik dilalui selama pengoptimalan/eksekusi kueri tidak ada hubungannya dengan urutan yang dicetak dalam output. Demikian pula, arah panah dalam pola rekursif juga tidak memengaruhi urutan jalur grafik.

Fungsi agregat jalur grafik

Karena simpul dan tepi yang terlibat dalam pola panjang arbitrer mengembalikan koleksi (dari simpul dan tepi yang dilalui di jalur tersebut), pengguna tidak dapat memproyeksikan atribut secara langsung menggunakan sintaks tablename.attributename konvensional. Untuk kueri di mana diperlukan untuk memproyeksikan nilai atribut dari simpul menengah atau tabel tepi, di jalur yang dilalui, gunakan fungsi agregat jalur grafik berikut: STRING_AGG, LAST_VALUE, SUM, AVG, MIN, MAX, dan COUNT. Sintaks umum untuk menggunakan fungsi agregat ini dalam klausa SELECT adalah:

<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

Fungsi STRING_AGG mengambil ekspresi dan pemisah sebagai input dan mengembalikan string. Pengguna dapat menggunakan fungsi ini dalam klausul SELECT untuk memproyeksikan atribut dari simpul atau tepi perantara di jalur yang dilalui.

LAST_VALUE

Untuk memproyeksikan atribut dari simpul terakhir jalur yang dilalui, fungsi agregat LAST_VALUE dapat digunakan. Ini adalah kesalahan untuk menyediakan alias tabel edge sebagai input ke fungsi ini, hanya nama tabel simpul atau alias yang dapat digunakan.

Simpul Terakhir: Simpul terakhir mengacu pada simpul yang muncul terakhir di jalur yang dilalui, terlepas dari arah panah dalam predikat MATCH. Misalnya: MATCH(SHORTEST_PATH(n(-(e)->p)+) ). Di sini simpul terakhir di jalur adalah simpul P terakhir yang dikunjungi.

MATCH(SHORTEST_PATH((n<-(e)-)+p)) Dalam pola, simpul terakhir adalah simpul N terakhir yang dikunjungi.

SUM

Fungsi ini mengembalikan jumlah nilai atau ekspresi atribut node/edge yang disediakan yang muncul di jalur yang dilalui.

COUNT

Fungsi ini mengembalikan jumlah nilai non-null dari atribut node/edge yang ditentukan di jalur. Fungsi COUNT tidak mendukung * operator - penggunaan hasil yang dicoba * dalam kesalahan sintaks.

{  COUNT( <expression> )  <order_clause>  }

AVG

Mengembalikan rata-rata nilai atau ekspresi atribut node/edge yang disediakan yang muncul di jalur yang dilalui.

MIN

Mengembalikan nilai minimum dari nilai atribut node/edge yang disediakan atau ekspresi yang muncul di jalur yang dilalui.

MAX

Mengembalikan nilai maksimum dari nilai atribut node/edge yang disediakan atau ekspresi yang muncul di jalur yang dilalui.

Keterangan

Fungsi SHORTEST_PATH hanya dapat digunakan di dalam MATCH.
Fungsi LAST_NODE hanya didukung di dalam SHORTEST_PATH.
Fungsi SHORTEST_PATH mengembalikan satu jalur terpendek antara simpul. Saat ini tidak mendukung pengembalian semua jalur terpendek antar simpul; ini juga tidak mendukung pengembalian semua jalur antar simpul.
Implementasi SHORTEST_PATH menemukan jalur terpendek yang tidak tertahankan.
Dalam beberapa kasus, rencana buruk dapat dihasilkan untuk kueri dengan jumlah hop yang lebih tinggi, yang menghasilkan waktu eksekusi kueri yang lebih tinggi. Evaluasi apakah petunjuk kueri seperti BANTUAN OPTION (HASH JOIN) dan / atau OPTION (MAXDOP 1).

Contoh

Untuk contoh kueri yang diperlihatkan di sini, kami menggunakan tabel simpul dan tepi yang dibuat dalam sampel SQL Graph

J. Temukan jalur terpendek antara dua orang

Dalam contoh berikut, kita menemukan jalur terpendek antara Jacob dan Alice. Kita memerlukan simpul dan tepi yang Person dibuat dari sampel SQL Graph.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. Temukan jalur terpendek dari simpul tertentu ke semua simpul lain dalam grafik.

Contoh berikut menemukan semua orang yang terhubung dengan Jacob dalam grafik dan jalur terpendek mulai dari Jacob ke semua orang tersebut.

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. Hitung jumlah hop/tingkat yang dilalui untuk berpindah dari satu orang ke orang lain dalam grafik.

Contoh berikut menemukan jalur terpendek antara Jacob dan Alice dan mencetak jumlah hop yang diperlukan untuk pergi dari Jacob ke 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. Temukan orang 1-3 lompatan jauh dari orang tertentu

Contoh berikut menemukan jalur terpendek antara Yakub dan semua orang yang terhubung dengan Jacob dalam grafik satu hingga tiga lompatan menjauh darinya.

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. Temukan orang tepat dua lompatan jauh dari orang tertentu

Contoh berikut menemukan jalur terpendek antara Yakub dan orang-orang yang tepat dua lompatan menjauh darinya dalam grafik.

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. Temukan orang 1-3 lompatan jauh dari orang tertentu, yang juga menyukai restoran tertentu

Contoh berikut menemukan jalur terpendek antara Yakub dan semua orang yang terhubung dengannya dalam grafik 1-3 lompatan menjauh darinya. Kueri juga memfilter orang yang terhubung dengan menyukai restoran tertentu. Dalam sampel di bawah ini, yang LAST_NODE(Person2) mengembalikan simpul akhir untuk setiap jalur terpendek. Simpul "terakhir" Person yang diperoleh kemudian LAST_NODE dapat "ditautkan" untuk traversal lebih lanjut untuk menemukan restoran yang mereka sukai.

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. Temukan jalur terpendek dari simpul tertentu ke semua simpul lain dalam grafik, tidak termasuk "perulangan"

Contoh berikut menemukan semua orang yang terhubung dengan Alice dalam grafik dan jalur terpendek mulai dari Alice ke semua orang tersebut. Contohnya secara eksplisit memeriksa "perulangan" di mana node awal dan akhir jalur terjadi sama.

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'

Bagikan melalui