Condividi tramite

SHORTEST_PATH (Transact-SQL)

  • Articolo

Si applica a: SQL Server 2019 (15.x) e versioni successive di Istanza gestita di SQL di Azure

Specifica una condizione di ricerca per un grafico, che viene eseguita la ricerca in modo ricorsivo o ripetitivo. SHORTEST_PATH può essere usato all'interno di MATCH con tabelle del nodo del grafo e dei bordi, nell'istruzione SELECT.

Convenzioni di sintassi Transact-SQL

Percorso più breve

La funzione SHORTEST_PATH consente di trovare:

  • Percorso più breve tra due nodi/entità specificati
  • Percorso/i più breve di origine singola.
  • Percorso più breve da più nodi di origine a più nodi di destinazione.

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

Per una sintassi completa, vedere MATCH (SQL Graph).

FOR PATH

FOR PATH deve essere usato con qualsiasi nome di tabella nodo o bordo nella clausola FROM, che partecipa a un criterio di lunghezza arbitrario. FOR PATH indica al motore che il nodo o la tabella perimetrale restituisce una raccolta ordinata che rappresenta l'elenco di nodi o archi trovati lungo il percorso attraversato. Gli attributi di queste tabelle non possono essere proiettati direttamente nella clausola SELECT. Per proiettare gli attributi di queste tabelle, è necessario usare le funzioni di aggregazione del percorso del grafico.

Modello di lunghezza arbitrario

Questo modello include i nodi e i bordi che devono essere attraversati ripetutamente fino a quando:

  • Viene raggiunto il nodo desiderato.
  • Viene soddisfatto il numero massimo di iterazioni specificate nel modello.

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 modello da 1 a n volte. Termina non appena viene trovato un più breve.

LAST_NODE

LAST_NODE() funzione 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 modello inizia nel nodo LAST del modello precedente.
  • Due modelli di percorso più brevi si uniscono allo stesso LAST_NODE().

Ordine percorso grafico

L'ordine del percorso del grafo fa riferimento all'ordine dei dati nel percorso di output. L'ordine del percorso di output inizia sempre nella parte non ricorsiva del modello seguito dai nodi/bordi visualizzati nella parte ricorsiva. L'ordine in cui il grafico viene attraversato durante l'ottimizzazione/esecuzione della 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 grafo.

Funzioni di aggregazione del percorso grafico

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 dalle tabelle intermedie del nodo o dei bordi, nel percorso attraversato, usare le funzioni di aggregazione del percorso del grafico seguenti: STRING_AGG, LAST_VALUE, SUM, AVG, MIN, MAX e COUNT. La sintassi generale per usare queste funzioni di aggregazione nella clausola 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

La funzione 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, è possibile usare LAST_VALUE funzione di aggregazione. Si tratta di un errore per specificare l'alias della tabella edge 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 è l'ultimo nodo P visitato.

MATCH(SHORTEST_PATH((n<-(e)-)+p)) Nel modello, l'ultimo nodo è l'ultimo nodo N visitato.

SUM

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

COUNT

Questa funzione restituisce il numero di valori non Null dell'attributo node/edge specificato nel percorso. La funzione COUNT non supporta l'operatore * . Tentativo di utilizzo dei risultati in un errore di * sintassi.

{  COUNT( <expression> )  <order_clause>  }

AVG

Restituisce la media dei valori dell'attributo node/edge forniti o dell'espressione visualizzati 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 forniti o dall'espressione visualizzata nel percorso attraversato.

Osservazioni:

  • La funzione SHORTEST_PATH può essere usata solo all'interno di MATCH.
  • La funzione LAST_NODE è supportata solo all'interno di SHORTEST_PATH.
  • La funzione SHORTEST_PATH restituisce un percorso più breve tra i nodi. Attualmente non supporta la restituzione di tutti i percorsi più brevi tra i nodi, ma non supporta anche la restituzione di tutti i percorsi tra i nodi.
  • L'implementazione SHORTEST_PATH trova un percorso più breve senza pesi.
  • In alcuni casi, i piani non corretti possono essere generati per le query con un numero più elevato di hop, che comporta tempi di esecuzione delle query più elevati. Valutare se gli hint per la query, ad esempio OPTION (HASH JOIN) e/o OPTION (MAXDOP 1) help.

Esempi

Per le query di esempio illustrate di seguito, vengono usate le tabelle node e edge create nell'esempio di grafo SQL

R. Trovare il percorso più breve tra due persone

Nell'esempio seguente si trova il percorso più breve tra Jacob e Alice. È necessario il nodo e friendOf il Person bordo creati dall'esempio di grafo SQL.

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 Jacob è connesso nel grafico e il percorso più breve che inizia da Jacob a tutte quelle 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 Jacob e Alice e stampa il numero di hop necessari per passare da Jacob 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 persone da 1 a 3 hop da una persona specifica

L'esempio seguente trova il percorso più breve tra Jacob e tutte le persone a cui Jacob è collegato nel grafico uno a tre hop lontano 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 persone esattamente due hop lontano da una persona specifica

L'esempio seguente trova il percorso più breve tra Jacob e le persone che sono esattamente due hop lontano 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 persone 1-3 hops lontano da una persona specifica, che anche come un ristorante specifico

L'esempio seguente trova il percorso più breve tra Jacob e tutte le persone a cui è connesso nel grafico 1-3 salta via da lui. La query filtra anche le persone connesse in base alle proprie esigenze di un determinato ristorante. Nell'esempio seguente, che LAST_NODE(Person2) restituisce il nodo finale per ogni percorso più breve. Il nodo "ultimo" Person ottenuto da LAST_NODE può quindi essere "concatenato" per ulteriori attraversamenti per trovare i ristoranti che preferiscono.

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, esclusi i "cicli"

Nell'esempio seguente vengono trovate tutte le persone a cui Alice è connessa nel grafico e il percorso più breve che inizia da Alice a tutte le persone. L'esempio verifica in modo esplicito la presenza di "cicli" in cui l'inizio 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'

Passaggi successivi