sql - tipos - Detección de ciclos con factorización de subconsultas recursivas.

subconsultas sql ejercicios resueltos

Question

Oracle SQL puede hacer consultas jerárquicas desde v2, usando su propia sintaxis CONNECT BY. En su última versión 11g 2, agregaron la factorización de subconsulta recursiva, también conocida como la cláusula recursiva con. Este es el estándar ANSI, y si lo entiendo correctamente, este también ha sido implementado por otros proveedores de RDBMS.

Al comparar la conexión con el recursivo, noté una diferencia en el conjunto de resultados al usar la detección de ciclos. La conexión por resultados es más intuitiva para mí, así que me pregunto si la implementación de Oracle contiene un error o si se trata de un ANSI estándar y el comportamiento esperado. Por lo tanto, mi pregunta es si puede verificar el recursivo con la consulta utilizando otras bases de datos como MySQL, DB2, SQL Server y otras. Siempre que las bases de datos sean compatibles con la cláusula recursiva, por supuesto.

Así es como funciona en Oracle 11.2.0.1.0

SQL> select *
2 from t
3 /
ID PARENT_ID
---------- ----------
1 2
2 1
2 rows selected.

La consulta utilizando la sintaxis de CONNECT BY:

SQL> select id
2 , parent_id
3 , connect_by_iscycle
4 from t
5 connect by nocycle parent_id = prior id
6 start with id = 1
7 /
ID PARENT_ID CONNECT_BY_ISCYCLE
---------- ---------- ------------------
1 2 0
2 1 1
2 rows selected.

Lo que me parece intuitivo. Sin embargo, usando la nueva sintaxis ANSI, devuelve una fila más:

SQL> with tr (id,parent_id) as
2 ( select id
3 , parent_id
4 from t
5 where id = 1
6 union all
7 select t.id
8 , t.parent_id
9 from t
10 join tr on t.parent_id = tr.id
11 ) cycle id set is_cycle to ''1'' default ''0''
12 select id
13 , parent_id
14 , is_cycle
15 from tr
16 /
ID PARENT_ID I
---------- ---------- -
1 2 0
2 1 0
1 2 1
3 rows selected.

Este es el script que puede usar para verificar:

create table t
( id number
, parent_id number
);
insert into t values (1, 2);
insert into t values (2, 1);
commit;
with tr (id,parent_id) as
( select id
, parent_id
from t
where id = 1
union all
select t.id
, t.parent_id
from t
join tr on t.parent_id = tr.id
) cycle id set is_cycle to ''1'' default ''0''
select id
, parent_id
, is_cycle
from tr;

Answer 1

De la documentación en CONNECT_BY_ISCYCLE :

La pseudocolumna CONNECT_BY_ISCYCLE devuelve 1 si la fila actual tiene un hijo que también es su antecesor

y que en CYCLE :

Se considera que una fila forma un ciclo si una de sus filas de ancestro tiene los mismos valores para las columnas del ciclo.

En su ejemplo, la fila 2 tiene un hijo que también es su antecesor, pero su id no se ha devuelto todavía.

En otras palabras, CONNECT_BY_ISCYCLE comprueba los hijos (que aún no se han devuelto), mientras que CYCLE comprueba la fila actual (que ya se ha devuelto).

CONNECT BY se basa en filas, mientras que los CTE recursivos se basan en conjuntos.

No hay concepto de "niño" en un CTE recursivo. Es una operación basada en un conjunto que puede producir resultados completamente fuera del árbol. En términos generales, la parte de anclaje y la parte recursiva pueden incluso utilizar las diferentes tablas.

Dado que los CTE recursivos generalmente se usan para construir árboles de jerarquía, Oracle decidió agregar una verificación de ciclo. Pero debido a la manera en que los CTE recursivos funcionan de manera basada en conjuntos, generalmente es imposible saber si el siguiente paso generará un ciclo o no.

Para realizar el "siguiente" paso, todo el conjunto "actual" debe estar disponible, pero para generar cada fila del conjunto actual (que incluye la columna de ciclo) solo necesitamos tener los resultados de la siguiente operación. No es un problema con una sola fila (como en CONNECT BY ), pero es un problema con un conjunto como un todo.

