Compartir a través de

SHORTEST_PATH (Transact-SQL)

  • Artículo

Se aplica a: SQL Server 2019 (15.x) y versiones posteriores de Azure SQL Database Azure SQL database Instancia administrada SQL Database en Microsoft Fabric

Especifica una condición de búsqueda para un grafo, que se busca de forma recursiva o repetitiva. SHORTEST_PATH se pueden usar dentro de MATCH con tablas perimetrales y nodos de grafos, en la instrucción SELECT.

Convenciones de sintaxis de Transact-SQL

Ruta de acceso más corta

La función SHORTEST_PATH le permite encontrar:

  • Ruta de acceso más corta entre dos nodos o entidades dados
  • Rutas de acceso más cortas de origen únicas.
  • Ruta de acceso más corta de varios nodos de origen a varios nodos de destino.

Toma un patrón de longitud arbitraria como entrada y devuelve una ruta de acceso más corta que existe entre dos nodos. Esta función solo se puede usar dentro de MATCH. La función devuelve solo una ruta de acceso más corta entre dos nodos dados. Si existe, dos o más rutas de acceso más cortas de la misma longitud entre cualquier par de nodos de origen y de destino, la función devuelve solo una ruta de acceso que se encontró primero durante el recorrido. Un patrón de longitud arbitraria solo se puede especificar dentro de una función SHORTEST_PATH.

Para obtener una sintaxis completa, consulte MATCH (SQL Graph).

FOR PATH

FOR PATH debe usarse con cualquier nombre de tabla perimetral o nodo en la cláusula FROM, que participa en un patrón de longitud arbitraria. FOR PATH indica al motor que el nodo o la tabla perimetral devuelve una colección ordenada que representa la lista de nodos o bordes que se encuentran a lo largo de la ruta de acceso atravesada. Los atributos de estas tablas no se pueden proyectar directamente en la cláusula SELECT. Para proyectar atributos de estas tablas, se deben usar las funciones de agregado de ruta de acceso del grafo.

Patrón de longitud arbitraria

Este patrón incluye los nodos y bordes que deben atravesarse repetidamente hasta que:

  • Se alcanza el nodo deseado.
  • Se cumple el número máximo de iteraciones especificadas en el patrón.

Se admiten los dos cuantificadores de patrones siguientes:

  • '+': repita el patrón 1 o más veces. Finaliza en cuanto encuentra una ruta de acceso más corta.
  • {1, n} : repite el patrón de 1 a n veces. Finalice tan pronto como se encuentre el más corto.

LAST_NODE

LAST_NODE() función permite encadenar dos patrones de recorrido de longitud arbitraria. Se puede usar en escenarios en los que:

  • Se usan más de un patrón de ruta de acceso más corto en una consulta y un patrón comienza en el último nodo del patrón anterior.
  • Dos patrones de ruta de acceso más cortos se combinan en la misma LAST_NODE().

Orden de ruta de acceso del grafo

El orden de la ruta de acceso del grafo hace referencia al orden de los datos en la ruta de acceso de salida. El orden de la ruta de acceso de salida siempre comienza en la parte no recursiva del patrón seguido de los nodos o bordes que aparecen en la parte recursiva. El orden en el que se recorre el gráfico durante la optimización o ejecución de consultas no tiene nada que ver con el orden impreso en la salida. Del mismo modo, la dirección de la flecha en el patrón recursivo tampoco afecta al orden de la ruta de acceso del grafo.

Funciones de agregado de ruta de acceso de grafo

Dado que los nodos y bordes implicados en el patrón de longitud arbitraria devuelven una colección (de nodos y bordes recorridos en esa ruta de acceso), los usuarios no pueden proyectar los atributos directamente mediante la sintaxis convencional tablename.attributename. Para las consultas en las que es necesario proyectar valores de atributo desde las tablas perimetrales o nodos intermedios, en la ruta de acceso recorrido, use las siguientes funciones de agregado de ruta de acceso de grafo: STRING_AGG, LAST_VALUE, SUM, AVG, MIN, MAX y COUNT. La sintaxis general para usar estas funciones de agregado en la cláusula SELECT es:

<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

La función STRING_AGG toma una expresión y un separador como entrada y devuelve una cadena. Los usuarios pueden usar esta función en la cláusula SELECT para proyectar atributos de los nodos intermedios o bordes de la ruta de acceso que atraviesa.

LAST_VALUE

Para proyectar atributos del último nodo de ruta de acceso recorrido, se puede usar LAST_VALUE función de agregado. Se trata de un error para proporcionar alias de tabla perimetral como entrada a esta función, solo se pueden usar nombres de tabla de nodo o alias.

