SHORTEST_PATH (Transact-SQL)

Gilt für: SQL Server 2019 (15.x) 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 Randtabellen in der SELECT-Anweisung verwendet werden.

ThemenlinksymbolTransact-SQL-Syntaxkonventionen

Kürzester Pfad

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

  • Ein kürzester Pfad zwischen zwei bestimmten Knoten/Entitäten
  • Einzelne Quelle kurzste Pfade(n).
  • Kürzester Pfad von mehreren Quellknoten zu mehreren Zielknoten.

Es dauert ein beliebiges Längenmuster als Eingabe und gibt einen kurzen Pfad zurück, der zwischen zwei Knoten vorhanden ist. Diese Funktion kann nur innerhalb von MATCH verwendet werden. Die Funktion gibt nur einen kurzen Pfad zwischen zwei bestimmten Knoten zurück. Wenn es zwei oder mehr kurze Pfade der gleichen Länge zwischen allen Quell- und Zielknoten gibt, gibt die Funktion nur einen Pfad zurück, der beim Durchlaufen zuerst gefunden wurde. Beachten Sie, dass ein beliebiges Längenmuster nur innerhalb einer SHORTEST_PATH-Funktion angegeben werden kann.

Verweisen Sie auf das MATCH (SQL Graph) für die Syntax.

FÜR PFAD

FOR PATH muss mit jedem Knoten- oder Edgetabellennamen in der FROM-Klausel verwendet werden, der an einem beliebigen Längenmuster teilnimmt. FOR PATH teilt dem Modul mit, dass die Knoten- oder Randtabelle eine sortierte Auflistung zurückgibt, die die Liste der Knoten oder Kanten darstellt, die entlang des durchlaufenen Pfads gefunden wurden. Die Attribute aus diesen Tabellen können nicht direkt in der SELECT-Klausel projiziert werden. Um Attribute aus diesen Tabellen zu projektieren, müssen Diagrammpfadaggregatfunktionen verwendet werden.

Beliebiges Längenmuster

Dieses Muster enthält die Knoten und Kanten, die wiederholt durchlaufen werden müssen, bis der gewünschte Knoten erreicht wird oder bis die maximale Anzahl von Iterationen wie im Muster angegeben ist. Jedes Mal, wenn die Abfrage ausgeführt wird, ist das Ergebnis der Ausführung dieses Musters eine sortierte Auflistung der Knoten und Kanten, die entlang des Pfads vom Startknoten bis zum Endknoten durchlaufen werden. Dies ist ein Syntaxmuster für reguläre Ausdrücke und die folgenden beiden Muster-Quantifizierer werden unterstützt:

  • '+': Wiederholen Sie das Muster 1 oder mehr Mal. Beenden, sobald der kürzeste Pfad gefunden wird.
  • {1,n} : Das Muster 1 bis „n“ Male wiederholen. Beenden Sie, sobald ein kürzester gefunden wird.

LAST_NODE

LAST_NODE()-Funktion ermöglicht die Verketteung von zwei beliebigen Längenverläufen. Es kann in Szenarien verwendet werden, in denen:

  • Mehrere kurze Pfadmuster werden in einer Abfrage verwendet, und ein Muster beginnt am LETZTEN Knoten des vorherigen Musters.
  • Zwei kurze Pfadmuster werden gleichzeitig LAST_NODE() zusammenführen.

Graphpfadreihenfolge

Die Diagrammpfadreihenfolge bezieht sich auf die Reihenfolge der Daten im Ausgabepfad. Die Ausgabepfadreihenfolge beginnt immer am nicht rekursiven 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 auch nicht auf die Diagrammpfadreihenfolge aus.

Graph-Pfadaggregatfunktionen

Da die Knoten und Kanten, die in beliebigem Längenmuster beteiligt sind, eine Auflistung (von Knoten(n) und Edges zurückgibt, die in diesem Pfad durchlaufen werden), können Benutzer die Attribute nicht direkt mit der herkömmlichen Syntax "tablename.attributname" projizieren. Verwenden Sie für Abfragen, in denen Attributwerte aus den Zwischenknoten- oder Randtabellen in den durchlaufenen Pfaden projektiert werden müssen, die folgenden Diagrammpfadaggregatfunktionen: STRING_AGG, LAST_VALUE, SUMME, 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 verwendet einen Ausdruck und Trennzeichen als Eingabe und gibt eine Zeichenfolge zurück. Benutzer können diese Funktion in der SELECT-Klausel verwenden, um Attribute aus den Zwischenknoten oder Kanten im durchlaufenen Pfad zu projektieren.

