Gestion d'arbres par représentation intervallaire

hello,
une chtite question par rapport à cet article de SQLPro : http://sql.developpez.com/arborescence/

L'idée est séduisante, dès lors qu'on ne remanie pas l'arborescence trop souvent. Mais j'ai un doute concernant un point précis : imaginez l'aroborescence suivante :
A est la racine de l'arbre, B C et D sont ses enfants directs. E et F sont les enfants de B.

SI l'on désire déplacer le sous arbre B, sous C, pour obtenir : A est la racine de l'arbre, C et D ses enfants directs, B est le descendant de C, E et F sont les descendants de B.

Avec cette technique intervalaire, le seul moyen que je voie pour déplacer un sous-arbre est :
- stocker le sous-arbre B dans une table temporaire
- renuméroter toutes les bornes supérieurs à la borne droite de B
- réinsérer le sous-arbre stocké dans la table temporaire, en renumérotant à nouveau les bornes.

Sur des gros arbres, c'est très vite lourdingue :D

Je voulais donc savoir si vous voyez une autre manière de faire :)

Une simple procédure stockée suffit.

Voici un exemple implémenté avec une table de nom T_FAMILLE_FML :

Code:

1
2
3
4
5
6
7
 
CREATE TABLE T_FAMILLE_FML
(FML_ID
 FML_BG
 FML_BD
 FML_NIVEAU
...)

La procédure :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
SET QUOTED_IDENTIFIER ON 
GO
SET ANSI_NULLS ON 
GO
 
/* ============================================= */
/* DÉPLACEMENT D'UN SOUS ARBRE DANS FAMILLE      */
/* ============================================= */
 
ALTER  PROCEDURE SP_MOVE_TREE_FML
 
	-- Frédéric Brouard, Philippe Boucault
	-- 03/10/2002
	@id int,         -- Ident de l'élément déplacé
	@id_parent int,  -- Ancêtre ou frère point de destination du déplacement
	@mode char(2),   -- FG : Grand Frère, PF : Petit Frère, FA : Fils ainé, FC : Fils cadet, P : Père, etc
	@recurs bit      -- La descendance est déplacé aussi
 
AS
 
DECLARE @OK int
DECLARE @bdmax int  -- limite supérieure droite de l'arborescence
DECLARE @deltab int -- Delta de borne
 
DECLARE @bgd int    -- Infos sur le déplacé
DECLARE @bdd int
DECLARE @nivd int
 
DECLARE @bgp int    -- Infos sur le parent
DECLARE @bdp int
DECLARE @nivp int
 
-- Mode silencieux
SET NOCOUNT ON
 
IF @mode IS NULL
BEGIN
   RAISERROR ('Déplacement impossible sans mode ! (TABLE T_FAMILLE_FML)', 16, 1)
   RETURN
END
 
IF @recurs IS NULL
BEGIN
   RAISERROR ('Déplacement impossible sans type ! (TABLE T_FAMILLE_FML)', 16, 1)
   RETURN
END
 
IF @id IS NULL
BEGIN
   RAISERROR ('Déplacement impossible sans précision de l''élément ! (TABLE T_FAMILLE_FML)', 16, 1)
   RETURN
END
 
IF @id_parent IS NULL
BEGIN
   RAISERROR ('Déplacement impossible sans précision du destinataire ! (TABLE T_FAMILLE_FML)', 16, 1)
   RETURN
END
 
IF @id = @id_parent
BEGIN
   RAISERROR ('Déplacement impossible , origine et destination identique ! (TABLE T_FAMILLE_FML)', 16, 1)
   RETURN
END
 
SET @mode = UPPER(@mode)
IF NOT( @mode = 'GF' OR @mode = 'PF' OR @mode = 'FC' OR @mode = 'FA' ) --  OR @mode = 'P' -- PBT: à vérifier !
BEGIN
   RAISERROR ('Déplacement impossible, mode inconnu ! (TABLE T_FAMILLE_FML)', 16, 1)
   RETURN
END
 
 
-- démarrage transaction -------------------
SET TRANSACTION ISOLATION LEVEL SERIALIZABLE 
BEGIN TRANSACTION MOVE_FML
 
