Partilhar via

SHORTEST_PATH (Transact-SQL)

  • Artigo

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

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

Convenções de sintaxe de Transact-SQL

Caminho mais curto

A função SHORTEST_PATH permite encontrar:

  • Um caminho mais curto entre dois nós/entidades fornecidos
  • 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 CORRES. A função retorna apenas um caminho mais curto entre dois nós fornecidos. Se existirem 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).

PARA CAMINHO

FOR PATH deve ser usado com qualquer nome de tabela de nó ou 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 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 agregadas de caminho de gráfico devem ser usadas.

Padrão de comprimento arbitrário

Esse padrão inclui os nós e as 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. É encerrado assim que encontra um caminho mais curto.
  • {1,n}: repete o padrão 1 por n horas. Encerre assim que um shortest for encontrado.

LAST_NODE

LAST_NODE() permite o encadeamento de dois padrões de travessia 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 fundem no 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/arestas 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 gráfico.

Funções agregadas de caminho de gráfico

Como os nós e bordas envolvidos no padrão de comprimento arbitrário retornam uma coleção (de nós e bordas atravessadas nesse caminho), os usuários não podem projetar os atributos diretamente usando a sintaxe convencional tablename.attributename. Para consultas em que é necessário projetar valores de atributo do nó intermediário ou tabelas de borda, no caminho percorrido, use as seguintes funções agregadas de caminho de 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 esta função, somente nomes de tabela de nó 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 CORRESP. 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 dos valores de atributo de nó/borda fornecidos ou expressão que apareceram 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 - a tentativa de uso de resulta em um erro de * sintaxe.

{  COUNT( <expression> )  <order_clause>  }

AVG

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

MÍN.

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

MÁX.

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

Comentários

  • A função SHORTEST_PATH só pode ser usada dentro de CORRES.
  • A função LAST_NODE só é suportada dentro SHORTEST_PATH.
  • A função SHORTEST_PATH retorna qualquer caminho mais curto entre os nós. Atualmente, ele não oferece suporte ao retorno de todos os caminhos mais curtos entre os nós; ele também não oferece suporte ao retorno de todos os caminhos entre os nós.
  • A implementação SHORTEST_PATH encontra um caminho mais curto não ponderado.
  • 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

R. Encontre o caminho mais curto entre duas pessoas

No exemplo a seguir, encontramos o caminho mais curto entre Jacó e Alice. Precisamos do nó e friendOf da borda criados a Person partir do 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 a partir 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 saltos/níveis percorridos para ir de uma pessoa para outra no gráfico.

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 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 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. Encontre pessoas exatamente a dois saltos de distância de uma determinada pessoa

O exemplo a seguir encontra o caminho mais curto entre Jacob e as pessoas que estão exatamente a dois saltos 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 a 1-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, isso LAST_NODE(Person2) retorna o nó final para cada caminho mais curto. O "último" Person nó obtido pode LAST_NODE então ser "encadeado" para travessias adicionais 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 localiza 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 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