SHORTEST_PATH (Transact-SQL)

Статья
08/21/2023

Область применения: SQL Server 2019 (15.x) и более поздних версий Управляемого экземпляра Базы данных SQL Azure SQL Azure

Указывает условие поиска графа, которое выполняется рекурсивно или повторяющееся. SHORTEST_PATH можно использовать внутри MATCH с узлом графа и пограничными таблицами в инструкции SELECT.

Соглашения о синтаксисе Transact-SQL

Кратчайший путь

Функция SHORTEST_PATH позволяет найти следующее:

Кратчайший путь между двумя заданными узлами и сущностями
Один исходный кратчайший путь.
Кратчайший путь от нескольких исходных узлов к нескольким целевым узлам.

Он принимает произвольный шаблон длины в качестве входных данных и возвращает кратчайший путь, который существует между двумя узлами. Эта функция может использоваться только внутри MATCH. Функция возвращает только один кратчайший путь между двумя заданными узлами. Если существуют два или более коротких пути одной длины между любой парой исходных и конечных узлов, функция возвращает только один путь, который был найден первым во время обхода. Произвольный шаблон длины можно указать только внутри функции SHORTEST_PATH.

Полный синтаксис см. в статье MATCH (SQL Graph).

ДЛЯ ПУТИ

FOR PATH должен использоваться с любым именем узла или пограничной таблицы в предложении FROM, который участвует в произвольном шаблоне длины. FOR PATH сообщает обработчику, что таблица узлов или ребер возвращает упорядоченную коллекцию, представляющую список узлов или ребер, найденных вдоль пути. Атрибуты из этих таблиц нельзя проецировать непосредственно в предложении SELECT. Чтобы проецировать атрибуты из этих таблиц, необходимо использовать агрегатные функции пути графа.

Произвольный шаблон длины

Этот шаблон включает узлы и края, которые должны проходить многократно, пока не будет:

Достигнут нужный узел.
Максимальное число итерации, указанное в шаблоне, выполняется.

Поддерживаются следующие два квантификатора шаблона:

'+': повторите шаблон 1 или более раз. Действие прекращается, как только будет найден кратчайший путь.
{1,n}: повторите шаблон от 1 до n раз. Завершите работу сразу после того, как будет найден самый короткий.

LAST_NODE

функция LAST_NODE() позволяет выполнять цепочку двух произвольных шаблонов обхода длины. Его можно использовать в сценариях, где:

Несколько кратчайших шаблонов пути используются в запросе, и один шаблон начинается с последнего узла предыдущего шаблона.
Два кратчайшие шаблоны пути объединяются в одну и ту же LAST_NODE().

Порядок пути графа

Порядок пути графа относится к порядку данных в выходном пути. Порядок выходного пути всегда начинается с нерекомендуемой части шаблона, за которой следуют узлы и края, которые отображаются в рекурсивной части. Порядок, в котором граф проходит во время оптимизации и выполнения запросов, не имеет ничего общего с порядком, напечатанным в выходных данных. Аналогичным образом направление стрелки в рекурсивном шаблоне также не влияет на порядок пути графа.

Агрегатные функции пути графа

Так как узлы и края, участвующие в произвольном шаблоне длины, возвращают коллекцию (из узлов и ребер), прошедших по этому пути, пользователи не могут проецирует атрибуты непосредственно с помощью стандартного синтаксиса tablename.attributename. Для запросов, в которых необходимо проецировать значения атрибутов из промежуточных узлов или пограничных таблиц, в пути, проверленных, используйте следующие статистические функции пути графа: STRING_AGG, LAST_VALUE, СУММ, AVG, MIN, MAX и COUNT. Общий синтаксис для использования этих агрегатных функций в предложении SELECT:

<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

Функция STRING_AGG принимает выражение и разделитель в качестве входных данных и возвращает строку. Пользователи могут использовать эту функцию в предложении SELECT для проекта атрибутов из промежуточных узлов или ребер пути, пройденного по пути.

LAST_VALUE

Чтобы проецировать атрибуты из последнего узла пути, пройденного, можно использовать LAST_VALUE агрегатную функцию. Это ошибка для предоставления псевдонима граничной таблицы в качестве входных данных для этой функции, можно использовать только имена таблиц узлов или псевдонимы.