-- L'élément existe toujours ?
SELECT @OK = count(*) FROM T_FAMILLE_FML WHERE FML_ID = @id
IF @OK IS NULL OR @OK = 0
BEGIN
   RAISERROR ('Déplacement impossible, l''élément n''existe pas ! (TABLE T_FAMILLE_FML)', 16, 1)
   GOTO LBL_ERROR
   RETURN
END
 
-- Le parent existe toujours ?
SELECT @OK = count(*) FROM T_FAMILLE_FML WHERE FML_ID = @id_parent
IF @OK IS NULL OR @OK = 0
BEGIN
   RAISERROR ('Déplacement impossible, le parent n''existe pas ! (TABLE T_FAMILLE_FML)', 16, 1)
   GOTO LBL_ERROR
   RETURN
END
 
-- On récupère la borne supérieure max de l'ensemble
SELECT @bdmax = max(FML_BD) FROM T_FAMILLE_FML
IF @bdmax IS NULL OR @bdmax = 0
BEGIN
   RAISERROR ('Déplacement impossible, la borne BD est nulle ! (TABLE T_FAMILLE_FML)', 16, 1)
   GOTO LBL_ERROR
   RETURN
END
 
-- On a un élément : on récupère ses caractéristiques
SELECT @bgd = FML_BG, @bdd = FML_BD, @nivd = FML_NIVEAU 
       FROM T_FAMILLE_FML 
       WHERE FML_ID = @id
IF @@ERROR <> 0
BEGIN
   GOTO LBL_ERROR
   RETURN
END
 
SET @deltab = @bdmax + 1 - @bgd
 
-- DEBUT de l'opération proprement dite...
 