Todavía no examiné Oracle 11 , pero SQL Server implementa los CTE recursivos simplemente ocultando un CONNECT BY detrás de ellos, lo que requiere colocar numerosas restricciones (todas las cuales prohíben efectivamente todas las operaciones basadas en conjuntos).

La implementación de PostgreSQL , por otro lado, está realmente basada en conjuntos.

Como se mencionó anteriormente, MySQL no implementa CTE en absoluto (no implementa HASH JOIN o MERGE JOIN también, solo los bucles anidados, así que no se sorprenda mucho).

Irónicamente, hoy recibí una carta sobre este tema, que cubriré en mi blog.

Actualizar:

Los CTE recursivos en SQL Server no son más que CONNECT BY disfrazados. Ver este artículo en mi blog para detalles impactantes:

• SQL Server: ¿los CTE recursivos están realmente basados ​​en conjuntos?

Answer 2

HASTA DONDE SE:

• MySQL no soporta CTE recursivos
• SQL Sever no admite la detección de ciclos en CTE recursivos

Answer 3

Los resultados de la conexión pueden no ser siempre intuitivos.

Las siguientes consultas muestran diferentes enfoques para detectar ciclos que comienzan con id = 3 para el gráfico en la imagen.

create table graph (id, id_parent) as
(select 2, 1 from dual
union all select 3, 1 from dual
union all select 4, 3 from dual
union all select 5, 4 from dual
union all select 3, 5 from dual)

SQL> select level lvl, graph.*, connect_by_iscycle cycle
2 from graph
3 start with id = 3
4 connect by nocycle prior id = id_parent;
LVL ID ID_PARENT CYCLE
---------- ---------- ---------- ----------
1 3 1 0
2 4 3 0
3 5 4 1
1 3 5 0
2 4 3 0
3 5 4 1
6 rows selected.
SQL> select level lvl, graph.*, connect_by_iscycle cycle
2 from graph
3 start with id = 3
4 connect by nocycle prior id = id_parent
5 and prior id_parent is not null;
LVL ID ID_PARENT CYCLE
---------- ---------- ---------- ----------
1 3 1 0
2 4 3 0
3 5 4 0
4 3 5 1
1 3 5 0
2 4 3 0
3 5 4 1
7 rows selected.
SQL> with t(id, id_parent) as
2 (select *
3 from graph
4 where id = 3
5 union all
6 select g.id, g.id_parent
7 from t
8 join graph g
9 on t.id = g.id_parent)
10 search depth first by id set ord
11 cycle id set cycle to 1 default 0
12 select * from t;
ID ID_PARENT ORD C
---------- ---------- ---------- -
3 1 1 0
4 3 2 0
5 4 3 0
3 5 4 1
3 5 5 0
4 3 6 0
5 4 7 0
3 5 8 1
8 rows selected.

El nodo con id = 3 tiene dos padres, por lo que Oracle atraviesa dos ciclos en este ejemplo.

(1, 3) -> (3, 4) -> (4, 5) -> (5, 3)

y

(5, 3) -> (3, 4) -> (4, 5)

Falta el borde (5, 3) del resultado de la primera consulta y el primer ciclo. Al mismo tiempo, el borde (5, 3) aparece en el resultado de la tercera consulta y el segundo ciclo dos veces.

¿Porque? Puede consultar la descripción de la lógica de detección de ciclo en la respuesta provista por Quassnoi. En inglés sencillo significa que

(1) connect by detecta un ciclo si la ID del niño para la fila actual es parte de las ID visitadas hasta ahora

(2) rec with detecta un ciclo si la ID de la fila actual es parte de las ID visitadas hasta ahora

El resultado de la segunda consulta parece el más natural, aunque hay un predicado adicional and prior id_parent is not null . En este caso

(3) detecta un ciclo si la ID de la fila actual es parte de las ID principales visitadas hasta ahora

Todas estas condiciones se implementan en las columnas cnt1, cnt2, cnt3 en la siguiente consulta.

