Partilhar via

SHORTEST_PATH (Transact-SQL)

  • Artigo

Aplica-se a: SQL Server 2019 (15.x) e versões posteriores Banco de Dados SQL do AzureInstância Gerenciada SQL do Azurebanco de dados SQL no Microsoft Fabric

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

Transact-SQL convenções de sintaxe

Caminho mais curto

A função SHORTEST_PATH permite encontrar:

  • Um caminho mais curto entre dois nós/entidades dados
  • Caminho(s) mais curto(s) de fonte ú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. Esta função só pode ser usada dentro de MATCH. A função retorna apenas um caminho mais curto entre quaisquer dois nós fornecidos. Se existirem, dois ou mais caminhos mais curtos do mesmo comprimento entre qualquer par de nó(s) de origem e de destino, a função retornará apenas um caminho que foi encontrado primeiro durante a travessia. 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).

PARA CAMINHO

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

Padrão de comprimento arbitrário

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

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

Os dois quantificadores de padrão a seguir são suportados:

  • '+' : Repita o padrão 1 ou mais vezes. Encerre assim que um caminho mais curto for encontrado.
  • {1,n}: Repita o padrão de 1 a n vezes. Encerre assim que um mais curto for encontrado.

LAST_NODE

LAST_NODE() função permite o encadeamento de dois padrões de travessia de comprimento arbitrário. Pode ser utilizado 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 nó LAST do padrão anterior.
  • Dois padrões de caminho mais curto se fundem ao mesmo LAST_NODE().

Ordem do caminho do gráfico

A ordem do caminho do gráfico 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 em que o gráfico é 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 gráfico.

Funções de agregação de caminho gráfico

Como os nós e bordas envolvidos no padrão de comprimento arbitrário retornam uma coleção (de nó(s) e a(s) borda(s) percorrida(s) 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 atributos do nó intermediário ou tabelas de borda, no caminho percorrido, use as seguintes funções de agregação de caminho gráfico: STRING_AGG, LAST_VALUE, SUM, AVG, MIN, MAX e COUNT. A sintaxe geral para usar essas funções agregadas 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 agregada pode ser usada. É um erro fornecer alias de tabela de borda como uma entrada para essa função, apenas nomes de tabela de nó ou aliases podem ser usados.

Último nó: O último nó refere-se ao nó que aparece em último lugar 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.

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

SOMA

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

CONTAGEM

Esta função retorna o número de valores não nulos do atributo node/edge especificado no caminho. A função COUNT não suporta o operador * - tentativa de uso de * resulta em um erro de sintaxe.

{  COUNT( <expression> )  <order_clause>  }

AVG

Retorna a média dos valores ou expressões de atributos de nó/borda fornecidos que apareceram no caminho percorrido.

MIN

Retorna o valor mínimo dos valores de atributo de nó/borda fornecidos ou da 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ó é suportada dentro SHORTEST_PATH.
  • A função SHORTEST_PATH retorna qualquer um caminho mais curto entre nós. Atualmente, ele não suporta o retorno todos os caminhos mais curtos entre nós; ele também não suporta o retorno todos os caminhos entre nós.
  • A implementação SHORTEST_PATH encontra um caminho mais curto não ponderado.
  • Em alguns casos, planos incorretos 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 em exemplo do SQL Graph

Um. Encontre o caminho mais curto entre duas pessoas

No exemplo a seguir, encontramos o caminho mais curto entre Jacó e Alice. Precisamos do nó Person e da borda friendOf criada a partir de 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. Encontre o caminho mais curto de um determinado nó para todos os outros nós no gráfico.

O exemplo a seguir encontra todas as pessoas às quais Jacó está conectado no gráfico e o caminho mais curto partindo de Jacó 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 lúpulos/níveis percorridos para ir de uma pessoa para outra no gráfico.

O exemplo a seguir encontra o caminho mais curto entre Jacob e Alice e imprime o número de lúpulos necessários para ir de Jacob a 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. Encontre pessoas a 1-3 saltos de distância de uma determinada pessoa

O exemplo a seguir encontra o caminho mais curto entre Jacó e todas as pessoas às quais Jacó está conectado no gráfico a 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. Encontre pessoas a exatamente dois saltos de distância de uma determinada pessoa

O exemplo a seguir encontra o caminho mais curto entre Jacob e pessoas que estão exatamente a dois saltos de distância dele no gráfico.

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 de distância de uma determinada pessoa, que também gostam 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 gráfico 1-3 saltos para longe dele. A consulta também filtra as pessoas conectadas por gostarem de um determinado restaurante. No exemplo abaixo, esse LAST_NODE(Person2) retorna o nó final para cada caminho mais curto. O "último" nó de Person obtido de LAST_NODE pode então ser "acorrentado" para mais travessias para encontrar o(s) restaurante(s) de que 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. Encontre o caminho mais curto de um determinado nó para todos os outros nós no gráfico, excluindo "loops"

O exemplo a seguir encontra todas as pessoas às quais Alice está conectada no gráfico e o caminho mais curto a partir de Alice para todas essas pessoas. O exemplo verifica explicitamente se há "loops" em que o nó inicial e o nó 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óximos passos