SHORTEST_PATH (Transact-SQL)

Si applica a: sìSQL Server 2019 (15.x) Sìdatabase SQL di Azure SìIstanza gestita di SQL di Azure

Specifica una condizione di ricerca per un grafo, che viene ricercata in modo ricorsivo o ripetitivo. SHORTEST_PATH può essere usato all'interno di MATCH con nodi del grafo e tabelle perimetrali, nell'istruzione SELECT.

Icona di collegamento a un argomento Convenzioni della sintassi Transact-SQL

Percorso più breve

La SHORTEST_PATH funzione consente di trovare:

  • Un percorso più breve tra due nodi/entità specifiche
  • Percorsi più brevi di origine singola.
  • Percorso più breve da più nodi di origine a più nodi di destinazione.

Accetta un modello di lunghezza arbitraria come input e restituisce un percorso più breve esistente tra due nodi. Questa funzione può essere usata solo all'interno di MATCH. La funzione restituisce solo un percorso più breve tra due nodi. Se sono presenti due o più percorsi più brevi della stessa lunghezza tra una coppia di nodi di origine e di destinazione, la funzione restituisce un solo percorso trovato per primo durante l'attraversamento. Si noti che un modello di lunghezza arbitraria può essere specificato solo all'interno di una SHORTEST_PATH funzione.

Per la sintassi, fare riferimento a MATCH (GRAFO SQL).

FOR PATH

FOR PATH deve essere usato con qualsiasi nome di nodo o tabella perimetrale nella clausola FROM, che farà parte di un modello di lunghezza arbitraria. FOR PATH indica al motore che il nodo o la tabella perimetrale restituirà una raccolta ordinata che rappresenta l'elenco di nodi o bordi trovati lungo il percorso attraversato. Gli attributi di queste tabelle non possono essere proiettati direttamente nella clausola SELECT. Per proiettare gli attributi da queste tabelle, è necessario usare le funzioni di aggregazione del percorso del grafo.

Modello di lunghezza arbitraria

Questo modello include i nodi e i bordi che devono essere attraversati ripetutamente fino a quando non viene raggiunto il nodo desiderato o fino a quando non viene raggiunto il numero massimo di iterazioni specificato nel modello. Ogni volta che viene eseguita la query, il risultato dell'esecuzione di questo modello sarà una raccolta ordinata dei nodi e dei bordi attraversati lungo il percorso dal nodo iniziale al nodo finale. Si tratta di un modello di sintassi dello stile di espressione regolare e sono supportati i due quantificatori di criteri seguenti:

  • '+': ripetere il modello 1 o più volte. Terminare non appena viene trovato un percorso più breve.
  • {1,n} : Ripetere il criterio da una a "n" volte. Terminare non appena viene trovato un valore più breve.

LAST_NODE

LAST_NODE() consente il concatenamento di due modelli di attraversamento di lunghezza arbitraria. Può essere usato negli scenari in cui:

  • In una query vengono usati più modelli di percorso più brevi e un criterio inizia in corrispondenza del nodo LAST del modello precedente.
  • Due modelli di percorso più brevi si uniscono nello stesso LAST_NODE().

Ordine dei percorsi dei grafi

L'ordine del percorso del grafo si riferisce all'ordine dei dati nel percorso di output. L'ordine del percorso di output inizia sempre in corrispondenza della parte non ricorsiva del modello seguita dai nodi/bordi visualizzati nella parte ricorsiva. L'ordine di attraversamento del grafo durante l'ottimizzazione/esecuzione delle query non ha nulla a che fare con l'ordine stampato nell'output. Analogamente, anche la direzione della freccia nel modello ricorsivo non influisce sull'ordine del percorso del grafico.

Funzioni di aggregazione percorso grafo

Poiché i nodi e i bordi coinvolti nel modello di lunghezza arbitraria restituiscono una raccolta (di nodi e bordi attraversati in tale percorso), gli utenti non possono proiettare gli attributi direttamente usando la sintassi tablename.attributename convenzionale. Per le query in cui è necessario proiettare i valori degli attributi dal nodo intermedio o dalle tabelle perimetrali, nel percorso attraversato usare le funzioni di aggregazione del percorso del grafo seguenti: STRING_AGG, LAST_VALUE, SUM, AVG, MIN, MAX e COUNT. La sintassi generale per usare queste funzioni di aggregazione nella clausola SELECT è la seguente:

<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

La STRING_AGG accetta un'espressione e un separatore come input e restituisce una stringa. Gli utenti possono usare questa funzione nella clausola SELECT per proiettare gli attributi dai nodi intermedi o dai bordi del percorso attraversato.

LAST_VALUE

Per proiettare gli attributi dall'ultimo nodo del percorso attraversato, LAST_VALUE funzione di aggregazione. È un errore fornire l'alias della tabella perimetrale come input per questa funzione. È possibile usare solo i nomi o gli alias delle tabelle dei nodi.

