SHORTEST_PATH (Transact-SQL)

Artikel
06/29/2023

Gilt für: SQL Server 2019 (15.x) und höher Azure SQL Datenbank Azure SQL Managed Instance

Gibt eine Suchbedingung für ein Diagramm an, das rekursiv oder wiederholt durchsucht wird. SHORTEST_PATH können in MATCH mit Graphknoten und Edgetabellen in der SELECT-Anweisung verwendet werden.

Transact-SQL-Syntaxkonventionen

Kürzester Pfad

Mit der SHORTEST_PATH-Funktion können Sie Folgendes finden:

Ein kürzester Pfad zwischen zwei Knoten/Entitäten
Die kürzesten Pfade einer einzelnen Quelle.
Kürzester Pfad von mehreren Quellknoten zu mehreren Zielknoten.

Es verwendet ein Muster mit beliebiger Länge als Eingabe und gibt einen kürzesten Pfad zurück, der zwischen zwei Knoten vorhanden ist. Diese Funktion kann nur innerhalb von MATCH verwendet werden. Die Funktion gibt nur einen kürzesten Pfad zwischen zwei beliebigen Knoten zurück. Wenn zwei oder mehr kurze Pfade der gleichen Länge zwischen einem beliebigen Quell- und Zielknotenpaar vorhanden sind, gibt die Funktion nur einen Pfad zurück, der zuerst während des Durchlaufs gefunden wurde. Ein Beliebiges Längenmuster kann nur innerhalb einer SHORTEST_PATH-Funktion angegeben werden.

Eine vollständige Syntax finden Sie unter MATCH (SQL Graph).

FOR PATH

FOR PATH muss mit jedem Knoten- oder Edgetabellennamen in der FROM-Klausel verwendet werden, die an einem Muster mit beliebiger Länge beteiligt ist. FOR PATH teilt der Engine mit, dass der Knoten oder die Edgetabelle eine geordnete Auflistung zurückgibt, die die Liste der Knoten oder Kanten darstellt, die sich entlang des durchlaufenen Pfads befinden. Die Attribute aus diesen Tabellen können nicht direkt in der SELECT-Klausel projiziert werden. Um Attribute aus diesen Tabellen zu projizieren, müssen Graphpfadaggregatfunktionen verwendet werden.

Muster für beliebige Längen

Dieses Muster umfasst die Knoten und Kanten, die wiederholt durchlaufen werden müssen, bis:

Der gewünschte Knoten wird erreicht.
Die maximale Anzahl von Iterationen, wie im Muster angegeben, ist erfüllt.

Die folgenden beiden Muster quantifizierer werden unterstützt:

'+': Wiederholen Sie das Muster mindestens 1 Mal. Beenden, sobald der kürzeste Pfad gefunden wird.
{1,n} : Das Muster 1 bis n Male wiederholen. Beenden Sie, sobald eine kürzeste gefunden wurde.

LAST_NODE

LAST_NODE()-Funktion ermöglicht das Verketten von zwei beliebigen Längendurchlaufmustern. Sie kann in Folgenden Szenarien verwendet werden:

In einer Abfrage werden mehr als ein kürzestes Pfadmuster verwendet, und ein Muster beginnt auf dem LETZTEN Knoten des vorherigen Musters.
Zwei kürzeste Pfadmuster werden auf demselben LAST_NODE() zusammengeführt.

Reihenfolge des Diagrammpfads

Die Reihenfolge des Graphpfads bezieht sich auf die Reihenfolge der Daten im Ausgabepfad. Die Reihenfolge des Ausgabepfads beginnt immer am nicht mehrcursiven Teil des Musters, gefolgt von den Knoten/Kanten, die im rekursiven Teil angezeigt werden. Die Reihenfolge, in der das Diagramm während der Abfrageoptimierung/-ausführung durchlaufen wird, hat nichts mit der Reihenfolge zu tun, die in der Ausgabe gedruckt wird. Ebenso wirkt sich die Richtung des Pfeils im rekursiven Muster nicht auf die Reihenfolge des Diagrammpfads aus.

Graphpfad-Aggregatfunktionen

Da die Knoten und Kanten, die am Muster mit beliebiger Länge beteiligt sind, eine Sammlung (von Knoten und Edges) zurückgeben, die in diesem Pfad durchlaufen werden, können Benutzer die Attribute nicht direkt mit der herkömmlichen Syntax tablename.attributename projizieren. Für Abfragen, bei denen Attributwerte aus den Zwischenknoten oder Edgetabellen projiziert werden müssen, verwenden Sie im durchlaufenen Pfad die folgenden Graphpfadaggregatfunktionen: STRING_AGG, LAST_VALUE, SUM, AVG, MIN, MAX und COUNT. Die allgemeine Syntax für die Verwendung dieser Aggregatfunktionen in der SELECT-Klausel lautet:

<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

Die STRING_AGG-Funktion nimmt einen Ausdruck und ein Trennzeichen als Eingabe an und gibt eine Zeichenfolge zurück. Benutzer können diese Funktion in der SELECT-Klausel verwenden, um Attribute von den Zwischenknoten oder Kanten im durchlaufenen Pfad zu projizieren.

LAST_VALUE

Zum Projektieren von Attributen aus dem letzten Knoten des durchquerten Pfads kann LAST_VALUE Aggregatfunktion verwendet werden. Es ist ein Fehler, Edgetabellenalias als Eingabe für diese Funktion bereitzustellen. Es können nur Knotentabellennamen oder Aliase verwendet werden.

