sql - recursivo - Visitar un gráfico dirigido como si fuera uno no dirigido, utilizando una consulta recursiva

recursividad en mysql

Question

Necesito su ayuda sobre la visita de un gráfico dirigido almacenado en una base de datos.

Considere el siguiente gráfico dirigido

1->2 
2->1,3 
3->1

Una tabla almacena esas relaciones:

create database test;
/c test;

create table ownership (
    parent bigint,
    child  bigint,
    primary key (parent, child)
);

insert into ownership (parent, child) values (1, 2);
insert into ownership (parent, child) values (2, 1);
insert into ownership (parent, child) values (2, 3);
insert into ownership (parent, child) values (3, 1);

Me gustaría extraer todos los bordes semi-conectados (es decir, los bordes conectados ignorando la dirección) de la gráfica accesible desde un nodo . Es decir, si comienzo desde parent = 1, me gustaría tener la siguiente salida

1,2
2,1
2,3
3,1

Estoy usando postgresql .

Modifiqué el ejemplo en el manual de Postgres que explica las consultas recursivas, y he adaptado la condición de unión para ir "arriba" y "abajo" (ignorando las indicaciones). Mi consulta es la siguiente:

/c test

WITH RECURSIVE graph(parent, child, path, depth, cycle) AS (
SELECT o.parent, o.child, ARRAY[ROW(o.parent, o.child)], 0, false
    from ownership o
    where o.parent = 1
UNION ALL
SELECT 
    o.parent, o.child,
    path||ROW(o.parent, o.child), 
    depth+1, 
    ROW(o.parent, o.child) = ANY(path)
    from 
        ownership o, graph g
    where 
        (g.parent = o.child or g.child = o.parent) 
        and not cycle

)
select  g.parent, g.child, g.path, g.cycle
from
    graph g

su salida sigue:

 parent | child |               path                | cycle 
--------+-------+-----------------------------------+-------
      1 |     2 | {"(1,2)"}                         | f
      2 |     1 | {"(1,2)","(2,1)"}                 | f
      2 |     3 | {"(1,2)","(2,3)"}                 | f
      3 |     1 | {"(1,2)","(3,1)"}                 | f
      1 |     2 | {"(1,2)","(2,1)","(1,2)"}         | t
      1 |     2 | {"(1,2)","(2,3)","(1,2)"}         | t
      3 |     1 | {"(1,2)","(2,3)","(3,1)"}         | f
      1 |     2 | {"(1,2)","(3,1)","(1,2)"}         | t
      2 |     3 | {"(1,2)","(3,1)","(2,3)"}         | f
      1 |     2 | {"(1,2)","(2,3)","(3,1)","(1,2)"} | t
      2 |     3 | {"(1,2)","(2,3)","(3,1)","(2,3)"} | t
      1 |     2 | {"(1,2)","(3,1)","(2,3)","(1,2)"} | t
      3 |     1 | {"(1,2)","(3,1)","(2,3)","(3,1)"} | t
(13 rows)

Tengo un problema : la consulta extrae los mismos bordes muchas veces , ya que se alcanzan a través de diferentes rutas, y me gustaría evitar esto. Si modifico la consulta externa en

select  distinct g.parent, g.child from graph

Tengo el resultado deseado, pero las ineficiencias permanecen en la consulta CON, ya que se realizan las uniones innecesarias. Entonces, ¿hay una solución para extraer los bordes alcanzables de un gráfico en un DB, comenzando desde uno dado, sin usar distinct?

También tengo otro problema (este está resuelto, mira en la parte inferior): como puedes ver en la salida, los ciclos se detienen solo cuando se alcanza un nodo por segunda vez . Es decir, tengo (1,2) (2,3) (1,2) . Me gustaría detener el ciclo antes de volver a ciclar sobre ese último nodo, es decir, tener (1,2) (2,3) . Intenté modificar la condición where de la siguiente manera

where
    (g.parent = o.child or g.child = o.parent) 
    and (ROW(o.parent, o.child) <> any(path))
    and not cycle

para evitar visitar los bordes ya visitados, pero no funciona y no puedo entender por qué ( (ROW(o.parent, o.child) <> any(path) ) debe evitar el ciclismo antes de volver al borde de la bicicleta pero no funciona t trabajo). ¿Cómo puedo hacer para detener los ciclos un paso antes del nodo que cierra el ciclo?

Editar : como sugirió danihp, para resolver el segundo problema que utilicé

where
    (g.parent = o.child or g.child = o.parent) 
    and not (ROW(o.parent, o.child) = any(path))
    and not cycle

y ahora la salida no contiene ciclos. Las filas pasaron de 13 a 6, pero todavía tengo duplicados, por lo que el problema principal (el primero) de extraer todos los bordes sin duplicados y sin diferencia sigue vivo. Salida actual con and not ROW

 parent | child |           path            | cycle 
--------+-------+---------------------------+-------
      1 |     2 | {"(1,2)"}                 | f
      2 |     1 | {"(1,2)","(2,1)"}         | f
      2 |     3 | {"(1,2)","(2,3)"}         | f
      3 |     1 | {"(1,2)","(3,1)"}         | f
      3 |     1 | {"(1,2)","(2,3)","(3,1)"} | f
      2 |     3 | {"(1,2)","(3,1)","(2,3)"} | f
(6 rows)

Edición n. ° 2: siguiendo lo sugerido por Erwin Brandstetter, modifiqué mi consulta, pero si no me equivoco, la consulta propuesta da MÁS filas que la mía (la comparación ROW sigue allí, ya que me parece más claro, incluso comprendí que la comparación de cadenas será más eficiente). Usando la nueva consulta, obtengo 20 filas, mientras que la mía da 6 filas

