Compartilhar via

SHORTEST_PATH (Transact-SQL)

  • Artigo

Aplica-se a: SQL Server 2019 (15.x) e posterior SQL do Azure Banco de DadosInstância Gerenciada de SQL do Azure

Especifica uma condição de pesquisa para um grafo, que é pesquisado recursivamente ou repetitivamente. SHORTEST_PATH pode ser usado dentro de MATCH com tabelas de borda e nó de grafo, na instrução SELECT.

Convenções de sintaxe de Transact-SQL

Caminho mais curto

A função SHORTEST_PATH permite que você encontre:

  • Um caminho mais curto entre dois nós/entidades determinados
  • Caminho(s) mais curto(s) de origem única.
  • Caminho mais curto de vários nós de origem para vários nós de destino.

Ele usa um padrão de comprimento arbitrário como entrada e retorna um caminho mais curto que existe entre dois nós. Essa função só pode ser usada dentro de MATCH. A função retorna apenas um caminho mais curto entre dois nós determinados. Se houver, dois ou mais caminhos mais curtos do mesmo comprimento entre qualquer par de nós de origem e destino, a função retornará apenas um caminho que foi encontrado primeiro durante a passagem. Um padrão de comprimento arbitrário só pode ser especificado dentro de uma função SHORTEST_PATH.

Para obter a sintaxe completa, consulte MATCH (SQL Graph).

FOR PATH

FOR PATH deve ser usado com qualquer nó ou nome de tabela de borda na cláusula FROM, que participa de um padrão de comprimento arbitrário. FOR PATH informa ao mecanismo que o nó ou a tabela de borda retorna uma coleção ordenada que representa a lista de nós ou bordas encontradas ao longo do caminho percorrido. Os atributos dessas tabelas não podem ser projetados diretamente na cláusula SELECT. Para projetar atributos dessas tabelas, as funções de agregação de caminho de grafo devem ser usadas.

Padrão de comprimento arbitrário

Esse padrão inclui os nós e bordas que devem ser percorridos repetidamente até:

  • O nó desejado é atingido.
  • O número máximo de iterações conforme especificado no padrão é atendido.

Há suporte para os dois quantificadores de padrão a seguir:

  • '+': repita o padrão 1 ou mais vezes. É encerrado assim que encontra um caminho mais curto.
  • {1,n}: repete o padrão 1 por n horas. Termine assim que um menor for encontrado.

LAST_NODE

LAST_NODE() função permite encadeamento de dois padrões de passagem de comprimento arbitrário. Ele pode ser usado em cenários em que:

  • Mais de um padrão de caminho mais curto é usado em uma consulta e um padrão começa no último nó do padrão anterior.
  • Dois padrões de caminho mais curtos se mesclam ao mesmo LAST_NODE().

Ordem do caminho do grafo

A ordem do caminho do grafo refere-se à ordem dos dados no caminho de saída. A ordem do caminho de saída sempre começa na parte não recursiva do padrão seguida pelos nós/bordas que aparecem na parte recursiva. A ordem na qual o grafo é percorrido durante a otimização/execução da consulta não tem nada a ver com a ordem impressa na saída. Da mesma forma, a direção da seta no padrão recursivo também não afeta a ordem do caminho do grafo.

Funções de agregação de caminho de grafo

Como os nós e as bordas envolvidos no padrão de comprimento arbitrário retornam uma coleção (de nós e bordas) percorrida nesse caminho), os usuários não podem projetar os atributos diretamente usando a sintaxe tablename.attributename convencional. Para consultas em que é necessário projetar valores de atributo das tabelas intermediárias de nó ou borda, no caminho percorrido, use as seguintes funções de agregação de caminho de grafo: STRING_AGG, LAST_VALUE, SUM, AVG, MIN, MAX e COUNT. A sintaxe geral para usar essas funções de agregação na cláusula 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

A função STRING_AGG usa uma expressão e um separador como entrada e retorna uma cadeia de caracteres. Os usuários podem usar essa função na cláusula SELECT para projetar atributos dos nós intermediários ou bordas no caminho percorrido.

LAST_VALUE

Para projetar atributos do último nó do caminho percorrido, LAST_VALUE função de agregação pode ser usada. É um erro fornecer alias de tabela de borda como uma entrada para essa função, somente nomes de tabela de nós ou aliases podem ser usados.

