Retrouver des relations circulaires

Bonjour :),

Je souhaites optimiser une requete, j'ai une table que l'on va appeler table1, avec 2 champs "parent_item" et "subordinate_item" qui réprésente donc un item parent et un subordonné. Je souhaite vérifier qu'il n'y a pas de relation circulaire dans ma table.
Exemple :
Ligne 1 : parent_item = 1, subordinate_item = 2
Ligne 2 : parent_item = 2, subordinate_item = 3
Ligne 3 : parent_item = 3, subordinate_item = 1

Donc ici on a une relation circulaire. Bien sur ma table réelle est bien plus grosse et si je vérifie ligne par ligne sans optimisation ma requete prends environ 30 minutes. Existe-t-il des outils pour optimiser ce genre de recherche?

Merci d'avance ! :D

k8

Bonjour :)

As tu des contraintes de perfs ? Parceque si tu dois le lancer une seule fois, 30 min est peut-être acceptable.

Sinon une approche en théorie des graphes est à prévoir, Peut-on savoir si ta table n'est qu'un seul graphe (toutes les lignes de la table sont liées entre elles) ? As-tu un arrêt ( subordinate_item a null )

Pour un graphe voici comment détecter un cycle :


http://fr.wikipedia.org/wiki/Algorit...ue#Pseudo-code

Si tu as plusieurs graphes il va te falloir l'itérer sur chaque élément qui n'a pas été parcouru dans un cycle précedent (donc sauvegarder les éléments parcourus).

Merci pour ta réponse rapide :king:.

Alors oui j'ai de très grosse contrainte de perf, je doit passer en dessous des 3 minutes si possible !

Sinon ma table possède beaucoup de graph différents, en général les lignes ne sont liés que par groupe de 3 ou 4. Et je n'ai aucun arret, c'est a dire que pour vérifier qu'un subordinate n'a pas lui meme un subordinate on doit vérifier qu'il n'apparait jamais dans le champ parent.

Sinon j'ai regardé les algorythmes que tu m'a donné, je t'avoues que c'est un peu compliqué pour moi 8O, je recherche plus une fonction oracle qui pourrait répondre a ce besoin.

Merci beaucoup :D

Il faut le faire en une seule requête, c'est bcp plus rapide.

Si tu ne cherchais que les relations circulaire sur deux niveaux, la requête de détection serait celle-ci :

Code:

---

1 2 3 4 5

SELECT * FROM table1 E -- enfants INNER JOIN table1 P -- parents ON E.parent_item = P.subordinate_item WHERE P.parent_item = E.subordinate_item

---

Sur trois niveaux, ça donne :

Code:

---

1 2 3 4 5 6 7

SELECT * FROM table1 E -- enfants INNER JOIN table1 P -- parents ON E.parent_item = P.subordinate_item INNER JOIN table1 GP -- grand-parents ON P.parent_item = GP.subordinate_item WHERE GP.parent_item = E.subordinate_item

---

et ainsi de suite. Pour le faire sur n niveaux, je pense que tu dois pouvoir utiliser une CTE récursive. Voir le papier de SQLpro à ce sujet : http://sqlpro.developpez.com/cours/s...te-recursives/

Je connaissais pas le concept de requête récursive, ça à l'air sympas :)

Il y'en a une présentation pour oracle ici

Sinon dans le cas de références cycliques, quelle est la clause d'arrêt de la récursivité ? Elle ne risque pas de tourner à l'infini ?

Citation:

---

Envoyé par Antoun

Pour le faire sur n niveaux, je pense que tu dois pouvoir utiliser une CTE récursive. Voir le papier de SQLpro à ce sujet : http://sqlpro.developpez.com/cours/s...te-recursives/

---

J'ai déjà essayé les CTE récursives de SQLPro sous Oracle 11g mais je n'ai pas obtenu de résultat, Oracle m'a refusé l'alias à l'intérieur du With.
Avez-vous pu y parvenir ?

Merci a tous pour toutes ces réponses !!! :king:

J'ai regardé pour la CTE, deja premiere chose je suis sur oracle 10g, cela ne pose pas de probleme?
Ensuite mon probleme est a n niveau c'est a dire que lorsque je vois qu'un item possede un fils je en peux pas savoir si sont fils aura lui meme 0 ou n fils.
Mais je ne vois pas comment l'utilisation de "with as" pourrait résoudre mon probleme. Comment faire par ce moyen pour vérifier que aucun fils n'est circulaire?