WITH RECURSIVE graph(parent, child, path, depth) AS (
SELECT o.parent, o.child, ARRAY[ROW(o.parent, o.child)], 0
    from ownership o
    where 1 in (o.child, o.parent)
UNION ALL
SELECT 
    o.parent, o.child,
    path||ROW(o.parent, o.child), 
    depth+1
    from 
        ownership o, graph g
    where 
        g.child in (o.parent, o.child) 
        and ROW(o.parent, o.child) <> ALL(path)

)
select  g.parent, g.child from graph g

Edición 3 : entonces, como señaló Erwin Brandstetter, la última consulta seguía siendo incorrecta, mientras que la correcta se puede encontrar en su respuesta.

Cuando publiqué mi primera consulta, no había entendido que me faltaban algunas combinaciones, como ocurre en el siguiente caso: si comienzo con el nodo 3, el db selecciona las filas (2,3) y (3,1) Luego, el primer paso inductivo de la consulta seleccionaría, uniendo desde estas filas, las filas (1,2) , (2,3) y (3,1) , faltando la fila (2,1) que debería incluirse en el resultado como conceptualmente el algoritmo implicaría ( (2,1) es "cercano" (3,1) )

Cuando traté de adaptar el ejemplo en el manual Postgresql, estaba tratando de unirme al padre y al hijo de la ownership , pero me equivoqué al no guardar el valor del graph que tenía que unir en cada paso.

Este tipo de consultas parece generar un conjunto diferente de filas dependiendo del nodo inicial (es decir, dependiendo del conjunto de filas seleccionadas en el paso base). Por lo tanto, creo que podría ser útil seleccionar solo una fila que contenga el nodo inicial en el paso base, ya que de todos modos obtendrá cualquier otro nodo "adyacente".

Answer 1

Podría funcionar así:

WITH RECURSIVE graph AS (
    SELECT parent
          ,child
          ,'','' || parent::text || '','' || child::text || '','' AS path
          ,0 AS depth
    FROM   ownership
    WHERE  parent = 1

    UNION ALL
    SELECT o.parent
          ,o.child
          ,g.path || o.child || '',''
          ,g.depth + 1
    FROM   graph g
    JOIN   ownership o ON o.parent = g.child
    WHERE  g.path !~~ (''%,'' || o.parent::text || '','' || o.child::text || '',%'')
    )
SELECT  *
FROM    graph

Mencionaste el rendimiento, así que optimicé en esa dirección.

Puntos principales:

• Recorre el gráfico solo en la dirección definida.

• Sin necesidad de un cycle columna, conviértalo en una condición de exclusión. Un paso menos por recorrer. Esa es también la respuesta directa a:

¿Cómo puedo hacer para detener los ciclos un paso antes del nodo que cierra el ciclo?

• Usa una cuerda para grabar la ruta. Más pequeño y más rápido que una matriz de filas. Todavía contiene toda la información necesaria. Sin embargo, podría cambiar con números bigint muy grandes.

• Compruebe si hay ciclos con el operador LIKE ( ~~ ), debe ser mucho más rápido.

• Si no espera más de 2147483647 filas en el transcurso del tiempo, use columnas de integer simples en lugar de bigint . Más pequeño y más rápido.

• Asegúrese de tener un índice en el parent . El índice en el child es irrelevante para mi consulta. (Excepto en su original donde atraviesa los bordes en ambas direcciones).

• Para gráficos enormes , cambiaría a un procedimiento plpgsql , donde puede mantener la ruta como tabla temporal con una fila por paso y un índice coincidente. Sin embargo, un poco de sobrecarga, que pagará con gráficos enormes.

Problemas en su consulta original:

WHERE (g.parent = o.child or g.child = o.parent) 

Solo hay un punto final de su recorrido en cualquier punto del proceso. A medida que dibuja el gráfico dirigido en ambas direcciones, el punto final puede ser padre o hijo, pero no ambos. Debe guardar el punto final de cada paso y luego:

WHERE g.child IN (o.parent, o.child) 

La violación de la dirección también hace cuestionable su condición inicial:

WHERE parent = 1

Tendría que ser

WHERE 1 IN (parent, child)

Y las dos filas (1,2) y (2,1) se duplican efectivamente de esta manera ...

Solución adicional después del comentario

• Ignorar dirección
• Aún caminar por cualquier borde solo una vez por camino.
• Usa ARRAY para el camino
• Guarde la dirección original en la ruta, no en la dirección real.

Tenga en cuenta que de esta forma (2,1) y (1,2) son duplicados efectivos, pero ambos se pueden usar en la misma ruta.

Presento la leaf columna que guarda el punto final real de cada paso.

WITH RECURSIVE graph AS (
    SELECT CASE WHEN parent = 1 THEN child ELSE parent END AS leaf
          ,ARRAY[ROW(parent, child)] AS path
          ,0 AS depth
    FROM   ownership
    WHERE  1 in (child, parent)

    UNION ALL
    SELECT CASE WHEN o.parent = g.leaf THEN o.child ELSE o.parent END -- AS leaf
          ,path || ROW(o.parent, o.child) -- AS path
          ,depth + 1 -- AS depth
    FROM   graph g
    JOIN   ownership o ON g.leaf in (o.parent, o.child) 
    AND    ROW(o.parent, o.child) <> ALL(path)
    )
SELECT *
FROM   graph