SQL> with t(id, id_parent, path_id, path_id_parent, cnt1, cnt2, cnt3) as
2 (select g.*,
3 cast(''->'' || g.id as varchar2(4000)),
4 cast(''->'' || g.id_parent as varchar2(4000)),
5 0,
6 0,
7 0
8 from graph g
9 where id = 3
10 union all
11 select g.id,
12 g.id_parent,
13 t.path_id || ''->'' || g.id,
14 t.path_id_parent || ''->'' || g.id_parent,
15 regexp_count(t.path_id || ''->'', ''->'' ||
16 (select id from graph c where c.id_parent = g.id) || ''->''),
17 regexp_count(t.path_id || ''->'', ''->'' || g.id || ''->''),
18 regexp_count(t.path_id_parent || ''->'', ''->'' || g.id || ''->'')
19 from t
20 join graph g
21 on t.id = g.id_parent
22 -- and t.cnt1 = 0
23 -- and t.cnt2 = 0
24 -- and t.cnt3 = 0
25 )
26 search depth first by id set ord
27 cycle id set cycle to 1 default 0
28 select * from t;
ID ID_PARENT PATH_ID PATH_ID_PARENT CNT1 CNT2 CNT3 ORD C
---------- ---------- --------------- --------------- ---- ---- ---- ---------- -
3 1 ->3 ->1 0 0 0 1 0
4 3 ->3->4 ->1->3 0 0 0 2 0
5 4 ->3->4->5 ->1->3->4 1 0 0 3 0
3 5 ->3->4->5->3 ->1->3->4->5 1 1 1 4 1
3 5 ->3 ->5 0 0 0 5 0
4 3 ->3->4 ->5->3 0 0 0 6 0
5 4 ->3->4->5 ->5->3->4 1 0 1 7 0
3 5 ->3->4->5->3 ->5->3->4->5 1 1 1 8 1
8 rows selected.

Si elimina los comentarios de cnt1 / cnt2 / cnt3 y elimina "cycle id set cycle a 1 default 0", la consulta devolverá el resultado como la consulta correspondiente arriba. En otras palabras , puede evitar la cycle clause e implementar cualquier lógica de detección de ciclo que encuentre más intuitiva .

Se pueden encontrar detalles adicionales sobre las jerarquías de desplazamiento y la detección de ciclos en el libro Oracle SQL Revealed .

Answer 4

MySQL Server versión 5.0.45 no me gustó with :

ERROR 1064 (42000): Tiene un error en su sintaxis SQL; revise el manual que corresponde a la versión de su servidor MySQL para conocer la sintaxis correcta para usar near ''with tr (id, parent_id) as (seleccione id, parent_id de t donde id = 1 union all s'' en la línea 1.

Answer 5

PostgreSQL admite consultas jerárquicas de estilo CON, pero no tiene detección automática de ciclos. Esto significa que debe escribir el suyo propio y el número de filas devueltas depende de la forma en que especifique las condiciones de unión en la parte recursiva de la consulta.

Ambos ejemplos usan una matriz si los ID (llamados all_ids) para detectar bucles:

WITH recursive tr (id, parent_id, all_ids, cycle) AS (
SELECT id, parent_id, ARRAY[id], false
FROM t
WHERE id = 1
UNION ALL
SELECT t.id, t.parent_id, all_ids || t.id, t.id = ANY(all_ids)
FROM t
JOIN tr ON t.parent_id = tr.id AND NOT cycle)
SELECT id, parent_id, cycle
FROM tr;
id | parent_id | cycle
----+-----------+-------
1 | 2 | f
2 | 1 | f
1 | 2 | t
WITH recursive tr (id, parent_id, all_ids, cycle) AS (
SELECT id, parent_id, ARRAY[id], false
FROM t
WHERE id = 1
UNION ALL
SELECT t.id, t.parent_id, all_ids || t.id, (EXISTS(SELECT 1 FROM t AS x WHERE x.id = t.parent_id))
FROM t
JOIN tr ON t.parent_id = tr.id
WHERE NOT t.id = ANY(all_ids))
SELECT id, parent_id, cycle
FROM tr;
id | parent_id | cycle
----+-----------+-------
1 | 2 | f
2 | 1 | t

Answer 6

WITH RECURSIVE s (master, slave, all_ids, cycle) AS
(
SELECT master, slave, ARRAY[master], false FROM binding WHERE master=3477
UNION ALL
SELECT d.master, d.slave, all_ids || d.master, d.slave = ANY(all_ids)
FROM
binding AS d
JOIN
s
ON (d.master = s.slave)
WHERE NOT d.master = ANY(all_ids)
)
SELECT *
FROM s;

Creo que mejor es esta condición d.slave = ANY(all_ids)