funciones - Datos de paso de PostgreSQL de CTE recursivo a la función

pl postgresql

Question

Tengo el siguiente problema: estoy tratando de descubrir todas las rutas posibles desde el nodo fuente ( node_s ) al nodo objetivo ( node_t ).

El formato de la tabla original con los bordes del gráfico es simple: | node_x | node_y | fuerza | , donde "node_x" -> "node_y" es un borde directo con la fuerza del borde como "peso".

La idea es si en cualquier momento durante la exploración de las rutas descubrimos que un nodo entre sus hijos tiene el objetivo node_t , registramos esta ruta y dejamos de explorar rutas desde este nodo; de lo contrario, continuamos la exploración.

La solución simple fue usar el CTE recursivo de PostgreSQL que construye el cierre transitivo del gráfico:

  WITH RECURSIVE transitive_closure (source, target, weight, path_string) AS
  ( 
   --non-recurive term
   SELECT b.node_x, b.node_y, b.strength, b.node_x || ''.'' || b.node_y || ''.'' AS path_string
   FROM best_path b
   WHERE b.node_x = node_s --source_node

   UNION

   --recurive term
   SELECT tc.source, b.node_y, least(tc.weight,b.strength), tc.path_string || b.node_y || ''.'' AS path_string
   FROM best_path AS b JOIN transitive_closure AS tc ON b.node_x = tc.target
   WHERE tc.path_string NOT LIKE ''%'' || b.node_y || ''.%''
  )
  SELECT * 
  FROM transitive_closure tc
  WHERE tc.target = node_t --target_node

El código anterior descubrirá todas las rutas posibles desde el nodo de origen node_s . Solo después de la construcción del cierre transitivo, puedo seleccionar las filas de rutas necesarias desde el nodo de origen al nodo de destino (ver la última instrucción SELECT).

Ejemplo:

La tabla best_path tiene los siguientes datos:

 node_x | node_y | strength 
--------+--------+----------
      1 |      2 |        1
      1 |      3 |        1
      2 |      4 |        1
      2 |      5 |        1
      3 |      6 |        1
      3 |      7 |        1
      4 |      8 |        1
      4 |      9 |        1
      5 |     10 |        1
      5 |     11 |        1

consulta:

encuentre las rutas desde el nodo de origen = 1, al nodo de destino = 4

resultado:

 source | target | strength | path_string
--------+--------+----------+------------
      1 |      2 |        1 | 1.2.
      1 |      3 |        1 | 1.3.
      1 |      4 |        1 | 1.2.4.
      1 |      5 |        1 | 1.2.5.
      1 |      6 |        1 | 1.3.6.
      1 |      7 |        1 | 1.3.7.
      1 |      8 |        1 | 1.2.4.8.
      1 |      9 |        1 | 1.2.4.9.
      1 |     10 |        1 | 1.2.5.10.
      1 |     11 |        1 | 1.2.5.11.

Esto no es lo que necesito. Dado que ya hay un borde directo desde el nodo 2 al nodo 4 (objetivo), no necesito las rutas 1.2.5., 1.2.4.8., 1.2.4.9., 1.2.5.10., 1.2.5.11., La exploración del camino para el nodo 2 debe detenerse en el punto en que se descubrió el camino de 2 a 4.

En resumen, no quiero descubrir las rutas del nodo si ya tiene un borde directo al nodo objetivo. Esto significa que en un término recursivo de CTE, me gustaría tener alguna condición que diga lo siguiente, el pseudocódigo sigue:

  WITH RECURSIVE transitive_closure (source, target, weight, path_string) AS
  ( 
   --non-recurive term (as before)
   SELECT b.node_x, b.node_y, b.strength, b.node_x || ''.'' || b.node_y || ''.'' AS path_string
   FROM best_path b
   WHERE b.node_x = node_s --source_node

   UNION

   --recurive term
   SELECT tc.source, b.node_y, least(tc.weight,b.strength), tc.path_string || b.node_y || ''.'' AS path_string
   FROM best_path AS b JOIN transitive_closure AS tc ON b.node_x = tc.target
   WHERE tc.path_string NOT LIKE ''%'' || b.node_y || ''.%''
     AND b.node_y = node_t 
     --will select only rows with direct edge to target

   UNION (second union is not allowed in CTE)

   SELECT those rows which do not have direct edge to target 
   AND which parents did not contribute to constructing the query above. 
   i.e. b.node_x = tc.target where there is no direct edge between b.node_x to node_t
  )

Como resultado de una consulta para encontrar las rutas del nodo fuente = 1, al nodo objetivo = 4, me gustaría tener lo siguiente:

 source | target | strength | path_string