Último Nó: o último nó refere-se ao nó que aparece por último no caminho percorrido, independentemente da direção da seta no predicado MATCH. Por exemplo: MATCH(SHORTEST_PATH(n(-(e)->p)+) ). Aqui, o último nó no caminho é o último nó P visitado.

MATCH(SHORTEST_PATH((n<-(e)-)+p)) No padrão, o último nó é o último nó N visitado.

SUM

Essa função retorna a soma de valores de atributo de nó/borda fornecidos ou expressão que apareceu no caminho percorrido.

COUNT

Essa função retorna o número de valores não nulos do atributo de nó/borda especificado no caminho. A função COUNT não dá suporte ao * operador – tentativa de uso de * resultados em um erro de sintaxe.

{  COUNT( <expression> )  <order_clause>  }

AVG

Retorna a média de valores de atributo de nó/borda fornecidos ou expressão que apareceu no caminho percorrido.

MÍN.

Retorna o valor mínimo dos valores de atributo de nó/borda fornecidos ou expressão que apareceu no caminho percorrido.

MÁX.

Retorna o valor máximo dos valores de atributo de nó/borda fornecidos ou expressão que apareceu no caminho percorrido.

Comentários

  • A função SHORTEST_PATH só pode ser usada dentro de MATCH.
  • A função LAST_NODE só tem suporte dentro de SHORTEST_PATH.
  • A função SHORTEST_PATH retorna qualquer caminho mais curto entre nós. Atualmente, ele não dá suporte ao retorno de todos os caminhos mais curtos entre nós; ele também não dá suporte ao retorno de todos os caminhos entre nós.
  • A implementação de SHORTEST_PATH encontra um caminho mais curto sem peso.
  • Em alguns casos, planos inválidos podem ser gerados para consultas com maior número de saltos, o que resulta em tempos de execução de consulta mais altos. Avalie se dicas de consulta como OPTION (HASH JOIN) e/ou OPTION (MAXDOP 1) ajudam.

Exemplos

Para as consultas de exemplo mostradas aqui, usamos as tabelas de nó e borda criadas no exemplo do SQL Graph

a. Encontrar o caminho mais curto entre duas pessoas

No exemplo a seguir, encontramos o caminho mais curto entre Jacob e Alice. Precisamos do nó e friendOf da Person borda criados com base no exemplo do 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. Localize o caminho mais curto de um determinado nó para todos os outros nós no grafo.

O exemplo a seguir localiza todas as pessoas às quais Jacob está conectado no grafo e o caminho mais curto que começa de Jacob para todas essas pessoas.

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. Conte o número de saltos/níveis percorridos para ir de uma pessoa para outra no grafo.

O exemplo a seguir localiza o caminho mais curto entre Jacob e Alice e imprime o número de saltos necessários para ir de Jacob para Alice.

 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. Encontrar pessoas de 1 a 3 saltos para longe de uma determinada pessoa

O exemplo a seguir encontra o caminho mais curto entre Jacob e todas as pessoas às quais Jacob está conectado no grafo de um a três saltos de distância dele.

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. Encontrar pessoas exatamente a dois saltos de uma determinada pessoa

O exemplo a seguir encontra o caminho mais curto entre Jacob e pessoas que estão exatamente a dois saltos dele no grafo.

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. Encontre pessoas de 1 a 3 saltos longe de uma determinada pessoa, que também gosta de um restaurante específico

O exemplo a seguir encontra o caminho mais curto entre Jacob e todas as pessoas às quais ele está conectado no grafo 1-3 salta para longe dele. A consulta também filtra as pessoas conectadas por gostarem de um determinado restaurante. No exemplo abaixo, que LAST_NODE(Person2) retorna o nó final para cada caminho mais curto. O "último" Person nó obtido de LAST_NODE pode então ser "encadeado" para novas travessias para encontrar os restaurantes que eles gostam.

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. Localize o caminho mais curto de um determinado nó para todos os outros nós no grafo, excluindo "loops"

O exemplo a seguir localiza todas as pessoas às quais Alice está conectada no grafo e o caminho mais curto começando de Alice para todas essas pessoas. O exemplo verifica explicitamente se há "loops" em que o nó inicial e final do caminho são os mesmos.

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'

Próximas etapas