Letzter Knoten: Der letzte Knoten bezieht sich auf den Knoten, der zuletzt im durchlaufenen Pfad angezeigt wird, unabhängig von der Pfeilrichtung im MATCH-Prädikat. Beispiel: MATCH(SHORTEST_PATH(n(-(e)->p)+) ). Hier ist der letzte Knoten im Pfad der zuletzt besuchte P-Knoten.

MATCH(SHORTEST_PATH((n<-(e)-)+p)) Im Muster ist der letzte Knoten der letzte besuchte N-Knoten.

SUM

Diese Funktion gibt die Summe der angegebenen Knoten-/Edge-Attributwerte oder -ausdrücke zurück, die im durchlaufenen Pfad angezeigt wurden.

COUNT

Diese Funktion gibt die Anzahl von Nicht-NULL-Werten des angegebenen Knoten-/Edge-Attributs im Pfad zurück. Die COUNT-Funktion unterstützt den * Operator nicht . Die versuchte Verwendung von * Ergebnissen zu einem Syntaxfehler.

{  COUNT( <expression> )  <order_clause>  }

DURCHSCHN.

Gibt den Durchschnitt der angegebenen Knoten-/Edge-Attributwerte oder -ausdrücke zurück, die im durchlaufenen Pfad angezeigt wurden.

MIN

Gibt den Mindestwert aus den angegebenen Knoten-/Edge-Attributwerten oder -ausdrücken zurück, die im durchlaufenen Pfad angezeigt wurden.

MAX

Gibt den maximalen Wert aus den angegebenen Knoten-/Edge-Attributwerten oder -Ausdrücken zurück, die im durchlaufenen Pfad angezeigt wurden.

Bemerkungen

Die SHORTEST_PATH-Funktion kann nur in MATCH verwendet werden.
Die LAST_NODE-Funktion wird nur in SHORTEST_PATH unterstützt.
Die SHORTEST_PATH-Funktion gibt einen beliebigen kürzesten Pfad zwischen Knoten zurück. Derzeit wird die Rückgabe aller kürzesten Pfade zwischen Knoten nicht unterstützt. Außerdem wird nicht unterstützt, alle Pfade zwischen Knoten zurückzugeben.
Die SHORTEST_PATH Implementierung findet einen ungewichteten kürzesten Pfad.
In einigen Fällen können schlechte Pläne für Abfragen mit einer höheren Anzahl von Hops generiert werden, was zu höheren Abfrageausführungszeiten führt. Bewerten Sie, ob Abfragehinweise wie OPTION (HASH JOIN) und/oder OPTION (MAXDOP 1) helfen.

Beispiele

Für die hier gezeigten Beispielabfragen verwenden wir die Knoten- und Edgetabellen, die im SQL Graph-Beispiel erstellt wurden.

A. Finden Sie den kürzesten Weg zwischen zwei Personen

Im folgenden Beispiel finden wir den kürzesten Weg zwischen Jacob und Alice. Wir benötigen den Knoten und friendOf edge, der Person aus SQL Graph-Beispiel erstellt wurde.

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. Suchen Sie den kürzesten Pfad von einem bestimmten Knoten zu allen anderen Knoten im Diagramm.

Im folgenden Beispiel finden Sie alle Menschen, mit denen Jakob verbunden ist, im Graphen und den kürzesten Weg, der von Jakob zu all diesen Menschen beginnt.

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. Zählen Sie im Diagramm die Anzahl der Hops/Ebenen, die durchlaufen werden, um von einer Person zur anderen zu wechseln.

Im folgenden Beispiel wird der kürzeste Pfad zwischen Jacob und Alice gefunden und die Anzahl der Hops gedruckt, die benötigt werden, um von Jacob nach Alice zu gelangen.

 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: Finden Sie Personen, die 1-3 Hops von einer bestimmten Person entfernt sind

Das folgende Beispiel findet den kürzesten Weg zwischen Jakob und allen Menschen, mit denen Jakob verbunden ist, im Graphen, der ein bis drei Hops von ihm entfernt ist.

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. Personen finden, die genau zwei Hops von einer bestimmten Person entfernt sind

Das folgende Beispiel findet den kürzesten Weg zwischen Jacob und Menschen, die genau zwei Hops von ihm entfernt sind, im Diagramm.

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. Finden Sie Menschen, die 1-3 Hops von einer bestimmten Person entfernt sind, die auch ein bestimmtes Restaurant mögen

Das folgende Beispiel findet den kürzesten Weg zwischen Jacob und allen Menschen, mit denen er verbunden ist, in der Graphen 1-3 Hops von ihm entfernt. Die Abfrage filtert auch verbundene Personen nach ihren Vorlieben für ein bestimmtes Restaurant. Im folgenden Beispiel LAST_NODE(Person2) wird der endgültige Knoten für jeden kürzesten Pfad zurückgegeben. Der "letzte" Person Knoten, der von LAST_NODE abgerufen wird, kann dann für weitere Durchgänge "verkettet" werden, um die Restaurants zu finden, die ihnen gefallen.

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. Suchen Sie den kürzesten Pfad von einem bestimmten Knoten zu allen anderen Knoten im Diagramm, mit Ausnahme von "Schleifen"

Im folgenden Beispiel werden alle Personen ermittelt, mit denen Alice im Diagramm verbunden ist, und den kürzesten Weg von Alice zu all diesen Personen. Im Beispiel wird explizit nach "Schleifen" überprüft, bei denen start und end node des Pfads identisch sind.

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'