--------+--------+----------+------------
      1 |      2 |        1 | 1.2.
      1 |      3 |        1 | 1.3.
      1 |      4 |        1 | 1.2.4.
      1 |      6 |        1 | 1.3.6.
      1 |      7 |        1 | 1.3.7.

¡Gracias de antemano por tu ayuda!

Ya lo he intentado de muchas maneras: por ejemplo, las condiciones en las cláusulas FROM / WHERE, tratando de pasar el CTE a la función, pero sin éxito.

Cualquier sugerencia será apreciada.

Tengo mi propia función recursiva que logra lo que quiero, sin embargo, es muy lenta en una enorme cantidad de datos; y el CTE de PostgreSQL aparentemente está bien optimizado, por lo que me gustaría profundizar en él un poco más.

Answer 1

Al volver a leer la pregunta del OP, se me ocurrió esta solución:

fuente

with recursive -- this denotes that at least one CTE is using recursion

inputs as ( select 1 as d_source, 4 as d_target )
,traverse_path(filter, source, target, path, bingo) as
(
  select bp.node_x, bp.node_x,  bp.node_y, bp.node_x || ''.'' || bp.node_y,

    max((bp.node_y = i.d_target)::int) over(partition by bp.node_x) ::bool  

  from best_path bp cross join inputs i
  where bp.node_x = i.d_source -- filter

  union

  select tp.filter, bp.node_x, bp.node_y, path || ''.'' || node_y,   

      max((bp.node_y = i.d_target)::int) over(partition by bp.node_x) ::bool   

  from best_path bp cross join inputs i
  join traverse_path tp on bp.node_x = tp.target
      and not tp.bingo
)    
select tp.*
from traverse_path tp cross join inputs i    
-- if Postgresql has Oracle KEEP windowing, 
-- we don''t need to use WHERE clause here     
where 
  not tp.bingo   
  or
  (
    tp.bingo and tp.target = d_target
  )

La cláusula WHERE anterior podría acortarse a:

  WHERE not bingo or target = 4

Salida:

FILTER  SOURCE  TARGET  PATH    BINGO
1       1       2       1.2     0
1       1       3       1.3     0
1       2       4       1.2.4   1
1       3       6       1.3.6   0
1       3       7       1.3.7   0

Prueba en vivo: http://www.sqlfiddle.com/#!1/cdde6/55

Aquí está el resultado para Source = 2, Target = 5:

FILTER  SOURCE  TARGET  PATH    BINGO
2       2       5       2.5     1

Datos:

CREATE TABLE best_path
    (node_x int, node_y int, strength int);

INSERT INTO best_path
    (node_x, node_y, strength)
VALUES
    (1, 2, 1),
    (1, 3, 1),
    (2, 4, 1),
    (2, 5, 1),
    (3, 6, 1),
    (3, 7, 1),
    (4, 8, 1),
    (4, 9, 1),
    (5, 10, 1),
    (5, 11, 1);

Answer 2

Solución optimizada, no más cláusula WHERE sobre el resultado final; a pesar de la solución específica de Postgresql, es decir, usamos DISTINCT ON para seleccionar una fila específica:

Teniendo en cuenta esta información:

CREATE TABLE best_path
    (node_x int, node_y int, strength int);

INSERT INTO best_path
    (node_x, node_y, strength)
VALUES
    (1, 2, 1),
    (1, 3, 1),
    (2, 4, 1),
    (2, 5, 1),
    (3, 6, 1),
    (3, 7, 1),
    (4, 8, 1),
    (4, 9, 1),
    (5, 10, 1),
    (5, 11, 1),
    (5, 12, 1);

Consulta, primera etapa, muestra detrás de escena (fuente = 1, objetivo = 11):

with recursive -- this denotes that at least one CTE is using recursion

inputs as ( select 1 as d_source, 11 as d_target )
,traverse_path(filter, source, target, path, bingo, distincter) as
(
  select                      
      bp.node_x, bp.node_x,  bp.node_y, bp.node_x || ''.'' || bp.node_y      
      ,max((bp.node_y = i.d_target)::int) over(partition by bp.node_x) ::bool            
      ,coalesce(
               nullif(
                   max((bp.node_y = i.d_target)::int) 
                   over(partition by bp.node_x order by bp.node_x, bp.node_y = d_target desc, bp.node_y)
                   , 0)          
               ,bp.node_y)                           
  from best_path bp cross join inputs i
  where bp.node_x = i.d_source -- filter      
  union      
  select 
      tp.filter, bp.node_x, bp.node_y, path || ''.'' || node_y       
      ,max((bp.node_y = i.d_target)::int) over(partition by bp.node_x) ::bool        
      ,coalesce(
               nullif(
                   max((bp.node_y = i.d_target)::int) 
                   over(partition by bp.node_x order by bp.node_x, bp.node_y = d_target desc, bp.node_y)
                   , 0)          
               ,bp.node_y)                       
  from best_path bp cross join inputs i
  join traverse_path tp on bp.node_x = tp.target
      and not tp.bingo
)    
select tp.*
from traverse_path tp 