Sinon j'ai également regardé le solution envoyé par Delwyn, mais elle requiere une architecture spécifique que je ne peux malheureusement pas implémenter.

Merci !

k8

Oracle 10g permet les CTE récursives, comme l'indique la FAQ de Xo citée par Delwyn.

Peux-tu poster le code de création de tes tables et un extrait de données ?

Bonjour,

Je n'ai pas le droit de donner mes codes de creation de table je suis désolé :?, en revanche voici un exemple qui reconstitue exactement mon cas (en très simplifié bien sur)

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

create table table1 ( Parent_id NUMBER(2), Subordinate_id NUMBER(2) ); insert into table1 values (1,2); insert into table1 values (2,3); insert into table1 values (3,4); insert into table1 values (5,4); insert into table1 values (4,2); insert into table1 values (6,7); insert into table1 values (7,8); insert into table1 values (9,10); insert into table1 values (11,7); commit;

---

Voici le schéma des relations qui sont définis ci dessus (en rouge la relation circulaire):
1 --> 2 --> 3 --> 4 --> 2
5 --> 4

6 --> 7 --> 8
11--> 7

9 --> 10

Voila,
Merci ! :D

Citation:

---

Envoyé par bankette

Bonjour,

Je n'ai pas le droit de donner mes codes de creation de table je suis désolé :?, en revanche voici un exemple qui reconstitue exactement mon cas (en très simplifié bien sur)

---

Ça me suffira ! J'essaie de faire qqch ce midi.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

select distinct subordinate_id from table1 where connect_by_iscycle = 1 connect by nocycle parent_id=prior subordinate_id ;   SUBORDINATE_ID -------------- 2 3 4

---

rah ! un jour il faudra vraiment que je comprenne ce que fait ce foutu CONNECT BY !

:applo:

Super c'est exactement ce qu'il me fallait un grand merci !!! :king:

Après test je suis a moins de 5 secondes pour executer le script !!! Super !!

Merci tout le monde

Citation:

---

Envoyé par Antoun

Oracle 10g permet les CTE récursives, comme l'indique la FAQ de Xo citée par Delwyn.

Peux-tu poster le code de création de tes tables et un extrait de données ?

---

Je pense qu'il y a un problème de vocabulaire.
Oracle gère les requêtes récursives depuis au moins la version 7 (1996 ?) avec START WITH CONNECT BY (c'est ce qui est décrit dans l'article de Xo).

Les CTE (Common Table Expression) sont ces vues qu'on adresse avant un select avec le mot clef WITH.

Mon propos était de faire fonctionner les CTE récursives décritent dans le papier de SQLPro avec Oracle, et pour ma part n'ayant pas réussi, je me demandais si c'était votre cas.

Récursivité Oracle : OUI
CTE Oracle : OUI
CTE récursive Oracle : NON (mais j'ai très bien pu commettre des erreurs)

Citation:

---

Envoyé par Waldar

Je pense qu'il y a un problème de vocabulaire.
Oracle gère les requêtes récursives depuis au moins la version 7 (1996 ?) avec START WITH CONNECT BY (c'est ce qui est décrit dans l'article de Xo).

Les CTE (Common Table Expression) sont ces vues qu'on adresse avant un select avec le mot clef WITH.

Mon propos était de faire fonctionner les CTE récursives décritent dans le papier de SQLPro avec Oracle, et pour ma part n'ayant pas réussi, je me demandais si c'était votre cas.

Récursivité Oracle : OUI
CTE Oracle : OUI
CTE récursive Oracle : NON (mais j'ai très bien pu commettre des erreurs)

---

euh... je n'ai absolument rien compris, mais ça doit être dû au fait que je n'ai jamais eu l'occasion de tester les CTE récursives.

Citation:

---

Envoyé par Waldar

Je pense qu'il y a un problème de vocabulaire.
Oracle gère les requêtes récursives depuis au moins la version 7 (1996 ?)

---

pour être précis, CONNECT BY a été introduit dans Oracle 2, avant 1980 donc... avant COMMIT, avant PRIMARY KEY... :aie:

Citation:

---

Récursivité Oracle : OUI
CTE Oracle : OUI
CTE récursive Oracle : NON (mais j'ai très bien pu commettre des erreurs)

---

FAUX :
Oracle ne gère pas la récursivité... Il gère, avec CONNECT BY PRIOR, uniquement la descente dans un arbre. On ne peut pas faire de parcours de graphe dans Oracle... Le CONNECT BY ne permet pas de le faire !

A +