Query gerarchica Oracle su dati non gerarchici

Question

Ho dati in una tabella Oracle organizzata come un grafico che può contenere cicli (vedere esempio).

 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 

Il mio obiettivo è quello di ottenere tutti i nodi che sono discendenti (figli, figli dei figli, etc.) di nodo X. Diciamo 2. Il mio risultato atteso è quindi: 3, 4, 5, 6, 8.

So che posso progettare una query come questa:

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

Il problema con una tale domanda è che si passerà attraverso tutti i possibili percorsi fino a quando non ciclano, e ce ne sono troppi nei miei dati reali. Il risultato è costituito da molti duplicati - Eccolo:

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 

miei dati reale è molto più complessa. il costo dell'esecuzione di una tale query è così grande che il mio tablespace TEMP, che era autoextendable, ha raggiunto 10Gb (originariamente 500 Mb) e il mio database in realtà si è rotto a causa del disco pieno.

ho cercato di progettare la query come questo (ricorsiva con un clausola):

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 

Il problema che ho incontrato è:

• con Oracle 10g, questo non è implementato (ORA-32033: unsupported column aliasing, e alcuni clienti utilizzano Oracle 9 o 10),
• con Oracle 11g, ottengo ORA-32041: UNION ALL operation in recursive WITH clause must have only two branches. Se rimuovo la clausola MINUS riceverò i cicli (ORA-32044: cycle detected while executing recursive WITH query).

In che modo interrogheresti i miei dati originali per ottenere quei nodi 3, 4, 5, 6, 8 in modo efficiente? Anche le soluzioni PL/SQL sono benvenute.

Grazie.

Answer 1

Qual è la profondità massima prevista per raggiungere qualsiasi nodo figlio?

Se è relativamente piccolo, si potrebbe ciclo verso il basso, mentre si verifica per i nodi che hai già visitato, in un qualcosa di maniera simile ...

(Nota, io non sono un esperto Oracle quindi questo è più vicino a pseudo codice con un po 'di SQL vera mescolato)

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; 

a seconda delle prestazioni, si potrebbe anche voler un campo depth in myMap; ottimizzando il join in modo da unire solo i nodi più recenti. Ciò implicherebbe due indici; uno per il JOIN (depth) e uno per il NOT EXISTS (parent).

EDIT

Aggiunto la parola chiave DISTINCT, per evitare il seguente caso ...
- Nodo 2 mappe a 3 e 4
- nodi 3 e 4 sia mappa al nodo 5
- Tutti i figli del nodo 5 ora sarebbero processati due volte

GROUP BY, o molte altre opzioni, può essere utilizzato per soddisfare questo invece di DISTINCT. È solo che il NON ESISTE da solo non è sufficiente.

Answer 2

Non ho ancora lavorato con questo, ma per quanto riguarda un CONNECT BY con l'opzione NOCYCLE? Questo dovrebbe smettere di attraversare l'albero quando vede un loop. Oracle 11i lo ha sicuramente, penso che sia arrivato da qualche parte nel periodo Oracle 10g.

Answer 3

Questo potrebbe aiutare fino a quando visitato supera i 4000 byte. I cicli non dovrebbero essere possibili ma la linea è lì solo a titolo di esempio.

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 
    ;