-- Opération récursive ?
IF @recurs = 0
BEGIN
   -- Seul l'élément doit être déplacé
 
   -- déplacement de l'élément seul en fin de liste
   UPDATE T_FAMILLE_FML
          SET FML_BG = FML_BG + @deltab,
              FML_BD = FML_BD + @deltab
          WHERE FML_ID = @id
   IF @@ERROR <> 0
   BEGIN
      GOTO LBL_ERROR
      RETURN
   END
 
   -- remontée de ses descendants dans la hiérarchie
   UPDATE T_FAMILLE_FML
          SET FML_BG = FML_BG - 1,
              FML_BD = FML_BD - 1,
              FML_NIVEAU = FML_NIVEAU - 1
          WHERE FML_BG > @bgd AND FML_BD < @bdd
   IF @@ERROR <> 0
   BEGIN
      GOTO LBL_ERROR
      RETURN
   END
   -- rééquilibrage de l'arbre
   UPDATE T_FAMILLE_FML
          SET FML_BG = FML_BG - 2
          WHERE FML_BG > @bdd AND FML_BG < @bdmax
   IF @@ERROR <> 0
   BEGIN
      GOTO LBL_ERROR
      RETURN
   END
   --    
   UPDATE T_FAMILLE_FML
          SET FML_BD = FML_BD - 2
          WHERE FML_BD > @bdd AND FML_BD <= @bdmax
   IF @@ERROR <> 0
   BEGIN
      GOTO LBL_ERROR
      RETURN
   END
 
   -- Mise en place de l'élement deplacé
 
   -- On récupère d'abord les caractéristiques du parent
   SELECT @bgp = FML_BG, @bdp = FML_BD, @nivp = FML_NIVEAU 
          FROM T_FAMILLE_FML 
          WHERE FML_ID = @id_parent
   IF @@ERROR <> 0
   BEGIN
      GOTO LBL_ERROR
      RETURN
   END
 
   -- Grand frère
   IF @mode = 'GF'
   BEGIN
      -- Limite sup.
      UPDATE T_FAMILLE_FML
             SET FML_BD = FML_BD + 2
             WHERE FML_BD >= @bdp AND FML_BD <= @bdmax
      IF @@ERROR <> 0
      BEGIN
         GOTO LBL_ERROR
         RETURN
      END
 
      -- Limite inf.
      UPDATE T_FAMILLE_FML
             SET FML_BG = FML_BG + 2
             WHERE FML_BG >= @bgp AND FML_BG < @bdmax
      IF @@ERROR <> 0
      BEGIN
         GOTO LBL_ERROR
         RETURN
      END
 
      UPDATE T_FAMILLE_FML
             SET FML_BG = @bgp,
                 FML_BD = @bgp + 1,
                 FML_NIVEAU = @nivp
             WHERE FML_ID = @id
      IF @@ERROR <> 0
      BEGIN
         GOTO LBL_ERROR
         RETURN
      END
   END
 
   -- Petit Frère 
   IF @mode = 'PF'
   BEGIN
      -- Limite sup.
      UPDATE T_FAMILLE_FML
             SET FML_BD = FML_BD + 2
             WHERE FML_BD > @bdp AND FML_BD <= @bdmax
      IF @@ERROR <> 0
      BEGIN
         GOTO LBL_ERROR
         RETURN
      END
 
      -- Limite inf.
      UPDATE T_FAMILLE_FML
             SET FML_BG = FML_BG + 2
             WHERE FML_BG > @bdp AND FML_BG < @bdmax
      IF @@ERROR <> 0
      BEGIN
         GOTO LBL_ERROR
         RETURN
      END
 
      UPDATE T_FAMILLE_FML
             SET FML_BG = @bdp + 1,
                 FML_BD = @bdp + 2,
                 FML_NIVEAU = @nivp
             WHERE FML_ID = @id
      IF @@ERROR <> 0
      BEGIN
         GOTO LBL_ERROR
         RETURN
      END
   END
 
   -- Fils cadet
   IF @mode = 'FC'
   BEGIN
      -- Limite sup.
      UPDATE T_FAMILLE_FML
             SET FML_BD = FML_BD + 2
             WHERE FML_BD >= @bdp AND FML_BD <= @bdmax
      IF @@ERROR <> 0
      BEGIN
         GOTO LBL_ERROR
         RETURN
      END
 
      -- Limite inf.
      UPDATE T_FAMILLE_FML
             SET FML_BG = FML_BG + 2
             WHERE FML_BG > @bdp AND FML_BG < @bdmax
      IF @@ERROR <> 0
      BEGIN
         GOTO LBL_ERROR
         RETURN
      END
 
      UPDATE T_FAMILLE_FML
             SET FML_BG = @bdp,
                 FML_BD = @bdp + 1,
                 FML_NIVEAU = @nivp + 1
             WHERE FML_ID = @id
      IF @@ERROR <> 0
      BEGIN
         GOTO LBL_ERROR
         RETURN
      END
   END
 
   -- Fils ainé
   IF @mode = 'FA'
   BEGIN
      -- Limite sup.
      UPDATE T_FAMILLE_FML
             SET FML_BD = FML_BD + 2
             WHERE FML_BD > @bgp AND FML_BD <= @bdmax
      IF @@ERROR <> 0
      BEGIN
         GOTO LBL_ERROR
         RETURN
      END
 
      -- Limite inf.
      UPDATE T_FAMILLE_FML
             SET FML_BG = FML_BG + 2
             WHERE FML_BG > @bgp AND FML_BG < @bdmax
      IF @@ERROR <> 0
      BEGIN
         GOTO LBL_ERROR
         RETURN
      END
 
      UPDATE T_FAMILLE_FML
             SET FML_BG = @bgp + 1,
                 FML_BD = @bgp + 2,
                 FML_NIVEAU = @nivp + 1
             WHERE FML_ID = @id
      IF @@ERROR <> 0
      BEGIN
         GOTO LBL_ERROR
         RETURN
      END
   END