Último nodo: el último nodo hace referencia al nodo que aparece por última vez en la ruta de acceso atravesada, independientemente de la dirección de la flecha en el predicado MATCH. Por ejemplo: MATCH(SHORTEST_PATH(n(-(e)->p)+) ). Aquí el último nodo de la ruta de acceso es el último nodo P visitado.

En el MATCH(SHORTEST_PATH((n<-(e)-)+p)) patrón, el último nodo es el último nodo N visitado.

SUM

Esta función devuelve la suma de los valores de atributo de nodo o borde proporcionados o la expresión que aparecían en la ruta de acceso atravesada.

COUNT

Esta función devuelve el número de valores no NULL del atributo node/edge especificado en la ruta de acceso. La función COUNT no admite el * operador : se intentó usar los resultados en un error de * sintaxis.

{  COUNT( <expression> )  <order_clause>  }

MEDIA

Devuelve el promedio de valores de atributo de nodo o borde proporcionados o expresión que aparecían en la ruta de acceso atravesada.

MÍN

Devuelve el valor mínimo de los valores de atributo de nodo o borde proporcionados o la expresión que aparecían en la ruta de acceso atravesada.

MAX

Devuelve el valor máximo de los valores de atributo de nodo o borde proporcionados o la expresión que aparecían en la ruta de acceso atravesada.

Comentarios

  • La función SHORTEST_PATH solo se puede usar dentro de MATCH.
  • La función LAST_NODE solo se admite dentro de SHORTEST_PATH.
  • La función SHORTEST_PATH devuelve una ruta de acceso más corta entre los nodos. Actualmente no admite la devolución de todas las rutas de acceso más cortas entre los nodos; tampoco admite la devolución de todas las rutas de acceso entre nodos.
  • La implementación de SHORTEST_PATH busca una ruta de acceso más corta sin peso.
  • En algunos casos, se pueden generar planes incorrectos para consultas con un mayor número de saltos, lo que da como resultado tiempos de ejecución de consultas más altos. Evalúe si las sugerencias de consulta como OPTION (HASH JOIN) y / o OPTION (MAXDOP 1) ayudan.

Ejemplos

Para ver las consultas de ejemplo que se muestran aquí, usamos las tablas perimetrales y de nodo creadas en el ejemplo de SQL Graph.

A Buscar la ruta más corta entre dos personas

En el ejemplo siguiente, encontramos el camino más corto entre Jacob y Alice. Necesitamos el nodo y friendOf el Person borde creados a partir del ejemplo de 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. Busque la ruta de acceso más corta de un nodo determinado a todos los demás nodos del gráfico.

En el ejemplo siguiente se encuentran todas las personas a las que Jacob está conectado en el gráfico y la ruta más corta a partir de Jacob a todas esas personas.

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. Cuente el número de saltos o niveles recorridos para pasar de una persona a otra en el gráfico.

En el ejemplo siguiente se encuentra la ruta más corta entre Jacob y Alice e imprime el número de saltos que se tardan en 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. Buscar personas de 1 a 3 saltos lejos de una persona determinada

En el ejemplo siguiente se encuentra el camino más corto entre Jacob y todas las personas a las que Jacob está conectado en el gráfico uno a tres saltos lejos de él.

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. Buscar personas exactamente dos saltos lejos de una persona determinada

En el ejemplo siguiente se encuentra el camino más corto entre Jacob y las personas que están exactamente dos saltos lejos de él en el 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. Encuentra personas de 1 a 3 saltos lejos de una persona determinada, que también le gusta un restaurante específico

En el ejemplo siguiente se encuentra el camino más corto entre Jacob y todas las personas a las que está conectado en el gráfico 1-3 saltos lejos de él. La consulta también filtra a las personas conectadas por su gusto en un restaurante determinado. En el ejemplo siguiente, que LAST_NODE(Person2) devuelve el nodo final para cada ruta de acceso más corta. El nodo "último" Person obtenido de LAST_NODE puede ser "encadenado" para encontrar los restaurantes a los que les gusta.

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. Busque la ruta de acceso más corta de un nodo determinado a todos los demás nodos del grafo, excepto "bucles".

En el ejemplo siguiente se buscan todas las personas a las que Alice está conectado en el gráfico y la ruta más corta que comienza desde Alice a todas esas personas. En el ejemplo se comprueba explícitamente si hay "bucles" en los que el nodo inicial y final de la ruta de acceso son los mismos.

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'

Pasos siguientes