Salida para source = 1, target = 11: http://www.sqlfiddle.com/#!1/db290/56

FILTER   SOURCE   TARGET   PATH     BINGO    DISTINCTER
1        1        2        1.2      0        2
1        1        3        1.3      0        3
1        2        4        1.2.4    0        4
1        2        5        1.2.5    0        5
1        3        6        1.3.6    0        6
1        3        7        1.3.7    0        7
1        4        8        1.2.4.8  0        8
1        4        9        1.2.4.9  0        9
1        5        11       1.2.5.11 1        1
1        5        10       1.2.5.10 1        1
1        5        12       1.2.5.12 1        1

Como podemos ver, el objetivo 11 es la primera fila entre las fuentes de 5. ¿Cómo sucedió esto? En nuestra columna DISTINCTER, usamos ORDER BY en MAX, esta es una de las raras ocasiones en que un ORDER en ventanas MAX tiene sentido. Simplemente lo usamos para ordenar nuestro resultado. Intenté colocar el ORDER BY al final de la consulta, pero la base de datos se queja de que no puede usar ORDER en CTE. CTE prohíbe colocar una cláusula ORDER BY. Pero como todos sabemos, podemos influir en la clasificación en la cláusula OVER() , así es como se clasifican nuestros resultados. En el resultado anterior, entre la fuente de 5, el número 11 ordena antes de 10 y 12, ya que 11 es nuestro objetivo. Entonces, cuando hacemos un DISTINCT ON (función específica de Postgresql), Postgres recogerá esa primera línea, por lo tanto, recuperará el objetivo 11.

Esta es nuestra consulta final, optimizada, aunque específica de Postgresql:

with recursive -- this denotes that at least one CTE is using recursion    
inputs as ( select 1 as d_source, 11 as d_target )
,traverse_path(filter, source, target, path, bingo) as (
  select 
      distinct on (
        bp.node_x,            
        coalesce(
               nullif(
                   max((bp.node_y = i.d_target)::int) 
                   over(partition by bp.node_x order by bp.node_x, bp.node_y = d_target desc, bp.node_y)
                   , 0)          
               ,bp.node_y)
      )          
      bp.node_x, bp.node_x,  bp.node_y, bp.node_x || ''.'' || bp.node_y      
      ,max((bp.node_y = i.d_target)::int) over(partition by bp.node_x) ::bool  
  from best_path bp cross join inputs i
  where bp.node_x = i.d_source -- filter
  union
  select       
      distinct on (
        bp.node_x,            
        coalesce(
               nullif(
                   max((bp.node_y = i.d_target)::int) 
                   over(partition by bp.node_x order by bp.node_x, bp.node_y = d_target desc, bp.node_y)
                   , 0)          
               ,bp.node_y)
      )    
      tp.filter, bp.node_x, bp.node_y, path || ''.'' || node_y       
      ,max((bp.node_y = i.d_target)::int) over(partition by bp.node_x) ::bool  
  from best_path bp cross join inputs i
  join traverse_path tp on bp.node_x = tp.target
      and not tp.bingo
) select tp.* from traverse_path tp

Salida para source = 1, target = 11 http://www.sqlfiddle.com/#!1/db290/55

FILTER   SOURCE   TARGET   PATH     BINGO
1        1        2        1.2      0
1        1        3        1.3      0
1        2        4        1.2.4    0
1        2        5        1.2.5    0
1        3        6        1.3.6    0
1        3        7        1.3.7    0
1        4        8        1.2.4.8  0
1        4        9        1.2.4.9  0
1        5        11       1.2.5.11 1

Salida para source = 1, target = 4: http://www.sqlfiddle.com/#!1/db290/53

FILTER  SOURCE  TARGET  PATH    BINGO
1       1       2       1.2     0
1       1       3       1.3     0
1       2       4       1.2.4   1
1       3       6       1.3.6   0
1       3       7       1.3.7   0

Salida para source = 2, target = 5: http://www.sqlfiddle.com/#!1/db290/54

FILTER  SOURCE  TARGET  PATH    BINGO
2       2       5       2.5     1

