SHORTEST_PATH (Transact-SQL)

  • Artículo

Se aplica a: SQL Server 2019 (15.x) y versiones posteriores Azure SQL DatabaseAzure SQL Managed Instance

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:

  • Una ruta de acceso más corta entre dos nodos o entidades dados
  • Rutas de acceso más cortas de origen única.
  • 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. 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 se deben recorrer 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 el mismo 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 se inicia 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 gráfico.

Funciones de agregado de ruta de acceso de grafo

Dado que los nodos y los 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 tablename.attributename convencional. Para las consultas en las que es necesario proyectar valores de atributo desde las tablas perimetrales o del nodo intermedio, en la ruta de acceso que atraviesa, use las siguientes funciones de agregado de ruta de acceso del 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 o bordes intermedios de la ruta de acceso que se 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 o alias de nodo.

Último nodo: el último nodo hace referencia al nodo que aparece por última vez en la ruta de acceso que atraviesa, 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 expresión que aparecieron 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 - intento de uso de 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 recorrido.

MÍN

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

MÁX

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

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 no ponderada.
  • En algunos casos, se pueden generar planes incorrectos para las consultas con un mayor número de saltos, lo que da como resultado tiempos de ejecución de consultas mayores. Evalúe si las sugerencias de consulta como OPTION (HASH JOIN) y /o OPTION (MAXDOP 1) ayudan.

Ejemplos

Para las consultas de ejemplo que se muestran aquí, se usan 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 buscan todas las personas a las que Jacob está conectado en el gráfico y la ruta más corta que comienza desde 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. Encontrar 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. Encontrar a la gente 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 que los recorridos adicionales encuentren los restaurantes 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 gráfico, 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 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