detección del ciclo con la factorización subconsulta recursiva
https://stackoverflow.com/questions/1731889
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Oracle SQL puede hacer consultas jerárquicas desde v2, usando su CONNECT patentada por la sintaxis. En su última versión 11g 2, agregaron factoring sub consulta recursiva, también conocido como el recursiva con la cláusula. Este es el estándar ANSI, y si he entendido bien, éste ha sido implementado por otros proveedores de RDBMS también.
Cuando se compara el Connect-By con el recursiva con, he notado una diferencia en el conjunto de resultados cuando se utiliza detección de ciclo. La conexión de los resultados son más intuitivo para mí, así que me pregunto si la implementación de Oracle contiene un error, o si este es un comportamiento esperado y ANSI estándar. Por lo tanto, mi pregunta es si se puede comprobar el recursiva con consulta utilizando otras bases de datos como MySQL, DB2, SQL Server y otros. Siempre que esas bases de datos apoyan la recursiva con la cláusula por supuesto.
Aquí es cómo 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 mediante CONNECT BY sintaxis:
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 parece intuitivo para mí. 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 utilizar para comprobar:
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;
Solución
A partir de la documentación de CONNECT_BY_ISCYCLE :
Los rendimientos
CONNECT_BY_ISCYCLEpseudocolumna1si la fila actual tiene un niño que es también su ancestro
y que en CYCLE :
Una fila se considera para formar un ciclo si uno de sus filas antepasado tiene los mismos valores para las columnas de ciclo.
En el ejemplo, la fila 2 tiene un niño que es también su antecesor, pero su id no ha regresado todavía.
En otras palabras, CONNECT_BY_ISCYCLE comprueba los niños (que son aún para ser devueltos), mientras que CYCLE comprueba el fila actual (que ya se devuelve).
CONNECT BY se basa fila, mientras que CTE recursivas se establecen a base de.
Tenga en cuenta que la documentación de Oracle en CYCLE menciona una "fila ancestro". Sin embargo, en términos generales, no existe el concepto de una "fila ancestro" en un CTE recursiva. Es una operación basada en conjunto que puede dar resultados completamente fuera del árbol. En términos generales, la parte de anclaje y la parte recursiva pueden incluso utilizar las diferentes tablas.
Desde CTE de recursivos son general se utiliza para construir árboles de jerarquía, Oracle decidió añadir un cheque ciclo. Sin embargo, debido al modo basado en conjuntos de operan los CTE recursivas, por lo general es imposible decir será el siguiente paso de generar un ciclo o no, ya que sin una clara definición de la condición del ciclo "fila ancestro" no se puede definir bien.
Para realizar la etapa de "siguiente", todo el conjunto "actual" tiene que estar disponible, pero para generar cada fila del conjunto actual (que incluye la columna ciclo) que sólo tiene que tener los resultados de la "próxima" operación.
No es un problema si el conjunto actual consiste siempre en una sola fila (como en CONNECT BY), pero es un problema si la operación recursiva definida en un conjunto como un todo.
No se veía en Oracle 11 todavía, pero SQL Server implementa recursivas de CTE con sólo esconde un CONNECT BY detrás de ellos, lo que requiere la colocación de numerosas restricciones (todos los cuales prohibir efectivamente todas las operaciones basadas en conjuntos).
aplicación de PostgreSQL, por otro lado, se establece-basan con verdad que puede hacer cualquier operación con la parte de anclaje en la parte recursiva. Que no tiene ningún medio para detectar ciclos, sin embargo, ya que los ciclos no se definen en el primer lugar.
Como se mencionó antes, MySQL no implementa de CTE en absoluto (no implementa de HASH JOIN o MERGE JOINs así, sólo los bucles anidados, por lo que no se sorprenda mucho).
Irónicamente, he recibido hoy una carta sobre este mismo tema, que voy a cubrir en mi blog.
Actualización:
CTE recursivas de en SQL Server no son más que CONNECT BY disfrazada. Lee este artículo en mi blog para más detalles impactantes:
Otros consejos
PostgreSQL soporta CON estilo consultas jerárquicas, pero no tiene ninguna detección de ciclo automático. Esto significa que usted necesita para escribir su propia y el número de filas devueltas depende de la forma que especifique condiciones de combinación en la parte recursiva de la consulta.
Ambos ejemplos utilizan una matriz si IDs (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
Que yo sepa:
- MySQL no soporta recursiva del CTE
- SQL Sever no soporta ciclo detección en recursivo de CTE
MySQL Server versión 5.0.45 no le gustaba with:
ERROR 1064 (42000): Usted tiene un error en su sintaxis SQL; comprobar el manual que corresponde a su versión del servidor MySQL para la derecha sintaxis para usar cerca de 'con tr (id, parent_id) como (SELECT ID, parent_id de t donde id = 1 union todo s'en la línea 1.
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 es mejor esta condición d.slave = ANY(all_ids)
Los resultados del conecten puede no ser siempre intuitiva.
A continuación consultas demuestran diferentes enfoques para detectar ciclos de arranque 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.
Nodo con id = 3 tiene dos padres para Oracle atraviesa dos ciclos en este ejemplo.
(1, 3) -> (3, 4) -> (4, 5) -> (5, 3)
y
(5, 3) -> (3, 4) -> (4, 5)
Edge (5, 3) falta en el resultado de la primera consulta y primer ciclo. Al mismo tiempo el borde (5, 3) aparece en el resultado para la tercera consulta y segundo ciclo de dos veces.
¿Por qué? Puede comprobar descripción de la lógica de detección de ciclo de la respuesta proporcionada por Quassnoi. En la llanura Inglés significa que
(1) conectar por detecta un ciclo si ID niño por la línea actual es parte de IDs visitado hasta ahora
(2) de grabación con detecta un ciclo si ID de fila actual es parte de IDs visitado hasta ahora
Resultado de la segunda consulta es la más natural, aunque hay and prior id_parent is not null predicado adicional. En este caso
(3) detecta un ciclo si ID de la línea actual es parte de ID de matriz visitado hasta ahora
Todas estas condiciones se aplican en columnas CNT1, CNT2, en CNT3 por debajo de 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 el filtro uncomment por CNT1 / CNT2 / CNT3 y quitar "ciclo de ciclo de Identificación del conjunto a 1 por defecto 0", entonces consulta devolverá resultado que la consulta correspondiente anteriormente. En otras palabras usted puede evitar cycle clause y implementar la lógica de detección de ciclo a encontrar más intuitivo .
Los detalles adicionales sobre atraviesan las jerarquías y la detección de ciclo se pueden encontrar en el libro Oracle SQL Revelado .
