SHORTEST_PATH (Transact-SQL)

Article
06/29/2023

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

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 nœud et de bord de graphe, dans l’instruction SELECT.

Conventions de la syntaxe Transact-SQL

Chemin le plus court

La fonction SHORTEST_PATH vous permet de rechercher :

Chemin d’accès le plus court entre deux nœuds/entités donnés
Chemin(s) le(
Chemin d’accès le plus court de plusieurs nœuds sources vers plusieurs nœuds cibles.

Il prend un modèle de longueur arbitraire comme entrée et retourne un chemin d’accès le plus court qui existe entre deux nœuds. Cette fonction ne peut être utilisée qu’à l’intérieur de MATCH. La fonction retourne un seul chemin le plus court entre deux nœuds donnés. S’il existe deux ou plusieurs chemins d’accès les plus courts de la même longueur entre une ou plusieurs paires de nœuds source et de destination, la fonction ne retourne qu’un seul chemin qui a été trouvé en premier lors de 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 la syntaxe complète, reportez-vous à MATCH (SQL Graph).

FOR PATH

FOR PATH doit être utilisé avec n’importe quel nom de nœud ou de table de périphérie dans la clause FROM, qui participe à un modèle de longueur arbitraire. FOR PATH indique au moteur que le nœud ou la table d’arêtes retourne une collection ordonnée représentant la liste des nœuds ou arêtes 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 de graphe 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é dans le modèle est atteint.

Les deux quantificateurs de modèles 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() permet le chaînage de deux modèles de traversée de longueur arbitraire. Il peut être utilisé dans des 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.
Les deux modèles de chemin les plus courts se fusionnent au même LAST_NODE().

Ordre des chemins de graphique

L’ordre des chemins de 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 graphe 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 non plus l’ordre du chemin du graphe.

Fonctions d’agrégation de chemin de graphe

Étant donné que les nœuds et les arêtes impliqués dans le modèle de longueur arbitraire retournent une collection (de nœuds et d’arêtes parcourus dans ce chemin), les utilisateurs ne peuvent pas projeter les attributs directement à l’aide de la syntaxe tablename.attributename conventionnelle. Pour les requêtes pour lesquelles il est nécessaire de projeter des valeurs d’attribut à partir des tables de nœud ou de périphérie intermédiaires, dans le chemin parcouru, utilisez les fonctions d’agrégation de chemin de graphe 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 dans le 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 de fournir un alias de table de périphérie comme entrée à cette fonction. Seuls les noms de table de nœuds ou les alias 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 d’accès 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 N visité.

SUM

Cette fonction retourne la somme des valeurs ou expression d’attribut de nœud/edge fournies qui sont apparues dans le chemin parcouru.

COUNT

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

{  COUNT( <expression> )  <order_clause>  }

AVG

Retourne la moyenne des valeurs ou de l’expression d’attribut de nœud/edge fournies qui sont apparues dans le chemin parcouru.

MIN

Retourne la valeur minimale des valeurs ou de l’expression d’attribut de nœud/edge fournies qui sont apparues dans le chemin d’accès parcouru.

MAX

Retourne la valeur maximale de l’expression ou des valeurs d’attribut de nœud/arête fournies qui sont apparues dans le chemin parcouru.

Notes

La fonction SHORTEST_PATH ne peut être utilisée qu’à l’intérieur de MATCH.
La fonction LAST_NODE est uniquement prise en charge à l’intérieur de SHORTEST_PATH.
La fonction SHORTEST_PATH retourne un chemin d’accès le plus court entre les nœuds. Actuellement, il ne prend pas en charge le retour de tous les chemins d’accès les plus courts entre les nœuds ; il ne prend pas non plus en charge le retour de tous les chemins d’accès 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 nombre plus élevé de tronçons, ce qui entraîne des temps d’exécution des requêtes plus élevés. Évaluez si les indicateurs de requête comme OPTION (HASH JOIN) et/ou OPTION (MAXDOP 1) 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 graphe.

L’exemple suivant recherche toutes les personnes auxquelles Jacob est connecté dans le graphique et le chemin le plus court à partir de Jacob pour 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 tronçons/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 affiche le nombre de sauts 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 personnes à 1-3 sauts 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 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 personnes exactement à deux sauts d’une personne donnée

L’exemple suivant trouve le chemin le plus court entre Jacob et les personnes qui se trouvent exactement à deux sauts 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 houblons 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 selon 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 « dernier » Person nœud obtenu à partir de LAST_NODE peut ensuite être « chaîné » pour les autres traversées afin de 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 d’accès le plus court d’un nœud donné à tous les autres nœuds du graphe, à l’exclusion des « boucles »

L’exemple suivant recherche toutes les personnes auxquelles Alice est connectée dans le graphique et le chemin d’accès le plus court commençant d’Alice à toutes ces personnes. L’exemple vérifie explicitement les « boucles » où le nœud de début et le nœud de fin 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