END
ELSE
BEGIN
   -- L'élément et sa descendance doivent être déplacés
 
   -- déplacement de l'élément et de sa descendance en fin de liste
   -- Le niveau sera réactualisé ultérieurement
   UPDATE T_FAMILLE_FML
          SET FML_BG = FML_BG + @deltab,
              FML_BD = FML_BD + @deltab,
              FML_NIVEAU = FML_NIVEAU - @nivd
          WHERE FML_BG >= @bgd AND FML_BD <= @bdd
   IF @@ERROR <> 0
   BEGIN
      GOTO LBL_ERROR
      RETURN
   END
 
   -- rétablissement des bornes
 
   -- Calcul du Delta
   SET @deltab = @bdd - @bgd + 1
   --
   UPDATE T_FAMILLE_FML
          SET FML_BD = FML_BD - @deltab
          WHERE FML_BD > @bdd AND FML_BG <= @bdmax
   IF @@ERROR <> 0
   BEGIN
      GOTO LBL_ERROR
      RETURN
   END
   -- 
   UPDATE T_FAMILLE_FML
          SET FML_BG = FML_BG - @deltab
          WHERE FML_BG > @bdd AND FML_BG < @bdmax
   IF @@ERROR <> 0
   BEGIN
      GOTO LBL_ERROR
      RETURN
   END
 
   -- On récupère d'abord les caractéristiques du parent
   SELECT @bgp = FML_BG, @bdp = FML_BD, @nivp = FML_NIVEAU 
          FROM T_FAMILLE_FML 
          WHERE FML_ID = @id_parent
   IF @@ERROR <> 0
   BEGIN
      GOTO LBL_ERROR
      RETURN
   END
 
   -- Mise en place de l'élement deplacé
 
   -- Grand frère
   IF @mode = 'GF'
   BEGIN
      -- Limite sup.
      UPDATE T_FAMILLE_FML
             SET FML_BD = FML_BD + @deltab
             WHERE FML_BD > @bgp AND FML_BD <= @bdmax
      IF @@ERROR <> 0
      BEGIN
         GOTO LBL_ERROR
         RETURN
      END
 
      -- Limite inf.
      UPDATE T_FAMILLE_FML
             SET FML_BG = FML_BG + @deltab
             WHERE FML_BG >= @bgp AND FML_BG < @bdmax
      IF @@ERROR <> 0
      BEGIN
         GOTO LBL_ERROR
         RETURN
      END
 
      -- Recadrage de la liste d'éléments déplacés
      SET @deltab = @bdmax - @bgp + 1
      UPDATE T_FAMILLE_FML
             SET FML_BG = FML_BG - @deltab,
                 FML_BD = FML_BD - @deltab,
                 FML_NIVEAU = FML_NIVEAU + @nivp
             WHERE FML_BG > @bdmax
      IF @@ERROR <> 0
      BEGIN
         GOTO LBL_ERROR
         RETURN
      END
   END
 
   -- Petit Frère 
   IF @mode = 'PF'
   BEGIN
      -- Limite sup.
      UPDATE T_FAMILLE_FML
             SET FML_BD = FML_BD + @deltab
             WHERE FML_BD > @bdp AND FML_BD <= @bdmax
      IF @@ERROR <> 0
      BEGIN
         GOTO LBL_ERROR
         RETURN
      END
 
      -- Limite inf.
      UPDATE T_FAMILLE_FML
             SET FML_BG = FML_BG + @deltab
             WHERE FML_BG > @bdp AND FML_BG < @bdmax
      IF @@ERROR <> 0
      BEGIN
         GOTO LBL_ERROR
         RETURN
      END
 
      -- Recadrage de la liste d'éléments déplacés
      SET @deltab = @bdmax - @bdp
      UPDATE T_FAMILLE_FML
             SET FML_BG = FML_BG - @deltab,
                 FML_BD = FML_BD - @deltab,
                 FML_NIVEAU = FML_NIVEAU + @nivp
             WHERE FML_BG > @bdmax
      IF @@ERROR <> 0
      BEGIN
         GOTO LBL_ERROR
         RETURN
      END
   END
 
   -- Fils cadet
   IF @mode = 'FC'
   BEGIN
      -- Limite sup.
      UPDATE T_FAMILLE_FML
             SET FML_BD = FML_BD + @deltab
             WHERE FML_BD >= @bdp AND FML_BD <= @bdmax
      IF @@ERROR <> 0
      BEGIN
         GOTO LBL_ERROR
         RETURN
      END
 
      -- Limite inf.
      UPDATE T_FAMILLE_FML
             SET FML_BG = FML_BG + @deltab
             WHERE FML_BG > @bdp AND FML_BG < @bdmax
      IF @@ERROR <> 0
      BEGIN
         GOTO LBL_ERROR
         RETURN
      END
 
      -- Recadrage de la liste d'éléments déplacés
      SET @deltab = @bdmax - @bdp + 1
      UPDATE T_FAMILLE_FML
             SET FML_BG = FML_BG - @deltab,
                 FML_BD = FML_BD - @deltab,
                 FML_NIVEAU = FML_NIVEAU + @nivp + 1
             WHERE FML_BG > @bdmax
      IF @@ERROR <> 0
      BEGIN
         GOTO LBL_ERROR
         RETURN
      END
   END
 
   -- Fils ainé
   IF @mode = 'FA'
   BEGIN
      -- Limite sup.
      UPDATE T_FAMILLE_FML
             SET FML_BD = FML_BD + @deltab
             WHERE FML_BD > @bgp AND FML_BD <= @bdmax
      IF @@ERROR <> 0
      BEGIN
         GOTO LBL_ERROR
         RETURN
      END
 
      -- Limite inf.
      UPDATE T_FAMILLE_FML
             SET FML_BG = FML_BG + @deltab
             WHERE FML_BG > @bgp AND FML_BG < @bdmax
      IF @@ERROR <> 0
      BEGIN
         GOTO LBL_ERROR
         RETURN
      END
 
      -- Recadrage de la liste d'éléments déplacés
      SET @deltab = @bdmax - @bgp
      UPDATE T_FAMILLE_FML
             SET FML_BG = FML_BG - @deltab,
                 FML_BD = FML_BD - @deltab,
                 FML_NIVEAU = FML_NIVEAU + @nivp + 1
             WHERE FML_BG > @bdmax
      IF @@ERROR <> 0
      BEGIN
         GOTO LBL_ERROR
         RETURN
      END
   END
