SHORTEST_PATH (Transact-SQL)

Artykuł
03/05/2025

Dotyczy: SQL Server 2019 (15.x) i nowsze wersje Azure SQL Database Azure SQL Managed Instance SQL Database w usłudze Microsoft Fabric

Określa warunek wyszukiwania grafu, który jest wyszukiwany rekursywnie lub powtarzalnie. SHORTEST_PATH można używać wewnątrz funkcji MATCH z węzłami grafu i tabelami krawędzi w instrukcji SELECT.

Transact-SQL konwencje składni

Najkrótsza ścieżka

Funkcja SHORTEST_PATH umożliwia znalezienie następujących elementów:

Najkrótsza ścieżka między dwoma podanymi węzłami/jednostkami
Najkrótsze ścieżki pojedynczego źródła.
Najkrótsza ścieżka z wielu węzłów źródłowych do wielu węzłów docelowych.

Przyjmuje on dowolny wzorzec długości jako dane wejściowe i zwraca najkrótszą ścieżkę, która istnieje między dwoma węzłami. Tej funkcji można używać tylko wewnątrz funkcji MATCH. Funkcja zwraca tylko jedną najkrótszą ścieżkę między dowolnymi dwoma podanymi węzłami. Jeśli istnieje, dwie lub więcej najkrótszych ścieżek o tej samej długości między dowolną parą węzłów źródłowych i docelowych, funkcja zwraca tylko jedną ścieżkę, która została znaleziona jako pierwsza podczas przechodzenia. Dowolny wzorzec długości można określić tylko wewnątrz funkcji SHORTEST_PATH.

Aby uzyskać pełną składnię, zapoznaj się z MATCH (SQL Graph).

DLA ŚCIEŻKI

PARAMETR PATH musi być używany z dowolną nazwą węzła lub tabeli krawędzi w klauzuli FROM, która uczestniczy w dowolnym wzorzec długości. W obszarze PATH informuje aparat, że węzeł lub tabela krawędzi zwraca uporządkowaną kolekcję reprezentującą listę węzłów lub krawędzi znalezionych wzdłuż ścieżki przechodzącej. Atrybuty z tych tabel nie mogą być projektowane bezpośrednio w klauzuli SELECT. Aby można było projektować atrybuty z tych tabel, należy użyć funkcji agregacji ścieżki grafu.

Dowolny wzorzec długości

Ten wzorzec zawiera węzły i krawędzie, które muszą być wielokrotnie przechodzine do jednego z następujących elementów:

Żądany węzeł jest osiągany.
Maksymalna liczba iteracji określonych w wzorcu jest spełniona.

Obsługiwane są następujące dwa kwantyfikatory wzorca:

"+": powtórz wzorzec 1 lub więcej razy. Po znalezieniu najkrótszej ścieżki zakończ działanie.
{1,n}: powtórz wzorzec 1, aby n razy. Zakończ natychmiast po znalezieniu najkrótszego.

LAST_NODE

funkcja LAST_NODE() umożliwia łączenie łańcuchów dwóch dowolnych wzorców przechodzenia długości. Można go używać w scenariuszach, w których:

W zapytaniu jest używanych więcej niż jeden najkrótszy wzorzec ścieżki, a jeden wzorzec rozpoczyna się od ostatniego węzła poprzedniego wzorca.
Dwa najkrótsze wzorce ścieżek scalają się w tym samym LAST_NODE().

Kolejność ścieżki grafu

Kolejność ścieżki grafu odnosi się do kolejności danych w ścieżce wyjściowej. Kolejność ścieżki wyjściowej zawsze zaczyna się od nierekursywnej części wzorca, po której następują węzły/krawędzie, które pojawiają się w części cyklicznego. Kolejność przechodzenia grafu podczas optymalizacji/wykonywania zapytania nie ma nic wspólnego z kolejnością wydrukowaną w danych wyjściowych. Podobnie kierunek strzałki we wzorcu rekursywnym również nie ma wpływu na kolejność ścieżki grafu.

Funkcje agregacji ścieżki grafu

Ponieważ węzły i krawędzie zaangażowane w dowolny wzorzec długości zwracają kolekcję (węzły i krawędzie przechodzące w tej ścieżce), użytkownicy nie mogą projektować atrybutów bezpośrednio przy użyciu konwencjonalnej składni tablename.attributename. W przypadku zapytań, w których wymagane jest projekcja wartości atrybutów z pośredniego węzła lub tabel krawędzi, w ścieżce przechodzenia użyj następujących funkcji agregacji ścieżki grafu: STRING_AGG, LAST_VALUE, SUM, AVG, MIN, MAX i COUNT. Ogólna składnia do używania tych funkcji agregujących w klauzuli SELECT to:

<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

Funkcja STRING_AGG przyjmuje wyrażenie i separator jako dane wejściowe i zwraca ciąg. Użytkownicy mogą używać tej funkcji w klauzuli SELECT do atrybutów projektu z węzłów pośrednich lub krawędzi w ścieżce przechodzącej.

LAST_VALUE

Aby projektować atrybuty z ostatniego węzła ścieżki przechodzącej, można użyć LAST_VALUE funkcji agregującej. Jest to błąd podczas udostępniania aliasu tabeli krawędzi jako danych wejściowych tej funkcji, można użyć tylko nazw tabel węzłów lub aliasów.