Otro enfoque, en lugar del enfoque BINGO. Utilice continue_search como la lógica para continuar el travesal. Y use CADA función agregada para determinar si necesitamos continuar atravesando el gráfico.

Así es como funciona: http://www.sqlfiddle.com/#!1/db290/84

Consulta final: http://www.sqlfiddle.com/#!1/db290/85

Es interesante notar que TODOS son muy parecidos a los ingleses:

Contraste esto:

,max((bp.node_y = i.d_target)::int) over(partition by bp.node_x) ::bool  

Con usar CADA:

,every(bp.node_y <> i.d_target) over(partition by bp.node_x)

¿Cuál es más fácil de leer?

Aquí está el resultado que ilustra el principio de usar TODOS para facilitar DISTINCT ON:

Fuente = 1, Objetivo = 5. Tenga en cuenta que 5 se ordena primero antes que otros números que pertenecen a la misma fuente, esto luego será recogido por DISTINCT ON.

FILTER    SOURCE    TARGET    PATH      CONTINUE_SEARCH     DISTINCTER
1         1         2         1.2       1                   2
1         1         3         1.3       1                   3
1         2         5         1.2.5     0                   0
1         2         4         1.2.4     0                   0
1         3         6         1.3.6     1                   6
1         3         7         1.3.7     1                   7

Aquí está la consulta que hace ese principio:

with recursive -- this denotes that at least one CTE is using recursion

inputs as ( select 1 as d_source, 5 as d_target )
,traverse_path(filter, source, target, path, continue_search, distincter) as
(
  select                      
      bp.node_x, bp.node_x,  bp.node_y, concat(bp.node_x , ''.'' , bp.node_y )
      ,every(bp.node_y <> i.d_target) over(partition by bp.node_x)          
      ,coalesce(        
              cast(nullif(
                   every(bp.node_y <> i.d_target) 
                   over(partition by bp.node_x order by bp.node_x, bp.node_y = d_target desc, bp.node_y)
                   , true) as int)
               ,bp.node_y)                           
  from best_path bp cross join inputs i
  where bp.node_x = i.d_source -- filter      
  union      
  select 
      tp.filter, bp.node_x, bp.node_y, concat(path , ''.'' , node_y)
      ,every(bp.node_y <> i.d_target) over(partition by bp.node_x)    
      ,coalesce(
              cast(nullif(
                   every(bp.node_y <> i.d_target) 
                   over(partition by bp.node_x order by bp.node_x, bp.node_y = d_target desc, bp.node_y)
                   , true) as int)
               ,bp.node_y)                       
  from best_path bp cross join inputs i
  join traverse_path tp on bp.node_x = tp.target
     and tp.continue_search
)    
select tp.*
from traverse_path tp 

Consulta final:

with recursive -- this denotes that at least one CTE is using recursion

inputs as ( select 1 as d_source, 5 as d_target )
,traverse_path(filter, source, target, path, continue_search) as
(
  select                      
      distinct on
      (
        bp.node_x
        ,coalesce(
              cast(nullif(
                   every(bp.node_y <> i.d_target) 
                   over(partition by bp.node_x order by bp.node_x, bp.node_y = d_target desc, bp.node_y)
                   , true) as int)
               ,bp.node_y)                       
      )    
      bp.node_x, bp.node_x,  bp.node_y, concat(bp.node_x , ''.'' , bp.node_y )
      ,every(bp.node_y <> i.d_target) over(partition by bp.node_x)          
  from best_path bp cross join inputs i
  where bp.node_x = i.d_source -- filter      
  union      
  select   
      distinct on
      (
        bp.node_x
        ,coalesce(
              cast(nullif(
                   every(bp.node_y <> i.d_target) 
                   over(partition by bp.node_x order by bp.node_x, bp.node_y = d_target desc, bp.node_y)
                   , true) as int)
               ,bp.node_y)                       
      )  
      tp.filter, bp.node_x, bp.node_y, concat(path , ''.'' , node_y)
      ,every(bp.node_y <> i.d_target) over(partition by bp.node_x)          
  from best_path bp cross join inputs i
  join traverse_path tp on bp.node_x = tp.target
     and tp.continue_search
)    
select tp.*
from traverse_path tp 

Salida:

FILTER    SOURCE    TARGET    PATH      CONTINUE_SEARCH
1         1         2         1.2       1
1         1         3         1.3       1
1         2         5         1.2.5     0
1         3         6         1.3.6     1
1         3         7         1.3.7     1

Answer 3

Puede hacer que la búsqueda de la ruta sea más eficiente si comienza desde abajo. Comience por los niños. Si comienza en el padre, implica atravesar a todos los niños; mientras que si buscó desde el niño, solo tiene un padre, por lo tanto, no perderá el tiempo buscando la ruta entre el origen y el destino.

