Requête hiérarchique Oracle sur des données non hiérarchiques

Question

J'ai des données dans une table Oracle organisée sous la forme d'un graphique pouvant contenir des cycles (voir l'exemple).

 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 

Mon but est d'obtenir tous les nœuds qui sont des descendants (enfants, enfants d'enfants, etc.) du noeud X. Disons que 2. Mon résultat attendu est alors: 3, 4, 5, 6, 8.

Je sais que je peux concevoir une requête comme ceci:

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

Le problème avec une telle requête est qu'elle traversera tous les chemins possibles jusqu'à leur cycle, et il y en a trop dans mes données actuelles. Le résultat se compose de nombreux doublons - Ici, il 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 

Mes données réelles est beaucoup plus complexe. le coût d'exécution d'une telle requête est si énorme que mon espace de table TEMP, qui était autoextendable, a atteint 10 Go (à l'origine 500 Mo) et ma base de données s'est cassée à cause du disque plein.

J'ai essayé de concevoir la requête comme celui-ci (récursif clause):

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 

Le problème que je rencontre est:

• avec Oracle 10g, ce ne sont pas mis en œuvre (ORA-32033: unsupported column aliasing et certains clients utilisent Oracle 9 ou 10),
• avec Oracle 11g, j'obtiens ORA-32041: UNION ALL operation in recursive WITH clause must have only two branches. Si je supprime la clause MINUS, j'obtiendrai des cycles (ORA-32044: cycle detected while executing recursive WITH query).

Comment voulez-vous interroger mes données d'origine pour obtenir les nœuds 3, 4, 5, 6, 8 efficacement? Les solutions PL/SQL sont également les bienvenues.

Merci.

Answer 1

Quelle est votre profondeur maximale prévue pour atteindre un nœud enfant?

Si elle est relativement faible, vous pourriez créer une boucle vers le bas, tout en vérifiant pour les noeuds que vous avez déjà visité, dans une manière quelque chose comme ça ...

(Note, je ne suis pas un expert Oracle si c'est plus proche au code pseudo avec un peu réel SQL mélangé)

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 fonction de la performance, vous pouvez également un champ depth dans myMap; optimiser la jointure pour ne joindre que les nœuds les plus récents. Cela impliquerait deux index; un pour le JOIN (depth) et un pour les NOT EXISTS (parent).

EDIT

Ajouté le mot clé DISTINCT, pour éviter le cas suivant ...
- Noeud 2 cartes à 3 et 4
- Les nœuds 3 et 4 fois carte au noeud 5
- Tous les enfants du nœud 5 seraient désormais traitées deux fois

GROUP BY, ou bien d'autres options, il peut être utilisé pour répondre à cela au lieu de DISTINCT. C'est juste que le NOT EXISTS n'est pas suffisant.

Answer 2

Je n'ai pas travaillé avec moi-même, mais qu'en est-il d'un CONNECT BY avec l'option NOCYCLE? Cela devrait arrêter de traverer l'arbre quand il voit une boucle. Oracle 11i a certainement cela, je pense qu'il est venu quelque part dans la période Oracle 10g.

Answer 3

Cela peut aider jusqu'à ce que visité dépasse 4000 octets. Les cycles ne devraient pas être possibles mais la ligne est là juste à titre d'exemple.

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 
    ;