Последний узел: последний узел ссылается на узел, который отображается последним в пути, пересекаемом независимо от направления стрелки в предикате MATCH. Например: MATCH(SHORTEST_PATH(n(-(e)->p)+) ). Здесь последний узел в пути является последним посещаемым узлом P.

В шаблоне MATCH(SHORTEST_PATH((n<-(e)-)+p)) последний узел является последним посещаемым N-узлом.

SUM

Эта функция возвращает сумму предоставленных значений атрибутов узла или пограничных атрибутов или выражений, которые появились в пути с обходом.

КОЛИЧЕСТВО

Эта функция возвращает количество непустых значений указанного атрибута узла или edge в пути. Функция COUNT не поддерживает * оператор — попытка использования * результатов в синтаксической ошибке.

{  COUNT( <expression> )  <order_clause>  }

СРЕДН.

Возвращает среднее значение предоставленных значений атрибутов узла или пограничных атрибутов или выражений, которые появились в пути с обходом.

MIN

Возвращает минимальное значение из предоставленных значений атрибутов узла или пограничных атрибутов или выражений, которые появились в обходном пути.

MAX

Возвращает максимальное значение из предоставленных значений атрибутов узла или edge, которые появились в пути.

Замечания

Функцию SHORTEST_PATH можно использовать только внутри MATCH.
Функция LAST_NODE поддерживается только в SHORTEST_PATH.
Функция SHORTEST_PATH возвращает любой самый короткий путь между узлами. В настоящее время он не поддерживает возврат всех кратчайшего пути между узлами; он также не поддерживает возврат всех путей между узлами.
Реализация SHORTEST_PATH находит несвешанный кратчайший путь.
В некоторых случаях плохие планы могут создаваться для запросов с большим количеством прыжков, что приводит к увеличению времени выполнения запроса. Оцените, могут ли подсказки запроса, такие как OPTION (HASH JOIN) и /или OPTION (MAXDOP 1).

Примеры

Примеры запросов, показанных здесь, используются таблицы узлов и пограничных вычислений, созданные в примере SQL Graph.

О. Поиск кратчайшего пути между двумя людьми

В следующем примере мы находим самый короткий путь между Джейкобом и Алисом. Нам нужен узел и friendOf ребра, созданные Person из примера 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. Найдите кратчайший путь от заданного узла ко всем остальным узлам в графе.

В следующем примере находятся все люди, к которым Джейкоб подключен в графе, и самый короткий путь, начиная с Джейкоба ко всем этим людям.

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. Подсчитывать количество прыжков или уровней, пройденных для перехода от одного человека к другому в графе.

Следующий пример находит самый короткий путь между Джейкобом и Алисом и печатает количество прыжков, которые он принимает, чтобы перейти от Джейкоба к Алисе.

 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. Найти людей 1-3 прыжки от заданного человека

Следующий пример находит самый короткий путь между Джейкобом и всеми людьми, к которым Джейкоб подключен в графе один к трем прыжкам от него.

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'

Д. Найти людей ровно два прыжка от заданного человека

В следующем примере показано, как найти самый короткий путь между Джейкобом и людьми, которые находятся ровно в двух прыжках от него в графе.

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

Е. Найти людей 1-3 прыжки от заданного человека, который также как конкретный ресторан

Следующий пример находит самый короткий путь между Джейкобом и всеми людьми, к которым он подключен в графе 1-3 прыжков от него. Запрос также фильтрует подключенных людей по своему вкусу заданному ресторану. В приведенном ниже примере возвращает LAST_NODE(Person2) конечный узел для каждого кратчайшего пути. Затем "последний" Person узел, полученный от LAST_NODE этого, может быть "цеплен" для дальнейшего обхода, чтобы найти рестораны, которые они любят.

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. Поиск кратчайшего пути от заданного узла ко всем остальным узлам в графе, за исключением "циклов"

В следующем примере все люди, к которым подключена Алиса в графе, и самый короткий путь, начиная с Алисы ко всем этим людям. В примере явным образом проверяется наличие циклов, в которых начальный и конечный узел пути совпадают.

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'