SHORTEST_PATH (Transact-SQL)

Article
01/02/2025

S’applique à : SQL Server 2019 (15.x) et versions ultérieures d’Azure SQL Database Azure SQL Managed Instance SQL database dans Microsoft Fabric

Spécifie une condition de recherche pour un graphique, qui est recherché de manière récursive ou répétitive. SHORTEST_PATH pouvez être utilisé à l’intérieur de MATCH avec des tables de graphe et de bord, dans l’instruction SELECT.

Conventions de la syntaxe Transact-SQL

Chemin le plus court

La fonction SHORTEST_PATH vous permet de trouver :

Chemin le plus court entre deux nœuds/entités donnés
Chemin(s) le
Chemin le plus court entre plusieurs nœuds sources et plusieurs nœuds cibles.

Il prend un modèle de longueur arbitraire comme entrée et retourne un chemin le plus court qui existe entre deux nœuds. Cette fonction ne peut être utilisée qu’à l’intérieur de MATCH. La fonction ne retourne qu’un seul chemin le plus court entre deux nœuds donnés. S’il existe, deux chemins ou plus courts de la même longueur entre une paire de nœuds source et de destination, la fonction retourne un seul chemin trouvé en premier pendant la traversée. Un modèle de longueur arbitraire ne peut être spécifié qu’à l’intérieur d’une fonction SHORTEST_PATH.

Pour obtenir une syntaxe complète, reportez-vous à MATCH (SQL Graph).

FOR PATH

FOR PATH doit être utilisé avec n’importe quel nom de table de bord ou nœud dans la clause FROM, qui participe à un modèle de longueur arbitraire. FOR PATH indique au moteur que le nœud ou la table de bord retourne une collection ordonnée représentant la liste des nœuds ou des bords trouvés le long du chemin parcouru. Les attributs de ces tables ne peuvent pas être projetés directement dans la clause SELECT. Pour projeter des attributs à partir de ces tables, les fonctions d’agrégation de chemin d’accès au graphique doivent être utilisées.

Modèle de longueur arbitraire

Ce modèle inclut les nœuds et les arêtes qui doivent être parcourus à plusieurs reprises jusqu’à ce que :

Le nœud souhaité est atteint.
Le nombre maximal d’itérations spécifiées dans le modèle est atteint.

Les deux quantificateurs de modèle suivants sont pris en charge :

'+' : Répétez le modèle 1 ou plusieurs fois. Arrêtez dès qu’un chemin d’accès le plus court est trouvé.
{1,n} : répétez le modèle une à n fois. Terminez dès qu’un plus court est trouvé.

LAST_NODE

LAST_NODE() fonction autorise le chaînage de deux modèles de traversée de longueur arbitraire. Il peut être utilisé dans les scénarios où :

Plusieurs modèles de chemin d’accès les plus courts sont utilisés dans une requête et un modèle commence au dernier nœud du modèle précédent.
Deux modèles de chemin d’accès les plus courts fusionnent au même LAST_NODE().

Ordre des chemins d’accès au graphique

L’ordre du chemin d’accès au graphique fait référence à l’ordre des données dans le chemin de sortie. L’ordre du chemin de sortie commence toujours à la partie non récursive du modèle suivi des nœuds/arêtes qui apparaissent dans la partie récursive. L’ordre dans lequel le graphique est parcouru pendant l’optimisation/l’exécution des requêtes n’a rien à voir avec l’ordre imprimé dans la sortie. De même, la direction de la flèche dans le modèle récursif n’affecte pas l’ordre du chemin du graphique.

Fonctions d’agrégation de chemin d’accès au graphique

Étant donné que les nœuds et les arêtes impliqués dans le modèle de longueur arbitraire retournent une collection (des nœuds) et des bords parcourus dans ce chemin d’accès, les utilisateurs ne peuvent pas projeter les attributs directement à l’aide de la syntaxe tablename.attributename conventionnelle. Pour les requêtes où il est nécessaire de projeter des valeurs d’attribut à partir du nœud intermédiaire ou des tables de périphérie, dans le chemin parcouru, utilisez les fonctions d’agrégation de chemins de graphique suivantes : STRING_AGG, LAST_VALUE, SOMME, AVG, MIN, MAX et COUNT. La syntaxe générale pour utiliser ces fonctions d’agrégation dans la clause SELECT est la suivante :

<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 fonction STRING_AGG prend une expression et un séparateur comme entrée et retourne une chaîne. Les utilisateurs peuvent utiliser cette fonction dans la clause SELECT pour projeter des attributs à partir des nœuds intermédiaires ou des arêtes du chemin parcouru.

LAST_VALUE

Pour projeter des attributs à partir du dernier nœud du chemin parcouru, LAST_VALUE fonction d’agrégation peut être utilisée. Il s’agit d’une erreur pour fournir un alias de table edge en tant qu’entrée à cette fonction, seuls les noms ou alias de table de nœuds peuvent être utilisés.