with recursive find_parent(source, target, recentness) as
(
    select source, target, 0 
    from tbl
    where target = 9

    union all

    select i.source, i.target, fp.recentness + 1
    from tbl i
    join find_parent fp on i.target = fp.source
),
construct_path(source, target, recentness, path) as
(
  select source, target, recentness, source || ''.'' || target
  from find_parent 
  where recentness = (select max(recentness) from find_parent)

  union

  select dd.source, dd.target, dd.recentness, cp.path || ''.'' || dd.target
  from find_parent dd
  join construct_path cp on dd.recentness = cp.recentness - 1  
)
select source, target, path 
from construct_path
order by recentness desc

Salida:

SOURCE   TARGET   PATH
1        2        1.2
2        4        1.2.4
4        9        1.2.4.9

Prueba en vivo: http://www.sqlfiddle.com/#!1/13e6b/1

Similar a esto: Cómo obtener el padre dado a un niño en SQL SERVER 2005

Esto está optimizado, corte la recursión en el padre si ya encuentra el específico (fuente).

Fuente = 2

Objetivo = 9

with recursive find_parent(source, target, recentness) as
(
    select source, target, 0 
    from tbl
    where target = 9

    union all

    select i.source, i.target, fp.recentness + 1
    from tbl i
    join find_parent fp on i.target = fp.source 
         -- despite the name, this target is another one''s source
         and i.target <> 2
)
,construct_path(source, target, recentness, path) as
(
    select source, target, recentness, source || ''.'' || target
    from find_parent 
    where recentness = (select max(recentness) from find_parent)

    union

    select dd.source, dd.target, dd.recentness, cp.path || ''.'' || dd.target
    from find_parent dd
    join construct_path cp on dd.recentness = cp.recentness - 1  

)
select source, target, path
from construct_path
order by recentness desc

Salida:

SOURCE   TARGET  PATH
2        4       2.4
4        9       2.4.9

Prueba en vivo: http://www.sqlfiddle.com/#!1/13e6b/16

Answer 4

Tabla temporal para la prueba:

CREATE TEMP TABLE best_path (node_x int, node_y int, strength int);
INSERT INTO best_path  VALUES
 (1, 2,  1)
,(1, 3,  1)
,(2, 4,  1)
,(2, 5,  1)
,(3, 6,  1)
,(3, 7,  1)
,(4, 8,  1)
,(4, 9,  1)
,(5, 10, 1)
,(5, 11, 1);

Consulta:
_{modificado para acomodar el comentario sobre 2 - 5}

WITH RECURSIVE t AS (    -- for readability and convenience:
    SELECT 1 AS node_s   -- source_node
         , 4 AS node_t   -- target_node
    )
    , x AS (
    SELECT node_x
    FROM   t, best_path
    WHERE  node_y = node_t
    )
    , a AS  ( 
    SELECT b.node_x
         , b.node_y
         , b.strength AS weight
         , b.node_x || ''.'' || b.node_y || ''.'' AS path
    FROM   t, best_path b
    LEFT   JOIN x ON x.node_x = b.node_x
    WHERE  b.node_x = node_s
    AND    (x.node_x IS NULL                    -- no point with edge to target
            OR b.node_y = node_t)               -- except with target_node

    UNION ALL
    SELECT a.node_x
         , b.node_y
         , least(a.weight, b.strength)
         , a.path || b.node_y || ''.'' AS path
    FROM   t, a
    JOIN   best_path AS b ON b.node_x = a.node_y
    LEFT   JOIN x ON x.node_x = b.node_x
    WHERE  a.node_y <> node_t                   -- arrived at target
    AND    a.path !~~ (''%'' || b.node_y || ''.%'') -- not visited yet
    AND    (x.node_x IS NULL                    -- no point with edge to target
            OR b.node_y = node_t)               -- except with target_node
    )
TABLE a;

Produce el resultado solicitado exactamente.

Agregué la condición de salto a la consulta inicial, también, porque podemos alcanzar el objetivo en solo un paso.

Esto pasa a ser muy parecido a mi respuesta a una pregunta anterior similar . Se aplican todas las explicaciones y enlaces. El truco más importante aquí es incluir un CTE x adicional para recolectar los nodos que ...

tener (a) ventaja directa al objetivo.

Para uso repetido en la condición de corte del CTE recursivo. No es ampliamente conocido que puede agregar CTE adicionales (no recursivos) sobre un CTE recursivo independientemente de la palabra clave RECURSIVE .