SHORTEST_PATH (Transact-SQL)

Artikel
03/05/2025

gäller för: SQL Server 2019 (15.x) och senare versioner Azure SQL Database Azure SQL Managed Instance SQL-databas i Microsoft Fabric

Anger ett sökvillkor för ett diagram som genomsöks rekursivt eller repetitivt. SHORTEST_PATH kan användas i MATCH med grafnoder och kanttabeller i SELECT-instruktionen.

Transact-SQL syntaxkonventioner

Kortaste sökväg

Med funktionen SHORTEST_PATH kan du hitta:

En kortaste sökväg mellan två angivna noder/entiteter
Kortaste sökväg för enskild källa.
Kortaste sökvägen från flera källnoder till flera målnoder.

Det tar ett godtyckligt längdmönster som indata och returnerar en kortaste sökväg som finns mellan två noder. Den här funktionen kan bara användas i MATCH. Funktionen returnerar bara en kortaste sökväg mellan två angivna noder. Om det finns två eller flera kortaste sökvägar av samma längd mellan valfritt par av käll- och målnoder, returnerar funktionen bara en sökväg som hittades först under blädering. Ett godtyckligt längdmönster kan bara anges i en SHORTEST_PATH funktion.

Fullständig syntax finns i MATCH (SQL Graph).

FÖR SÖKVÄG

FOR PATH måste användas med valfritt nod- eller kanttabellnamn i FROM-satsen, som deltar i ett godtyckligt längdmönster. FOR PATH anger för motorn att nod- eller kanttabellen returnerar en ordnad samling som representerar listan över noder eller kanter som finns längs sökvägen. Attributen från dessa tabeller kan inte projiceras direkt i SELECT-satsen. Om du vill projicera attribut från dessa tabeller måste du använda aggregeringsfunktioner för grafsökvägar.

Mönster för godtycklig längd

Det här mönstret innehåller de noder och kanter som måste passeras upprepade gånger tills antingen:

Den önskade noden har nåtts.
Det maximala antalet iterationer som anges i mönstret uppfylls.

Följande två mönsterkvantifierare stöds:

'+': Upprepa mönstret 1 eller fler gånger. Avsluta så snart en kortaste sökväg hittas.
{1,n}: Upprepa mönstret 1 för att n gånger. Avsluta så snart en kortast hittas.

LAST_NODE

funktionen LAST_NODE() tillåter sammanlänkning av två godtyckliga längd bläddringsmönster. Den kan användas i scenarier där:

Mer än ett kortaste sökvägsmönster används i en fråga och ett mönster börjar vid den sista noden i föregående mönster.
Två kortaste sökvägsmönster sammanfogas på samma LAST_NODE().

Diagramsökvägsordning

Diagramsökvägsordning refererar till dataordningen i utdatasökvägen. Utdatasökvägsordningen startar alltid vid den icke-rekursiva delen av mönstret följt av de noder/kanter som visas i den rekursiva delen. Den ordning som diagrammet passerar under frågeoptimering/körning har inget att göra med den ordning som skrivs ut i utdata. På samma sätt påverkar pilriktningen i det rekursiva mönstret inte heller grafsökvägsordningen.

Mängdfunktioner för grafsökväg

Eftersom de noder och kanter som ingår i godtyckliga längdmönster returnerar en samling (av noder och kanter) som passerar i den sökvägen, kan användarna inte projicera attributen direkt med hjälp av syntaxen för konventionellt tablename.attributename. För frågor där det krävs för att projicera attributvärden från mellanliggande nod- eller kanttabeller använder du följande diagramsökvägsaggregeringsfunktioner i sökvägen: STRING_AGG, LAST_VALUE, SUM, AVG, MIN, MAX och COUNT. Den allmänna syntaxen för att använda dessa mängdfunktioner i SELECT-satsen är:

<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

Funktionen STRING_AGG tar ett uttryck och en avgränsare som indata och returnerar en sträng. Användare kan använda den här funktionen i SELECT-satsen för att projicera attribut från mellanliggande noder eller kanter i sökvägen som passerar.

LAST_VALUE

Om du vill projicera attribut från den sista noden i sökvägen som har bläddrats kan LAST_VALUE mängdfunktion användas. Det är ett fel att ange kanttabellalias som indata till den här funktionen, endast nodtabellnamn eller alias kan användas.

