Discussion :

[cedricROCHART]

Bonjour à tous,

Je me suis inspiré d'un excellent article sur http://sqlpro.developpez.com/cours/arborescence/ pour écrire des procédures d'insertion, suppression, déplacement, copie et clone. Cette arborescence permet de manipuler plusieurs arbres. Pour y parvenir j'ai créé 3 tables
arborescence => Représente un noeud et sa racine (pour gérer plusieurs arbres)
arborescence_info => Permet de nommer un noeud dans plusieurs langue
arborescence_borne => Permet d'affecter plusieurs borne gauche et droite pour un noeud (cas des clones : un noeud peut être présent à plusieurs endroit de l'arborescence, ce n'est pas une copie mais bien le même objet).

Mon soucis concerne la copie et le clone de sous-arbre :
Mes procédures comportent 2 paramètres, le noeud à dupliquer et le père de l'endroit où l'on souhaite l'insérer (on ajoute à droite des fils déjà existant).

Concernant la copie de sous arbre :
- On récupère les informations des noeuds à dupliquer et du père du nouvelle emplacement

- On récupère le nombre de noeud composant le sous-arbre à dupliquer

- On décale les bornes droite >= au père de 2 * nbNoeud

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
UPDATE arborescence_borne
INNER JOIN arborescence ON arb_id = arbo_arb_id
SET arbo_borne_droite = arbo_borne_droite + (2 * nbNoeud)
WHERE arbo_borne_droite >= borneDroitePere
	AND arb_racine_arb_id = racinePere;

- On décale les bornes gauche > au père de 2 * nbNoeud

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
UPDATE arborescence_borne
INNER JOIN arbo_borne_droite ON arb_id = arbo_arb_id
SET arbo_borne_gauche = arbo_borne_gauche + (2 * nbNoeud)
WHERE arbo_borne_gauche > borneDroitePere
	AND arb_racine_arb_id = racinePere;

- On calcule le deltaBorne => (borneDroitePere + (2 * nbNoeud) - 1) - borneDroiteDuplique)

- On calcule le deltaNiveau => niveauP - (niveauDuplique + 1)

- On boucle (WHILE) pour l'insertion des noeuds, de la borne gauche à la borne droite du noeud à dupliquer.

Le résultat de cette procédure est que des noeuds sont copiés mais pas ceux désirés.



Concernant le clonage de noeud :
- On récupère les informations des noeuds à dupliquer et du père du nouvelle emplacement

- On récupère le nombre de noeud composant le sous-arbre à dupliquer

- On décale les bornes droite >= au père de 2 * nbNoeud

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
UPDATE arborescence_borne
INNER JOIN arborescence ON arb_id = arbo_arb_id
SET arbo_borne_droite = arbo_borne_droite + (2 * nbNoeud)
WHERE arbo_borne_droite >= borneDroitePere
	AND arb_racine_arb_id = racinePere;

- On décale les bornes gauche > au père de 2 * nbNoeud

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
UPDATE arborescence_borne
INNER JOIN arbo_borne_droite ON arb_id = arbo_arb_id
SET arbo_borne_gauche = arbo_borne_gauche + (2 * nbNoeud)
WHERE arbo_borne_gauche > borneDroitePere
	AND arb_racine_arb_id = racinePere;

- On calcule le deltaBorne => (borneDroitePere + (2 * nbNoeud) - 1) - borneDroiteDuplique)

- On calcule le deltaNiveau => niveauP - niveauDuplique + 1

- On ajoute les bornes au noeud dans arborescence_borne

Là encore les résultats sont incohérent.

Je pense que cela viens du fait que je décale les bornes des éléments à droite du père avant de parcourir le sous arbre à dupliquer.

[SQLpro]

À me lire :
http://blog.developpez.com/sqlpro/p7...edure_de_depla
http://blog.developpez.com/sqlpro/p8...vallaire_proce

A +

[cedricROCHART]

Bonjour,

Merci pour votre retour rapide.
Je me suis inspiré de l'insertion et du déplacement d'arbre pour la copie de noeud mais les résultats sont instable par exemple je peux copier 5 ou 6 sous arbre d'une centaine de feuille chacun mais il survient un moment où les bornes ne sont plus cohérente entre elles.

[SQLpro]

MySQL n'est pas un vrai SGBDR et ne sait pas faire des opérations ensemblistes.
Je ne serais pas étonné que cela vienne de ça !

A +

[cedricROCHART]

Bonjour,
Merci pour vos remarques et après lecture de l'un de vos billet http://blog.developpez.com/sqlpro/p9...oudre_aux_yeux qui nous a laissé quelques sueur froide, nous avons décidé de migrer vers Postgres qui nous parait plus robuste et moins permissif que Mysql.

Merci d'avoir pris le temps de me repondre.

Au plaisir.

[ericd69]

salut,

au passage les arbres intervallaires ne sont pas l'approche la plus efficace:

• 3 opérations ensemblistes (insert/delete ou déplacements suivi de 2 updates)
• de toute façon faut se fader une récursion (que tu la fasses coté sgbd ou langage appelant)

autan je suis d'accord quand tu te fous des mec qui réinvente les sgbd à coup de nosql antédiluvien, cher sqlpro, autan sortir cet méthode ancêtrale de stockage d'arbre en tableau...
attention elle marche bien mais bon...

par définition dans un arbre au sens graphe du terme, chaque élément a un seul antécédent...

donc une simple colonne genre "idparent" permet de coder la relation...
avantage: 1 seule opération pour insertion ou déplacement

après selon les compétences on fait ça avec un api purement sql procédural ou avec un mixe langage appelant/sql

mais le sgbd n'a pas grand chose à voir dans la complexité du traitement... c'est juste une question d'approche... les représentations c'est comme les techniques de tri, il y en a plein mais chacune est optimisée pour une situation...

les arbres intervallaires sont hyper efficaces pour restituer rapidement tous les éléments d'un sous-arbre si ceux-ci sont à afficher au même niveau les uns que le autres... sinon les désavantages de la mise à jour de la structure le rendent moins attrayant...

après il faut aussi bien gérer le niveau d'isolation des opérations de mise à jour (là aussi quel que soit le sgbd)...

bref les arbres ne sont pas compliqués (guère plus que le parcours de graphes plus génériques pour peu qu'on utilise des structures souples et adaptées et qu'on sérialise bien les opérations)

bref rien d'impossible en mysql...

après tu migres si tu veux,ça dépend de tes besoins (ou peurs)

bon courage

[SQLpro]

Bonjour,
Merci pour vos remarques et après lecture de l'un de vos billet http://blog.developpez.com/sqlpro/p9...oudre_aux_yeux qui nous a laissé quelques sueur froide, nous avons décidé de migrer vers Postgres qui nous parait plus robuste et moins permissif que Mysql.

Merci d'avoir pris le temps de me repondre.

Au plaisir.

C'est effectivement une nettement meilleurs solution et surtout totalement libre, avec ses avantages et inconvénients.

A +