Aide sur algorithme de regroupement

J'ai une table contenant 2 colonnes (Identifiant, identifiant maitre)

120 123
121 122
122 121
122 123
123 120
123 122
100 101
101 100

Je souhaite trouver un identifiant maitre unique par groupe, soit par exemple :
120 120
121 120
122 120
122 120
123 120
123 120
100 100
101 100

J'ai appliqué sur la table plusieurs traitements SQL, mais il me reste quelques cas ou je n'obtiens pas ce que je veux (500 cas sur 3.000.000 de lignes).

Connaitriez-vous une méthode afin de réaliser ce traitement ?
Merci de votre aide

En toute généralité, cela me semble être un problème de recherche de composantes connexes dans le graphe où les sommets sont les identifiants et les arcs les relations (identifiant, identifiant maître).

effectivement.

Maintenant reste à savoir comment faire cela en SQL (non récursif) :?

en sql pur ce n'est pas possible sauf à connaitre précisément le nombre de niveaux possibles auxquels cela devient plus simple avec par exemple des requêtes union comprenant autant de sous requête que de niveau
si on ajoute un champ père utltime on peut la faire tourner tant qu'elle apporte une modif



par contre il est possible d'utiliser une fonction récursive
et de programmer une fonction paternité ultime avec un test d'arret sur
maitre=esclave
si la version de sql peut utiliser les fonctions intégrées c'est gagné

Petit bémol à l'affirmation de random.
Certains SGBD (et c'est le cas d'Oracle) ont une extension de SQL afin de traiter les reqêtes recursives.

Malheureusement je suis sous Sybase !

Mihaela tu as raison mais ce n'est pas dans le sql pur

metheorn si tu peux ajouter un champ regroup tu fais tourner unr requête
mise à jour

étape 1 regroup prends dans tous les cas de figure la valeur de maitre

étape 2 à faire itérer tant que des enregistrements sont mis à jour
regroup= maitre(maitre)
where regroup<>maitre(maitre)

Merci

Je test et je vous tiens au courant

Donc ma table que je nommerais #master
ID
ID_RATTACHE (correspond à maitre)
ID_MASTER (correspond à regroup)

1ère étape :
update #master
set ID_MASTER=ID_RATTACHE

2ème étape :
update #master
set #master.ID_MASTER=T2.ID_RATTACHE
from #master, #master T2
where #master.ID_RATTACHE=T2.ID
and #master.ID_MASTER<>T2.ID_RATTACHE

La deuxième étape boucle indéfiniment, et dans notre cas on retrouve la table ci-dessous :
120 123 122
121 122 123
122 121 122
122 123 122
123 120 123
123 122 123

puis
120 123 120
121 122 121
122 121 122
122 123 120
123 120 123
123 122 121

En gros, cela boucle à la fin entre les deux résultats ci-dessus.

Je pense que le problème vient du fait que les liens peuvent aller dans les deux sens.
120 pointe sur 123 et 123 point sur 120 (et 122)

désolé je n'avais pas vu la subtilité du regroupement

Quelle règle fait qu'à partir de
100 101
101 100

tu obtiennes
100 100
101 100

et non
100 101
101 101

Est-ce que Sybase implémente le WITH RECURSIVE de SQL3 ?

Les deux possibilités me conviennent.
Par défaut, nous préférons prendre l'identifiant le plus petit.

Concernant le WITH RECURSIVE, Sybase ne le gère pas :( !

J'ai testé la méthode suivante sur ton jeu d'essai :
A exécuter une seule fois :

Code:

---

1 2 3 4 5 6 7 8

update metheorn x set c = (select min(b) from (select a, b from metheorn y union select a, a from metheorn y union select b, a from metheorn y) z where x.a = z.a);

---

A itérer tant qu'il y a des changements (1 seule fois dans ton exemple) :

Code:

---

1 2 3 4 5 6 7 8 9 10

update metheorn x set c = (select min(c) from (select a, c from metheorn union select x.a, z.c from metheorn x inner join metheorn y on x.c = y.c inner join metheorn z on y.b = z.a) z where x.a = z.a);

---

PS : normalement un alias est interdit sur un UPDATE, mais cela marche parfaitement avec ORACLE avec lequel je fais mes tests, avec SYBASE tu sera peut-être obligé de ré-écrire la syntaxe des UPDATE.

Je test et je te tiens au couant.
En tout cas, encore merci :P

Malheureusement, cela ne fonctionne pas entièrement.

1. la deuxième requête boucle toujours sur toute les lignes de la table
2. il y a un cas qui ne fonctionne pas (par contre le cas ci-dessus fonctionne nickel)

Voici donc le cas qui pose problème :
100 101
100 101
100 101
101 100
101 100
101 100
102 100
102 100
103 104
104 103
105 100
105 103

on obtient :
100 101 100
100 101 100
100 101 100
101 100 100
101 100 100
101 100 100
102 100 100
102 100 100
103 104 103
104 103 103
105 100 100
105 103 100

Je regarde comment améliorer la requete pour traiter ce cas. A voir également le fait qu'il boucle toujours !

J'ai règler le premier soucis en rajoutant une sous-requete UNION :

Code:

---

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

update metheorn x set c = (select min(c) from (select a, c from metheorn union select x.a, y.c from metheorn x inner join metheorn y on x.c = y.b union select x.a, z.c from metheorn x inner join metheorn y on x.c = y.c inner join metheorn z on y.b = z.a) z where x.a = z.a);

---

Par contre, je n'ai pas choisit de méthode pour tester le fait qu'il y ai eu un changement ou non. Mais cela, c'est beaucoup plus simple !

encore merci.
Je vais tester toute cette méthode sur une vrai base afin de vérifier qu'il ne reste pas de cas tordu !