SHORTEST_PATH (Transact-SQL)

Gilt für:yes SQL Server 2019 (15.x) YesAzure SQL-Datenbank YesAzure SQL verwaltete Instanz

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

Topic link iconTransact-SQL-Syntaxkonventionen

Kürzester Pfad

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

  • Ein kürzester Pfad zwischen zwei angegebenen Knoten/Entitäten
  • Kürzester Pfad(n) einer einzelnen Quelle.
  • Kürzester Pfad von mehreren Quellknoten zu mehreren Zielknoten.

Es nimmt ein beliebiges Längenmuster als Eingabe an 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 angegebenen Knoten zurück. Wenn es zwei oder mehr kürzeste Pfade derselben Länge zwischen einem quell- und zielknotenpaar gibt, gibt die Funktion nur einen Pfad zurück, der zuerst während des Durchlaufs gefunden wurde. Beachten Sie, dass ein beliebiges Längenmuster nur innerhalb einer SHORTEST_PATH Funktion angegeben werden kann.

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 beliebigen Längenmuster beteiligt ist. FOR PATH teilt der Engine mit, dass der Knoten oder die Edgetabelle 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 Graphpfad-Aggregatfunktionen verwendet werden.

Beliebiges Längenmuster

Dieses Muster schließt die Knoten und Kanten ein, die wiederholt durchlaufen werden müssen, bis der gewünschte Knoten erreicht ist oder bis die maximale Anzahl von Iterationen, wie im Muster angegeben, erreicht ist. Jedes Mal, wenn die Abfrage ausgeführt wird, ist das Ergebnis der Ausführung dieses Musters eine geordnete Auflistung der Knoten und Kanten, die entlang des Pfads vom Startknoten zum Endknoten durchlaufen werden. Dies ist ein Syntaxmuster für reguläre Ausdrücke, und die folgenden beiden Musterquantifizierer 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. Wird beendet, sobald eine kürzeste gefunden wird.

LAST_NODE

LAST_NODE()-Funktion ermöglicht das Verketten von zwei Durchlaufmustern beliebiger Länge. Sie kann in Szenarien verwendet werden, in denen:

  • In einer Abfrage werden mehr als ein kürzestes Pfadmuster verwendet, und ein Muster beginnt am Knoten LAST des vorherigen Musters.
  • Zwei kürzeste Pfadmuster werden am gleichen LAST_NODE() zusammengeführt.

Graph Pfadreihenfolge

Graph Pfadreihenfolge bezieht sich auf die Reihenfolge der Daten im Ausgabepfad. Die Reihenfolge der Ausgabepfade 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 in der Ausgabe ausgegebenen Reihenfolge zu tun. Ebenso wirkt sich die Richtung des Pfeils im rekursiven Muster auch nicht auf die Reihenfolge des Diagrammpfads aus.

Graph Path-Aggregatfunktionen

Da die Knoten und Kanten, die an einem beliebigen Längenmuster beteiligt sind, eine Auflistung (von Knoten und Kanten, die in diesem Pfad durchlaufen werden) zurückgeben, können Benutzer die Attribute nicht direkt mithilfe der herkömmlichen Syntax tablename.attributename pro projektieren. Verwenden Sie für Abfragen, bei denen Attributwerte aus den Zwischenknoten- oder Edgetabellen projiziert werden müssen, 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 verwendet einen Ausdruck und ein Trennzeichen als Eingabe und gibt eine Zeichenfolge zurück. Benutzer können diese Funktion in der SELECT-Klausel verwenden, um Attribute von den Zwischenknoten oder Rändern im durchlaufenen Pfad zu projizierten.

LAST_VALUE

Um Attribute aus dem letzten Knoten des durchlaufenen Pfads zu projektieren, kann LAST_VALUE Aggregatfunktion verwendet werden. Es ist ein Fehler, edge table alias 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 im durchlaufenen Pfad zuletzt angezeigt 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 zuletzt besuchte P-Knoten.