ostatniego węzła: ostatni węzeł odwołuje się do węzła, który pojawia się ostatnio w ścieżce przechodzącej, niezależnie od kierunku strzałki w predykacie MATCH. Na przykład: MATCH(SHORTEST_PATH(n(-(e)->p)+) ). W tym miejscu ostatni węzeł w ścieżce to ostatni odwiedzony węzeł P.

We wzorcu MATCH(SHORTEST_PATH((n<-(e)-)+p)) ostatnim węzłem jest ostatni odwiedzony węzeł N.

SUMA

Ta funkcja zwraca sumę podanych wartości atrybutów węzła/krawędzi lub wyrażenia, które pojawiły się w ścieżce przechodzenia.

HRABIA

Ta funkcja zwraca liczbę wartości innych niż null określonego atrybutu węzła/krawędzi w ścieżce. Funkcja COUNT nie obsługuje operatora * — podjęto próbę użycia * powoduje błąd składniowy.

{  COUNT( <expression> )  <order_clause>  }

AVG

Zwraca średnią podanych wartości atrybutów węzła/krawędzi lub wyrażenia, które pojawiły się w ścieżce przechodzenia.

MIN

Zwraca wartość minimalną z podanych wartości atrybutów węzła/krawędzi lub wyrażenia, które zostały wyświetlone w ścieżce przechodzenia.

MAX

Zwraca wartość maksymalną z podanych wartości atrybutów węzła/krawędzi lub wyrażenia, które zostały wyświetlone w ścieżce przechodzenia.

Uwagi

Funkcja SHORTEST_PATH może być używana tylko wewnątrz funkcji MATCH.
Funkcja LAST_NODE jest obsługiwana tylko w SHORTEST_PATH.
Funkcja SHORTEST_PATH zwraca dowolną najkrótszą ścieżkę między węzłami. Obecnie nie obsługuje zwracania wszystkich najkrótszych ścieżek między węzłami; Nie obsługuje również zwracania wszystkich ścieżek między węzłami.
Implementacja SHORTEST_PATH znajduje najkrótszą ścieżkę.
W niektórych przypadkach złe plany mogą być generowane dla zapytań z większą liczbą przeskoków, co powoduje wyższe czasy wykonywania zapytań. Oceń, czy wskazówki dotyczące zapytań, takie jak OPTION (HASH JOIN) i /lub OPTION (MAXDOP 1) — pomoc.

Przykłady

W przykładowych zapytaniach przedstawionych tutaj użyjemy tabel węzłów i krawędzi utworzonych w przykładzie SQL Graph

A. Znajdź najkrótszą ścieżkę między dwiema osobami

W poniższym przykładzie znajdujemy najkrótszą ścieżkę między Jacobem a Alicją. Potrzebujemy węzła Person i krawędzi friendOf utworzonej na podstawie przykładu 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. Znajdź najkrótszą ścieżkę z danego węzła do wszystkich innych węzłów na grafie.

W poniższym przykładzie znajdują się wszystkie osoby, z którymi Jacob jest połączony na wykresie, a najkrótsza ścieżka zaczyna się od Jacoba do wszystkich tych ludzi.

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. Zlicz liczbę przeskoków/poziomów przechodzących od jednej osoby do innej na wykresie.

Poniższy przykład znajduje najkrótszą ścieżkę między Jacobem a Alice i drukuje liczbę przeskoków potrzebnych do przejścia od Jacoba do Alicji.

 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. Znajdź osoby 1-3 przeskoki od danej osoby

Poniższy przykład znajduje najkrótszą ścieżkę między Jacobem a wszystkimi ludźmi, z którymi Jacob jest połączony w grafie jeden do trzech przeskoków od niego.

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. Znajdź osoby dokładnie dwa przeskoki od danej osoby

Poniższy przykład znajduje najkrótszą ścieżkę między Jacobem a osobami, które są dokładnie dwoma przeskokami od niego na wykresie.

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. Znajdź osoby 1-3 przeskoki od danej osoby, która również lubi określoną restaurację

Poniższy przykład znajduje najkrótszą ścieżkę między Jacobem a wszystkimi osobami, z którymi jest połączony w grafie 1-3 przeskoków od niego. Zapytanie filtruje również połączone osoby, lubi daną restaurację. W poniższym przykładzie LAST_NODE(Person2) zwraca ostatni węzeł dla każdej najkrótszej ścieżki. "Ostatni" węzeł Person uzyskany z LAST_NODE można następnie "połączyć łańcuch" w celu dalszego przechodzenia, aby znaleźć restauracje, które lubią.

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. Znajdź najkrótszą ścieżkę z danego węzła do wszystkich innych węzłów na grafie, z wyłączeniem "pętli"

Poniższy przykład znajduje wszystkie osoby, z którymi Alicja jest połączona na wykresie, oraz najkrótszą ścieżkę rozpoczynającą się od Alice do wszystkich tych osób. W przykładzie jawnie sprawdza się pętle "pętle", w których początek i końcowy węzeł ścieżki są takie same.

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'

Udostępnij za pośrednictwem