END
 
COMMIT TRANSACTION MOVE_FML
RETURN
 
LBL_ERROR:
ROLLBACK TRANSACTION MOVE_FML
 
GO
SET QUOTED_IDENTIFIER OFF 
GO
SET ANSI_NULLS ON 
GO

A +

J'ai été lire l'article en question, pour me faire une idée.

Mon sentiment est que la représentation intervallaire est en effet fort peu adadptée à ta problématique, contraitement à la représentation "habituelle". Si tu a déjà validé le choix de ce modèle, je n'ai pas d'autres solutions à te proposer ...

[Edit] Grillé [/Edit]

Le remaniement d'arbre et le déplacement de sous arbre ne pose aucun problème majeur ni en terme de performance, ni en terme de lourdeur dans le cadre d'une représentation intervallaire.

Pour l'avoir mise en production avec quelques centaines de milliers de lignes nous n'avons jamais été au dessus de 10 ms dans toutes les manips en production.

Encore faut-il savoir modéliser proprement une BD et indexer judicieusement.. Et là mon constat est clair : peu de gens savent modéliser et pratiquement aucun pour la performance... Quand à l'indexation... on trouve tout et n'importe quoi !

A +

update séquentiel

Bonjour,

J'ai été séduit par la représentation intervallaire et je suis étonné que vous ayez des performances bonnes ou acceptables lors du déplacement d'un sous-arbre.

En effet, l'update est obligatoirement séquentiel puisqu'il y a un update des valeurs. Je ne vois pas ce que les index apportent là dedans ?

le simple :

UPDATE NEW_FAMILLE
SET NFM_BD = NFM_BD + 2
WHERE NFM_BD >= 35

Quelque chose m'échappe certainement.
J'ai fait les tests sous postgres.

merci de votre patience

--

J'ai fini par trouver le pb :
- je travaillais avec une table hérité
- et j'ai défini (de façon automatique, trop automatique ...) des indexs en double sur la table mère et la table fille. Ca fait complètement chuter les perfs de mises à jour.

a+