LAST_VALUE

Um Attribute aus dem letzten Knoten des durchlaufenen Pfads zu projektieren, kann LAST_VALUE Aggregatfunktion verwendet werden. Es ist ein Fehler, edgetabellen alias als Eingabe für diese Funktion bereitzustellen, nur Knotentabellennamen oder Aliase können verwendet werden.

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

In der Erwägung, dass der letzte Knoten der letzte Nth-Knoten im Ausgabediagrammpfad für dieses Muster ist: MATCH(SHORTEST_PATH((n<-(e)-)+p))

SUM

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

COUNT

Diese Funktion gibt die Anzahl der Nicht-Null-Werte des gewünschten Knoten-/Edge-Attributs im Pfad zurück. Die Funktion COUNT unterstützt den Operator '*' mit einem Knoten- oder Edgetabellen-Alias. Ohne den Knoten- oder Randtabellen-Alias ist die Verwendung von * mehrdeutig und führt zu einem Fehler.

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

DURCHSCHN.

Gibt den Mittelwert der bereitgestellten Knoten-/Edge-Attributwerte oder des Ausdrucks zurück, der im durchlaufenen Pfad angezeigt wurde.

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.

Hinweise

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

Beispiele

Für die hier gezeigten Beispielabfragen nutzen wir die in SQL Graph erstellten Knoten- und Edgetabellen.

A. Finden Sie kürzesten Pfad zwischen 2 Personen

Im folgenden Beispiel finden wir kürzesten Pfad zwischen Jacob und Alice. Wir benötigen den Knoten "Person" und "FriendOf", der aus dem Diagrammbeispielskript 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 einen kurzen Pfad von einem bestimmten Knoten zu allen anderen Knoten im Diagramm.

Im folgenden Beispiel werden alle Menschen gefunden, mit denen Jacob in der Grafik verbunden ist, und der kürzeste Weg ab Jacob zu allen diesen Menschen.

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 die Anzahl von Hops/Levels, die von einer Person zu einer anderen in das Diagramm wechseln.

Das folgende Beispiel findet den kürzesten Pfad zwischen Jacob und Alice und druckt die Anzahl der Hops, die es benötigt, um von Jacob zu Alice zu wechseln.

 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: Suchen von Personen 1-3 Hops von einer bestimmten Person entfernt

Das folgende Beispiel findet den kürzesten Weg zwischen Jacob und allen Menschen, mit denen er in der Grafik verbunden ist, 1-3 Hops weg von ihm.

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. Suchen Sie genau 2 Hops von einer bestimmten Person entfernt

Im folgenden Beispiel wird der kürzeste Weg zwischen Jacob und Menschen gefunden, die genau 2 Hops von ihm im Diagramm entfernt sind.

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. Suchen Sie Personen 1-3 Hops von einer bestimmten Person entfernt, die auch ein bestimmtes Restaurant mag

Im folgenden Beispiel wird der kürzeste Weg zwischen Jacob und allen Menschen gefunden, die er in der Grafik 1-3 von ihm entfernt ist; und filtert auch nur diejenigen, die verbunden sind, indem sie ihren Geschmack für ein bestimmtes Restaurant haben. Beachten Sie im folgenden Beispiel, dass LAST_NODE(Person2) den endgültigen Knoten für jeden kürzesten Pfad traversal zurückgibt, wodurch dieser Person-Knoten für weitere Durchgänge "verkettet" werden kann, um das Restaurant(n) zu finden, das sie mögen.

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, ohne "Schleifen".

Im folgenden Beispiel werden alle Menschen gefunden, mit denen Jacob in der Grafik verbunden ist und der kürzeste Weg ab Alice zu allen diesen Menschen beginnt. Im Beispiel wird explizit nach "Schleifen" überprüft, wo der Start- und der Endknoten 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'

Weitere Informationen

MATCH (SQL Graph)CREATE TABLE (SQL Graph)INSERT (SQL Graph)] Graphverarbeitung mit SQL Server 2017