Der letzte Knoten ist hingegen der letzte N-ten Knoten im Ausgabediagrammpfad für dieses Muster: MATCH(SHORTEST_PATH((n<-(e)-)+p))

SUM

Diese Funktion gibt die Summe der bereitgestellten Knoten-/Edgeattributwerte oder des Ausdrucks zurück, die im durchlaufenen Pfad angezeigt wurden.

COUNT

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

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

DURCHSCHN.

Gibt den Durchschnitt der bereitgestellten Knoten-/Edgeattributwerte oder des Ausdrucks zurück, die im durchlaufenen Pfad angezeigt wurden.

MIN

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

MAX

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

Bemerkungen

  • 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 beliebigen kürzesten Pfad zwischen Knoten zurück. Derzeit wird die Rückgabe aller kürzesten Pfade zwischen Knoten nicht unterstützt. es unterstützt auch nicht das Zurückgeben aller Pfade zwischen Knoten.
  • Die SHORTEST_PATH Implementierung findet einen ungewichteten kürzesten Pfad.
  • In einigen Fällen können fehlerhafte Pläne für Abfragen mit einer höheren Anzahl von Hops generiert werden, was zu höheren Abfrageausführungszeiten führt. Werten Sie aus, ob Abfragehinweise wie OPTION (HASH JOIN) und/oder OPTION (MAXDOP 1) helfen.

Beispiele

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

A. Ermitteln des kürzesten Pfads zwischen zwei Personen

Im folgenden Beispiel finden wir den kürzesten Pfad zwischen Einem und Alice. Wir benötigen den Knoten Person und friendOf edge, die aus dem Graph-Beispielskript erstellt wurden.

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 angegebenen Knoten zu allen anderen Knoten im Diagramm.

Im folgenden Beispiel werden alle Personen gefunden, mit denen Im Graphen Eine Verbindung besteht, und der kürzeste Weg, der von Einer zu all diesen Personen 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 die Anzahl der hops/levels, die durchlaufen werden, um von einer Person zur anderen im Diagramm zu wechseln.

Im folgenden Beispiel wird der kürzeste Pfad zwischen Einem und Alice ermittelt, und es wird die Anzahl der Hops gedruckt, die benötigt werden, um von Einem zu 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: Suchen von Personen zwischen 1 und 3 Hops von einer bestimmten Person entfernt

Im folgenden Beispiel wird der kürzeste Pfad zwischen Einem und allen Personen gefunden, mit denen er im Diagramm 1 bis 3 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. Suchen von Personen, die genau zwei Hops von einer bestimmten Person entfernt sind

Im folgenden Beispiel wird der kürzeste Pfad zwischen Einem und Personen gefunden, die genau zwei 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 von Personen zwischen 1 und 3 Hops von einer bestimmten Person entfernt, die auch ein bestimmtes Restaurant mag

Im folgenden Beispiel wird der kürzeste Pfad zwischen Einem und allen Personen gefunden, mit denen er im Diagramm 1 bis 3 Hops von ihm entfernt ist. und filtert auch nur die verbundenen Personen nach ihren Wünschen nach einem bestimmten Restaurant. Beachten Sie im folgenden Beispiel, dass LAST_NODE(Person2) den letzten Knoten für jeden kürzesten Pfaddurchlauf zurückgibt, sodass der Knoten Person für weitere Durchgänge "verkettet" werden kann, um die restaurant(s) 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 angegebenen Knoten zu allen anderen Knoten im Diagramm, mit Ausnahme von "Schleifen".

Im folgenden Beispiel werden alle Personen gefunden, mit denen Der Graf verbunden ist, und den kürzesten Pfad von Alice zu all diesen Personen. Im Beispiel wird explizit nach "Schleifen" überprüft, bei denen 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)] Graph verarbeitung mit SQL Server 2017