Ultimo nodo: l'ultimo nodo fa riferimento al nodo visualizzato per ultimo nel percorso attraversato, indipendentemente dalla direzione della freccia nel predicato MATCH. Ad esempio: MATCH(SHORTEST_PATH(n(-(e)->p)+) ). Qui l'ultimo nodo nel percorso sarà l'ultimo nodo P visitato.

Mentre l'ultimo nodo è l'ultimo nodo N nel percorso del grafo di output per questo modello: MATCH(SHORTEST_PATH((n<-(e)-)+p))

SUM

Questa funzione restituisce la somma dei valori dell'attributo node/edge specificati o dell'espressione visualizzata nel percorso attraversato.

COUNT

Questa funzione restituisce il numero di valori non Null dell'attributo node/edge desiderato nel percorso. La funzione COUNT supporta l'operatore ' * ' con un alias di nodo o di tabella perimetrale. Senza l'alias del nodo o della tabella perimetrale, l'utilizzo di è * ambiguo e restituirà un errore.

{  COUNT( <expression> | <node_or_edge_alias>.* )  <order_clause>  }

MEDIA

Restituisce la media dei valori dell'attributo node/edge specificati o dell'espressione visualizzata nel percorso attraversato.

MIN

Restituisce il valore minimo dai valori dell'attributo node/edge specificati o dall'espressione visualizzata nel percorso attraversato.

MAX

Restituisce il valore massimo dai valori dell'attributo node/edge specificati o dall'espressione visualizzata nel percorso attraversato.

Commenti

  • La SHORTEST_PATH può essere usata solo all'interno di MATCH.
  • La LAST_NODE è supportata solo all'interno di SHORTEST_PATH.
  • La SHORTEST_PATH funzione restituirà un percorso più breve tra i nodi. Attualmente non supporta la restituzione di tutti i percorsi più brevi tra i nodi. non supporta anche la restituzione di tutti i percorsi tra i nodi.
  • L SHORTEST_PATH appalto trova un percorso più breve non ponderato.
  • In alcuni casi, possono essere generati piani non corretti per le query con un numero maggiore di hop, con tempi di esecuzione delle query più elevati. Valutare se gli hint di query come OPTION (HASH JOIN) e/o OPTION (MAXDOP 1) sono utili.

Esempio

Per le query di esempio illustrate di seguito, vengono sfruttate le tabelle di nodi e perimetrali create nell'esempio di grafico SQL

A. Trovare il percorso più breve tra 2 persone

Nell'esempio seguente viene trovato il percorso più breve tra Giacobbe e Alice. Saranno necessari il nodo Person e friendOf edge creati dallo script di esempio del grafo.

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. Trovare il percorso più breve da un determinato nodo a tutti gli altri nodi nel grafico.

L'esempio seguente trova tutte le persone a cui è connesso Jacobbe nel grafo e il percorso più breve che inizia da Giacobbe a tutte queste persone.

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. Contare il numero di hop/livelli attraversati per passare da una persona a un'altra nel grafico.

L'esempio seguente trova il percorso più breve tra Giacobbe e Alice e stampa il numero di hop necessari per passare da Giacobbe ad 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. Trovare le persone a 1-3 hop da una determinata persona

L'esempio seguente trova il percorso più breve tra Giacobbe e tutte le persone a cui è connesso nel grafo a 1-3 hop di distanza da lui.

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. Trovare le persone esattamente a 2 hop da una determinata persona

L'esempio seguente trova il percorso più breve tra Giacobbe e le persone che si trovano esattamente a 2 hop di distanza da lui nel grafico.

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. Trovare le persone a 1-3 hop da una determinata persona, a cui piace anche un ristorante specifico

L'esempio seguente trova il percorso più breve tra Giacobbe e tutte le persone a cui è connesso nel grafo a 1-3 hop di distanza da lui; e filtra anche solo le persone connesse in base al loro gradimento per un determinato ristorante. Si noti nell'esempio seguente che LAST_NODE(Person2) restituisce il nodo finale per ogni attraversamento del percorso più breve, consentendo così a tale nodo Person di essere "concatenato" per altri attraversamenti per trovare i ristoranti a cui piace.

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. Trovare il percorso più breve da un determinato nodo a tutti gli altri nodi nel grafico, escludendo i "cicli".

L'esempio seguente trova tutte le persone a cui è connesso Jacobbe nel grafico e il percorso più breve che inizia da Alice a tutte queste persone. Nell'esempio viene verificata in modo esplicito la presenza di "cicli" in cui il nodo iniziale e il nodo finale del percorso sono uguali.

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'

Vedere anche

MATCH (grafo SQL) CREATE TABLE (grafico SQL) INSERT (grafo SQL)] Elaborazione di grafi con SQL Server 2017