Last Node: Den sista noden refererar till den nod som visas sist i sökvägen, oavsett pilriktningen i MATCH-predikatet. Till exempel: MATCH(SHORTEST_PATH(n(-(e)->p)+) ). Här är den sista noden i sökvägen den senast besökta P-noden.

I mönstret MATCH(SHORTEST_PATH((n<-(e)-)+p)) är den sista noden den sista N-noden som besöktes.

SUMMA

Den här funktionen returnerar summan av angivna nod-/kantattributvärden eller -uttryck som visades i den bläddrade sökvägen.

RÄKNA

Den här funktionen returnerar antalet värden som inte är null för det angivna nod-/gränsattributet i sökvägen. Funktionen COUNT stöder inte operatorn * – försök att använda * resulterar i ett syntaxfel.

{  COUNT( <expression> )  <order_clause>  }

AVG

Returnerar medelvärdet för angivna nod-/gränsattributvärden eller -uttryck som visades i den bläddrade sökvägen.

MIN

Returnerar det minsta värdet från angivna nod-/kantattributvärden eller -uttryck som visades i den genomblästa sökvägen.

MAX

Returnerar det maximala värdet från angivna nod-/kantattributvärden eller -uttryck som visades i den bläddrade sökvägen.

Anmärkningar

Funktionen SHORTEST_PATH kan bara användas i MATCH.
Funktionen LAST_NODE stöds endast i SHORTEST_PATH.
Funktionen SHORTEST_PATH returnerar en kortaste sökväg mellan noder. Det stöder för närvarande inte att returnera alla kortaste sökvägar mellan noder. Det stöder inte heller att returnera alla sökvägar mellan noder.
Den SHORTEST_PATH implementeringen hittar en kortast väg som inte är viktad.
I vissa fall kan felaktiga planer genereras för frågor med högre antal hopp, vilket resulterar i högre frågekörningstider. Utvärdera om frågetips som ALTERNATIV (HASH JOIN) och/eller ALTERNATIV (MAXDOP 1) hjälper.

Exempel

För de exempelfrågor som visas här använder vi nod- och kanttabellerna som skapats i SQL Graph-exempel

A. Hitta kortaste sökvägen mellan två personer

I följande exempel hittar vi den kortaste sökvägen mellan Jacob och Alice. Vi behöver Person nod och friendOf edge som skapats från SQL Graph-exempel.

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. Hitta den kortaste sökvägen från en viss nod till alla andra noder i diagrammet.

I följande exempel hittar du alla personer som Jacob är ansluten till i grafen och den kortaste sökvägen från Jacob till alla dessa personer.

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. Räkna antalet hopp/nivåer som har bläddrats för att gå från en person till en annan i diagrammet.

I följande exempel hittar du den kortaste sökvägen mellan Jacob och Alice och skriver ut antalet hopp som krävs för att gå från Jacob till 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. Hitta personer 1-3 hopp bort från en viss person

I följande exempel hittar du den kortaste sökvägen mellan Jacob och alla personer som Jacob är ansluten till i grafen ett till tre hopp bort från honom.

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. Hitta människor exakt två hopp bort från en viss person

I följande exempel hittar du den kortaste sökvägen mellan Jacob och personer som är exakt två hopp bort från honom i diagrammet.

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. Hitta personer 1-3 hopp bort från en viss person, som också gillar en specifik restaurang

I följande exempel hittar du den kortaste vägen mellan Jacob och alla personer som han är ansluten till i grafen 1-3 hoppar bort från honom. Frågan filtrerar också anslutna personer genom att de gillar en viss restaurang. I exemplet nedan returnerar den LAST_NODE(Person2) den sista noden för varje kortaste sökväg. Den "sista" Person nod som hämtas från LAST_NODE kan sedan "länkas" för ytterligare bläddring för att hitta de restauranger som de gillar.

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. Hitta den kortaste sökvägen från en viss nod till alla andra noder i diagrammet, exklusive "loopar"

I följande exempel hittar du alla personer som Alice är ansluten till i diagrammet och den kortaste sökvägen från Alice till alla dessa personer. Exemplet söker uttryckligen efter "loopar" där start- och slutnoden för sökvägen råkar vara densamma.

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'

Dela via