Dernier nœud : le dernier nœud fait référence au nœud qui apparaît en dernier dans le chemin parcouru, quelle que soit la direction de la flèche dans le prédicat MATCH. Par exemple : MATCH(SHORTEST_PATH(n(-(e)->p)+) ). Ici, le dernier nœud du chemin est le dernier nœud P visité.

Dans le MATCH(SHORTEST_PATH((n<-(e)-)+p)) modèle, le dernier nœud est le dernier nœud visité.

SUM

Cette fonction retourne la somme des valeurs d’attribut ou d’attributs de périphérie fournies qui apparaissent dans le chemin d’accès parcouru.

COUNT

Cette fonction retourne le nombre de valeurs non null de l’attribut node/edge spécifié dans le chemin d’accès. La fonction COUNT ne prend pas en charge l’opérateur * : tentative d’utilisation des * résultats d’une erreur de syntaxe.

{  COUNT( <expression> )  <order_clause>  }

AVG

Retourne la moyenne des valeurs ou expressions d’attribut de nœud/edge fournies qui apparaissent dans le chemin d’accès parcouru.

MIN

Retourne la valeur minimale des valeurs d’attribut ou d’attributs de périphérie fournies qui apparaissent dans le chemin d’accès parcouru.

MAX

Retourne la valeur maximale des valeurs d’attribut ou d’attributs de périphérie fournies qui apparaissent dans le chemin d’accès parcouru.

Notes

La fonction SHORTEST_PATH ne peut être utilisée qu’à l’intérieur de MATCH.
La fonction LAST_NODE n’est prise en charge qu’à l’intérieur de SHORTEST_PATH.
La fonction SHORTEST_PATH retourne un chemin le plus court entre les nœuds. Il ne prend actuellement pas en charge le retour de tous les chemins les plus courts entre les nœuds ; il ne prend pas également en charge le retour de tous les chemins entre les nœuds.
L’implémentation SHORTEST_PATH recherche un chemin le plus court non pondéré.
Dans certains cas, des plans incorrects peuvent être générés pour les requêtes avec un plus grand nombre de tronçons, ce qui entraîne des temps d’exécution de requête plus élevés. Évaluez si les indicateurs de requête tels que OPTION (HASH JOIN) et /ou OPTION (MAXDOP 1) vous aident.

Exemples

Pour les exemples de requêtes présentés ici, nous utilisons les tables de nœud et de périphérie créées dans l’exemple SQL Graph

R : Trouver le chemin le plus court entre deux personnes

Dans l’exemple suivant, nous trouvons le chemin le plus court entre Jacob et Alice. Nous avons besoin du nœud et friendOf de la Person périphérie créés à partir de l’exemple SQL Graph.

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. Recherchez le chemin le plus court d’un nœud donné vers tous les autres nœuds du graphique.

L’exemple suivant recherche toutes les personnes auxquelles Jacob est connecté dans le graphique et le chemin le plus court commençant de Jacob à toutes ces personnes.

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. Comptez le nombre de sauts/niveaux parcourus pour passer d’une personne à une autre dans le graphique.

L’exemple suivant recherche le chemin le plus court entre Jacob et Alice et imprime le nombre de tronçons qu’il faut pour passer de 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. Trouver des gens 1-3 sauts loin d’une personne donnée

L’exemple suivant trouve le chemin le plus court entre Jacob et toutes les personnes auxquelles Jacob est connecté dans le graphique un à trois sauts loin de 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. Trouver des gens exactement deux sauts loin d’une personne donnée

L’exemple suivant trouve le chemin le plus court entre Jacob et les personnes qui sont exactement deux sauts loin de lui dans le graphique.

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. Trouver des gens 1-3 sauts loin d’une personne donnée, qui aime aussi un restaurant spécifique

L’exemple suivant trouve le chemin le plus court entre Jacob et toutes les personnes auxquelles il est connecté dans le graphique 1-3 sauts de lui. La requête filtre également les personnes connectées par leur goût d’un restaurant donné. Dans l’exemple ci-dessous, qui LAST_NODE(Person2) retourne le nœud final pour chaque chemin le plus court. Le nœud « dernier » Person obtenu à partir LAST_NODE de peut ensuite être « chaîné » pour d’autres traversées pour trouver le ou les restaurants qu’ils aiment.

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. Recherchez le chemin le plus court d’un nœud donné vers tous les autres nœuds du graphique, à l’exclusion des « boucles »

L’exemple suivant recherche toutes les personnes auxquelles Alice est connectée dans le graphique et le chemin le plus court commençant d’Alice à toutes ces personnes. L’exemple vérifie explicitement les « boucles » où le début et le nœud final du chemin d’accès sont identiques.

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'

Partager via