sql - recursivo - Visitar un gráfico dirigido como si fuera uno no dirigido, utilizando una consulta recursiva
recursividad en mysql (1)
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".
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
cyclecolumna, 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
bigintmuy 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
integersimples en lugar debigint. Más pequeño y más rápido.Asegúrese de tener un índice en el
parent. El índice en elchildes 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