Consulta jerárquica de Oracle en datos no jerárquicos

Question

Tengo datos en una tabla de Oracle organizada como un gráfico que puede contener ciclos (ver ejemplo).

 CREATE TABLE T (parent INTEGER, child INTEGER) 
       AS select 1 parent, 2 child from dual 
     union all select 1 parent, 8 child from dual 
     union all select 2 parent, 3 child from dual 
     union all select 2 parent, 4 child from dual 
     union all select 2 parent, 8 child from dual 
     union all select 3 parent, 4 child from dual 
     union all select 3 parent, 6 child from dual 
     union all select 4 parent, 5 child from dual 
     union all select 5 parent, 8 child from dual 
     union all select 6 parent, 5 child from dual 
     union all select 7 parent, 3 child from dual 
     union all select 7 parent, 5 child from dual 
     union all select 8 parent, 6 child from dual 

Mi objetivo es conseguir todos los nodos que son descendientes (hijos, hijos de los hijos, etc.) del nodo X. Digamos 2. Mi resultado esperado es entonces: 3, 4, 5, 6, 8.

Sé que puedo diseñar una consulta como esta:

SELECT child, sys_connect_by_path(child,'/') 
    FROM T 
    START WITH parent = 2 
CONNECT BY NOCYCLE PRIOR child = PARENT; 

El problema con este tipo de consulta es que va a ir a través de todos los caminos posibles hasta que completen el ciclo, y hay demasiados de ellos en mis datos reales. El resultado consiste en muchos duplicados - Aquí está:

child | sys_connect_by_path (for information) 
3  | /3 
4  | /3/4 
5  | /3/4/5 
8  | /3/4/5/8 
6  | /3/4/5/8/6 
6  | /3/6 
5  | /3/6/5 
8  | /3/6/5/8 
4  | /4 
5  | /4/5 
8  | /4/5/8 
6  | /4/5/8/6 
8  | /8 
6  | /8/6 
5  | /8/6/5 

Mis datos reales son mucho más complejos. el costo de ejecución de tal consulta es tan grande que mi tablespace TEMP, que era autoextendable, alcanzó 10Gb (originalmente 500 Mb) y mi base de datos se rompió debido a que el disco estaba lleno.

Me trataron de diseñar la consulta como la siguiente (recursiva con un cláusula):

WITH descendants(node) AS 
(SELECT 2 node FROM dual 
    UNION ALL 
    (
    SELECT child 
    FROM T 
    INNER JOIN descendants D 
     ON T.parent = D.node 
    MINUS SELECT node FROM descendants 
) 
) 
SELECT * FROM descendants 

El problema que encuentro es:

• con Oracle 10g, esto no se lleva a cabo (ORA-32033: unsupported column aliasing, y algunos clientes usan Oracle 9 o 10),
• con Oracle 11g, obtengo ORA-32041: UNION ALL operation in recursive WITH clause must have only two branches. Si elimino la cláusula MINUS obtendré ciclos (ORA-32044: cycle detected while executing recursive WITH query).

¿Cómo consultaría mis datos originales para obtener esos nodos 3, 4, 5, 6, 8 de manera eficiente? Las soluciones PL/SQL también son bienvenidas.

Gracias.

Answer 1

¿Cuál es su profundidad máxima esperada para llegar a cualquier nodo hijo?

Si es relativamente pequeño, podría bucle hacia abajo, mientras que la comprobación de los nodos que ya ha visitado, de una manera algo como esto ...

(Nota, no soy un experto de Oracle por lo que este está más cerca a pseudo código con un poco de SQL reales mezclados)

CREATE TABLE myMap (parent INT, child INT); 

INSERT INTO myTable SELECT NULL, 2 FROM DUAL; 

WHILE (SQL%ROWCOUNT > 0) 
LOOP 

    INSERT INTO 
    myMap 
    SELECT DISTINCT 
    dataMap.parent, 
    dataMap.child 
    FROM 
    myMap 
    INNER JOIN 
    dataMap 
     ON myMap.child = dataMap.parent 
    WHERE 
    NOT EXISTS (SELECT * FROM myMap WHERE parent = dataMap.parent) 

END LOOP; 

en función del rendimiento, también puede querer un campo depth en myMap; optimizando la unión para que solo se una a los nodos más recientes. Esto implicaría dos índices; uno para el JOIN (depth) y el otro para el NO EXISTE (parent).

EDITAR

añadido la palabra clave DISTINCT, para evitar el siguiente caso ...
- Nodo 2 mapas a 3 y 4
- Los nodos 3 y 4, tanto el mapa al nodo 5
- Todos los hijos del nodo 5 ahora se procesan dos veces

GROUP BY, o muchas otras opciones, se puede utilizar para atender esto en lugar de DISTINCT. Es solo que lo que NO EXISTE por sí solo no es suficiente.

Answer 2

No he trabajado con esto yo mismo, pero ¿qué pasa con un CONNECT BY con la opción NOCYCLE? Eso debería dejar de atravesar el árbol cuando ve un bucle. Oracle 11i definitivamente tiene eso, creo que llegó en algún momento del período Oracle 10g.

Answer 3

Esto podría ayudar hasta que se exceda 4000 bytes visitados. Los ciclos no deberían ser posibles, pero la línea está allí solo como un ejemplo.

WITH descendants(node, lvl, pth, visited) AS 
    (
    SELECT child node, 1, cast(child as varchar2(4000)), '/'||listagg(child,'/') within group (order by child) over()||'/' 
     FROM t 
    where parent = 2 
    UNION ALL 
    SELECT child, lvl+1, pth||'/'||child, D.visited||listagg(child,'/') within group (order by child) over()||'/' 
     FROM T 
    INNER JOIN descendants D 
     ON T.parent = D.node 
    WHERE D.visited not like '%/'||child||'/%' 
    ) 
    cycle node set cyc to '1' default '0' 
    SELECT distinct node 
     FROM descendants 
    order by node 
    ;