World Wide Tutorial

1. Representation classic self-jointed
A usual way to represent such a tree is to provide an auto-join the table on itself:

CREATE TABLE FAMILY (FAM_ID INTEGER, FAM_LIB VARCHAR (16), FAM_PERE INTEGER)
INSERT INTO FAMILY (FAM_ID, FAM_LIB, FAM_PERE) VALUES (0, 'Transport', NULL) INSERT INTO FAMILY (FAM_ID, FAM_LIB, FAM_PERE) VALUES (1, 'Terrestrial', 0) INSERT INTO FAMILY (FAM_ID, FAM_LIB, FAM_PERE) VALUES (2, 'Marin', 0) INSERT INTO FAMILY (FAM_ID, FAM_LIB, FAM_PERE) VALUES (3, 'Air', 0) INSERT INTO FAMILY (FAM_ID, FAM_LIB, FAM_PERE) VALUES (4, 'Cars', 1) INSERT INTO FAMILY (FAM_ID, FAM_LIB, FAM_PERE) VALUES (5, 'Truck', 1) INSERT INTO FAMILY (FAM_ID, FAM_LIB, FAM_PERE) VALUES (6, 'Moto', 1) INSERT INTO FAMILY (FAM_ID, FAM_LIB, FAM_PERE) VALUES (7, 'Cycling', 1) INSERT INTO FAMILY (FAM_ID, FAM_LIB, FAM_PERE) VALUES (8, 'Helico', 3) INSERT INTO FAMILY (FAM_ID, FAM_LIB, FAM_PERE) VALUES (9, 'Airplane', 3) INSERT INTO FAMILY (FAM_ID, FAM_LIB, FAM_PERE) VALUES (10, 'ultralight', 3) INSERT INTO FAMILY (FAM_ID, FAM_LIB, FAM_PERE) VALUES (11, 'Rocket', 3) INSERT INTO FAMILY (FAM_ID, FAM_LIB, FAM_PERE) VALUES (12, 'Parachute', 3) INSERT INTO FAMILY (FAM_ID, FAM_LIB, FAM_PERE) VALUES (13, 'glider', 3) INSERT INTO FAMILY (FAM_ID, FAM_LIB, FAM_PERE) VALUES (14, 'Sailing', 2) INSERT INTO FAMILY (FAM_ID, FAM_LIB, FAM_PERE) VALUES (15, 'Liner', 2) INSERT INTO FAMILY (FAM_ID, FAM_LIB, FAM_PERE) VALUES (16, 'Plate Sailing', 2) INSERT INTO FAMILY (FAM_ID, FAM_LIB, FAM_PERE) VALUES (17, 'Trail', 6) INSERT INTO FAMILY (FAM_ID, FAM_LIB, FAM_PERE) VALUES (18, 'Side-car', 6) INSERT INTO FAMILY (FAM_ID, FAM_LIB, FAM_PERE) VALUES (19, 'Civil ', 9) INSERT INTO FAMILY (FAM_ID, FAM_LIB, FAM_PERE) VALUES (20,' Tourism ', 9) INSERT INTO FAMILY (FAM_ID, FAM_LIB, FAM_PERE) VALUES (21,' Military ', 9)

Here is the column that allows FAM_PERE join the element of the tree to its ancetre.
Finding the supervisor of an element is not something difficult. Take for example the Parachute (ID = 12); searching for the father made a complaint:
SELECT * FROM FAMILY WHERE FAM_ID = (SELECT FAM_PERE FROM FAMILY WHERE FAM_ID = 12)
FAM_ID FAM_LIB FAM_PERE
---------------- ----------- -----------
3 Air 0
But finding all ascending is another pair of race. In general it goes through a recursive procedure such as:
Procedure RecherchePeres (in id integer, inout answer string) begin answer = answer + ',' + (SELECT FAM_LIB FROM FAMILY WHERE ID = FAM_ID) if id = 0 then return else id = (SELECT FAM_PERE FROM FAMILY WHERE ID = FAM_ID) end

Now, not only recursion is very expensive, but some languages stored procedures, as Transact SQL Server Microsoft SQL do not manage it!
That is why this model is a proscire when:
the tree is deep (more than 5 levels)
the tree is large (over 100 items on the same level)
the tree contains a lot of values (from 200 to 300 items)
The majority of complaints are requests for interrogation - SELECT (at least 50% of requests)
And personally I advise you to spend the interval model whenever one of these 4 criteria is true!

2. Representation of the tree structure intervallaire
A particularly elegant way to represent powerful hierarchies type of tree is set up adjacent intervals and covering. The principle is simple:
leaves located at the same level have adjacent intervals
nodes covering of leaves or other nodes have intervals covering
Remember also that an interval consists of two values: low base and the base high.

We then said everything on this hierarchical representation ... But what is their interest?
If the insertion or deletion in such a representation is an inexpensive, interrogation and including research expressed mostly in a single request, as we shall see ...
For this model, we must assign at all entrances of our table tree the two terminals of the interval that we call BG (Borne Left) and BD (Borne Right). The allocation of values of these terminals being along the tree as if we drew a line for the closest circle without ever crossing that line with a branch and numbering sequentially each leaf or node for the first time by the left edge and a second time by the right edge (or by analogy with a sheet on the front and back) is on track around the tree line wrapping it in more just like this:
(Please excuse me for having cut the tree in two, but it was not easy to work on drawing one plane!)
Numbering interval nodes and leaves of trees using a route "enveloping"

Of this figure, we can already see that:
the number of assigned number is double the number of elements
All leaves have a long interval 1 (Point right - simply left = 1)
conversely, all nodes have a long interval of more than 1 (Point right - simply left> 1)
We can therefore immediately whether this or that piece of the tree is a node or a leaf.

But there is also stronger: we can bring only one request:
all the elements, and leaf nodes combined, depending on the point of reference (ie under the tree whose root is the element of reference)
all independent elements of the reference element (or under trees complementary)
all fathers of a reference element
Another way to "see" that tree is to represent him in instalments inclusive. The root is the portion broadest sense, and each sheet is a thin slice:

representation tranche of a tree modeled on a intervallaire
Constructing the game test to test our queries:

CREATE TABLE NEW_FAMILLE (NFM_BG INTEGER, NFM_BD INTEGER, NFM_LIB VARCHAR (16))
INSERT INTO NEW_FAMILLE (NFM_BG, NFM_BD, NFM_LIB) VALUES (1, 44, 'Transport') INSERT INTO NEW_FAMILLE (NFM_BG, NFM_BD, NFM_LIB) VALUES (2, 21, 'Air') INSERT INTO NEW_FAMILLE (NFM_BG, NFM_BD, NFM_LIB) VALUES (3, 4, 'glider') INSERT INTO NEW_FAMILLE (NFM_BG, NFM_BD, NFM_LIB) VALUES (5, 6, 'Parachute') INSERT INTO NEW_FAMILLE (NFM_BG, NFM_BD, NFM_LIB) VALUES (7, 8, 'Helico') INSERT INTO NEW_FAMILLE (NFM_BG, NFM_BD, NFM_LIB) VALUES (9, 10, 'Rocket') INSERT INTO NEW_FAMILLE (NFM_BG, NFM_BD, NFM_LIB) VALUES (11, 12, 'ultralight') INSERT INTO NEW_FAMILLE (NFM_BG, NFM_BD, NFM_LIB) VALUES (13, 20, 'Airplane') INSERT INTO NEW_FAMILLE (NFM_BG, NFM_BD, NFM_LIB) VALUES (14, 15, 'Military') INSERT INTO NEW_FAMILLE (NFM_BG, NFM_BD, NFM_LIB) VALUES (16, 17, 'Tourism') INSERT INTO NEW_FAMILLE (NFM_BG, NFM_BD, NFM_LIB) VALUES (18, 19, 'Civil') INSERT INTO NEW_FAMILLE (NFM_BG, NFM_BD, NFM_LIB) VALUES (22, 35, 'Terrestrial') INSERT INTO NEW_FAMILLE (NFM_BG, NFM_BD, NFM_LIB) VALUES (23, 24, 'Bicycle') INSERT INTO NEW_FAMILLE (NFM_BG, NFM_BD, NFM_LIB) VALUES (25, 26, 'Cars') INSERT INTO NEW_FAMILLE (NFM_BG, NFM_BD, NFM_LIB) VALUES (27, 28,' Truck ') INSERT INTO NEW_FAMILLE (NFM_BG, NFM_BD, NFM_LIB) VALUES (29, 34, 'Moto') INSERT INTO NEW_FAMILLE (NFM_BG, NFM_BD, NFM_LIB) VALUES (30, 31, 'Side-car') INSERT INTO NEW_FAMILLE (NFM_BG, NFM_BD, NFM_LIB) VALUES (32, 33, 'Trail') INSERT INTO NEW_FAMILLE (NFM_BG, NFM_BD, NFM_LIB) VALUES (36, 43, 'Marin') INSERT INTO NEW_FAMILLE (NFM_BG, NFM_BD, NFM_LIB) VALUES (37, 38, 'Plate Sailing ') INSERT INTO NEW_FAMILLE (NFM_BG, NFM_BD, NFM_LIB) VALUES (39, 40,' Liner ') INSERT INTO NEW_FAMILLE (NFM_BG, NFM_BD, NFM_LIB) VALUES (41, 42,' Sailboat ')

Now how the main complaints expressed by management of this model tree:

2.1. Look all leaves
It is simply to find elements of a length of the interval is one:
SELECT * FROM NEW_FAMILLE WHERE NFM_BD - NFM_BG = 1

NFM_BG NFM_BD NFM_LIB
----------- ----------- ----------------
3 4 glider
5 6 Parachute
7 8 Helico
9 10 rocket
ULM 11 12
14 15 Military
Tourism 16 17
Civil 18 19
Cycling 23 24
Car 25 26
...
2.2. All sheets in a reference
In this case it is necessary to restrict the beach edge research to those of the element, always looking for a long intervals.

Example: all leaves under the 'Land' whose edges right and left are: NFM_BG = 22 = 35 and NFM_BD
SELECT * FROM NEW_FAMILLE WHERE NFM_BD - NFM_BG = 1 AND NFM_BG> 22 AND NFM_BD <35

NFM_BG NFM_BD NFM_LIB
----------- ----------- ----------------
Cycling 23 24
Car 25 26
Truck 27 28
30 31 Side-car
Trail 32 33

2.3. Look all nodes
Just find all the elements of a length of the interval of more than one:

SELECT * FROM NEW_FAMILLE WHERE NFM_BD - NFM_BG> 1
NFM_BG NFM_BD NFM_LIB
----------- ----------- ----------------
1 44 Transport
2 21 Air
13 20 Aircraft
Terrestrial 22 35
Moto 29 34
Marin 36 43

2.4. All nodes in a reference
In addition to seeking the elements of a length of the interval of more than one, we must also restrict the range of research edges to those of the element.

Example: all the nodes under the 'Transport' NFM_BG which is 1 and 44 is NFM_BD
SELECT * FROM NEW_FAMILLE WHERE NFM_BD - NFM_BG> 1 AND NFM_BG> 1 AND NFM_BD <44

NFM_BG NFM_BD NFM_LIB
----------- ----------- ----------------
2 21 Air
13 20 Aircraft
Terrestrial 22 35
Moto 29 34
Marin 36 43

2.5. All elements dependent on a point of reference (subtree)
It is simply find items whose left and right edges are included in the left and right edges of the element.

Example: all elements depending on the 'Ground' which NFM_BG is 22 and NFM_BD is 35

SELECT * FROM NEW_FAMILLE WHERE NFM_BG> 22 AND NFM_BD <35
NFM_BG NFM_BD NFM_LIB
----------- ----------- ----------------
Cycling 23 24
Car 25 26
Truck 27 28
Moto 29 34
30 31 Side-car
Trail 32 33
This request takes the elements hierarchically dependent on the 'Ground', but excluding, while the following query:

SELECT * FROM NEW_FAMILLE WHERE NFM_BG> = 22 AND NFM_BD <= 35
NFM_BG NFM_BD NFM_LIB
----------- ----------- ----------------
Terrestrial 22 35
Cycling 23 24
Car 25 26
Truck 27 28
Moto 29 34
30 31 Side-car
Trail 32 33
Retains the same point of reference, which then becomes the root of this sub tree.

2.6. All independent elements of a reference element (in addition to tree)
It is simply retain all the elements whose left side is lower than the left edge of the reference element as well as those whose right side is higher than the right edge of the reference element.

Example: all elements independent element NFM_BG whose land is 22 and NFM_BD is 35
SELECT * FROM NEW_FAMILLE WHERE NFM_BG <22 OR NFM_BD> 35

NFM_BG NFM_BD NFM_LIB
----------- ----------- ----------------
1 44 Transport
2 21 Air
3 4 glider
5 6 Parachute
7 8 Helico
9 10 rocket
ULM 11 12
13 20 Aircraft
14 15 Military
Tourism 16 17
Civil 18 19
Marin 36 43
37 38 Plate Windsurfing
39 40 Paquebot
Sailboat 41 42
It should be noted that in reversing the criteria we obtain research are obtained under the additional trees excluding all fathers of the element:

SELECT * FROM NEW_FAMILLE WHERE NFM_BG> 35 OR NFM_BD <22

NFM_BG NFM_BD NFM_LIB
----------- ----------- ----------------
2 21 Air
3 4 glider
5 6 Parachute
7 8 Helico
9 10 rocket
ULM 11 12
13 20 Aircraft
14 15 Military
Tourism 16 17
Civil 18 19
Marin 36 43
37 38 Plate Windsurfing
39 40 Paquebot
Sailboat 41 42

2.7. All fathers of a reference element
In fact research on all elements including both the left and right edges of the reference element:

Example: all fathers of the 'Moto' whose NFM_BG is 29 and NFM_BD is 34

SELECT * FROM NEW_FAMILLE WHERE NFM_BG <29 AND NFM_BD> 34

NFM_BG NFM_BD NFM_LIB
----------- ----------- ----------------
3 46 Transport
Terrestrial 24 37

NOTE: here we have a small variation in the filter WHERE. Rather than spell NFM_BD - NFM_BG = 1, we spent the element NFM_BD the right side of the equal sign, which does not change the value of the equation, but can activate the index of the column NFM_BG, index if there is, what can be assumed it must be a key to this table!

2.10. Counting knots
Counting knots stems from the list of lines with a value of the interval is greater than or different from one:

SELECT COUNT (*) AS NEW_FAMILLE KNOTS FROM WHERE NFM_BG <> NFM_BD -1

KNOTS
-----------
6
2.11. Insertion of an element in this tree
The particularity of this representation is that tree is a tree lined for which we can choose to insert a left or right of the element father. If it does not matter, choose systematic inclusion on the right which does not need to generate negative values for our terminals and leaves the root with a left edge worth what one can find the root instantly .

Try to insert the item 'Roller' directly connected with his father the 'Land'. In this case, the kiosk right of the 'Land' will serve as a reference because we insert on the right. This right is simply 35.

The insertion orders are as follows:
UPDATE NEW_FAMILLE SET NFM_BD = NFM_BD + 2 WHERE NFM_BD> = 35
UPDATE NEW_FAMILLE SET NFM_BG = NFM_BG + 2 WHERE NFM_BG> = 35
INSERT INTO NEW_FAMILLE (NFM_BG, NFM_BD, NFM_LIB) VALUES (35, 36, 'Roller')

In fact shifts on two units all sides, right or left, without distinction of any kind, whose value is greater than or equal to the base right of the father covered by the insertion.

Another way of looking at things is that the interval father covered by the element to insert into larger of two units to absorb the new son and that this leads all sides to the right of the father a delay of two units.

It is not possible to realise the update in a single complaint. Moreover, if you put a unique constraint on the terminals, it is imperative to begin with the updating of bounds right, then those left and inclusion.

Of course it is better to manage these orders SQL within a transaction.

2.12. Deleting an element of this tree
This can be achieved simply by removing the line corresponding to the element.

Example: abolition of the 'ultralight' (whose NFM_BG is 11):

DELETE FROM NEW_FAMILLE WHERE NFM_BG = 11

However, this leaves a tree with holes in the management unit intervals. This is not beautiful, but more importantly it can affect some queries that we have seen. The correction of this defect is of great simplicity. It is to renumber a portion of the tree. This is done by considering the value of the left edge of the item to delete and thus shift all sides (left or right) greater than the value of two units to the left (-2).
In our example, the left edge worth 11, should be run queries following amendment:

UPDATE NEW_FAMILLE SET NFM_BG = NFM_BG - 2 WHERE NFM_BG> = 11
UPDATE NEW_FAMILLE SET NFM_BD = NFM_BD - 2 WHERE NFM_BD> = 11

By the same token, it is not possible to achieve the updates into a single order and the removal must act first if there is a risk of telescopage values bounds. Moreover, if you put a unique constraint on the terminals, it is imperative to begin with the updating of bounds left, then right ones.

2.13. Deleting a subtree
Removing a tree in full is no more difficult than removing a leaf. It can therefore be achieved by a single complaint or even choose to own and renumber the tree.

For example remove the tree under which the root element 'Terrestrial' Point 22 left and right Point 35:

DELETE FROM NEW_FAMILLE WHERE NFM_BG> = 22 AND NFM_BD <= 35
Renumerotons then terminals located right under the tree removed, with a gap of 35 - 22 + 1, or 14
UPDATE NEW_FAMILLE SET NFM_BD = NFM_BD - 14 WHERE NFM_BD> = 22
UPDATE NEW_FAMILLE SET NFM_BG = NFM_BG - 14 WHERE NFM_BG> 22

Of course the insertion of a subtree (Operation much rarer) is as simple as deleting a subtree.

2.14. The icing on the cake!
Some applications may still appear more difficult, particularly when it comes to search for evidence relating to a level of the tree. For example, the research leaves located at n-1 compared to the level n the reference element. But if such a request may be your daily bread, nothing prevents model the level of element within the table containing the tree. In this case, the table becomes:

CREATE TABLE NEW_FAMILLE (NFM_BG INTEGER, NFM_BD INTEGER, NFM_NV INTEGER, NFM_LIB VARCHAR (16))

NFM_NV containing the level of element, starting with the zero level, meaning the root of the tree. Therefore changes to be made so requests views reflect the level of elements become trivial.

For example, for research leaves level n + 1 compared to the 'Land', the complaint reads:
SELECT * FROM NEW_FAMILLE WHERE NFM_BD - NFM_BG = 1 AND NFM_BG> 22 AND NFM_BD <35 AND NFM_NV = 2

I leave you to guess writing other motions ...

IMPORTANT:
To test the unity of the values of terminals that are in two separate columns, you can use table constraints such as:
CONSTRAINT UNI_BORNE CHECK BORNE_DROITE (VALUE NOT IN (SELECT BORNE_DROITE AS FROM TERMINAL MaTable UNION SELECT ALL BORNE_GAUCHE AS FROM TERMINAL MaTable)) and: CONSTRAINT UNI_BORNE CHECK BORNE_GAUCHE (VALUE NOT IN (SELECT BORNE_DROITE AS FROM TERMINAL MaTable UNION SELECT ALL BORNE_GAUCHE AS FROM TERMINAL MaTable ))

But few RDBMS accept constraints so complex and it is often necessary to go through triggers to implement such integrity.

STOCKEES PROCEDURES FOR HANDLING OF TREES:
Can be found on the site is an example of the main stored procedures written in Transact SQL (MS) to manage the insertion and removal in such a tree.
Here is an example (for SQL Server) management of a tree with standard nomenclature.
order of creation of the table
the two procedures to insert and delete
sight simplifying the presentation of data

-- Creation of the table T_NOMENCLATURE_NMC create table T_NOMENCLATURE_NMC (NMC_ID INTEGER identity, NMC_LIBELLE CHAR (32) not null, NMC_DESCRIPTION VARCHAR (1024) null, NMC_NIVEAU INTEGER not null, NMC_BG INTEGER not null, NMC_BD INTEGER not null, primary key constraint PK_T_NOMENCLATURE_NMC ( NMC_ID))
-- Indexing the table CREATE INDEX NDX_NMC_BG ON T_NOMENCLATURE_NMC (NMC_BG) CREATE INDEX NDX_NMC_BD ON T_NOMENCLATURE_NMC (NMC_BD)

-- Procedure for inclusion in the tree [Frédéric Brouard, Philippe Boucault 25/09/2002] CREATE PROCEDURE SP_INS_NOMENCLATURE @ lib varchar (32), - the wording to include @ desc varchar (1024), - description insert @ id_parent int - Ancestor brother or point of origin of the insertion mode @ char (2) - the insertion: - FA: Son Ainé - FC: Son Cadet - GF: Big Brother - PF: Little Brother, - P: Father AS DECLARE @ OK int DECLARE @ bgp int - simply left parent DECLARE @ bdp int - terminal right parent DECLARE @ nivp int - parent level DECLARE @ bgi int -- Simply left to insert DECLARE @ bdi int - terminal right to insert DECLARE @ nivi int - level insert SET NOCOUNT ON - management of side-effects mode IS IF @ @ lib NULL OR IS NULL OR = @ lib ' 'BEGIN RAISERROR (' Insertion impossible without language or mode! (TABLE T_NOMENCLATURE_NMC) ', 16, 1) RETURN END SET @ mode = UPPER (@ mode) IF NOT (mode = @' FA 'OR @ mode =' FC 'OR @ mode = 'GF' OR @ mode = 'PF' OR @ mode = 'P') BEGIN RAISERROR ( 'Insertion impossible, unknown mode!', 16, 1) RETURN END - starting transaction SET TRANSACTION ISOLATION LEVEL SERIALIZABLE BEGIN TRANSACTION INSERT_NOMENCLATURE - no parent => one case, empty table or insertion of a collateral IF @ id_parent IS NULL BEGIN SELECT OK @ = count (*) FROM T_NOMENCLATURE_NMC OK IF @ @ = 0 OK OR IS NULL BEGIN IF mode = @ 'FA' OR @ mode = 'FC' BEGIN RAISERROR ( 'Insertion impossible in a tree for a son without a father!', 16, 1) GOTO LBL_ERROR RETURN END ELSE BEGIN - the first insertion INSERT INTO T_NOMENCLATURE_NMC (NMC_LIBELLE, NMC_DESCRIPTION, NMC_NIVEAU , NMC_BG, NMC_BD) VALUES (@ lib, @ desc, 0, 1, 2) IF @ @ ERROR <> 0 BEGIN GOTO LBL_ERROR RETURN END COMMIT TRANSACTION INSERT_NOMENCLATURE SELECT @ @ IDENTITY RETURN END END ELSE - Inserting a collateral BEGIN RAISERROR ( 'Insertion impossible in a tree for an unspecified collateral parent!', 16, 1) GOTO LBL_ERROR RETURN END END - The parent still exists? SELECT OK @ = count (*) FROM T_NOMENCLATURE_NMC WHERE NMC_ID = @ id_parent OK IF @ @ = 0 OK OR IS NULL BEGIN RAISERROR ( 'Insertion impossible, the parent n''existe more!', 16, 1) GOTO LBL_ERROR RETURN END -- It was a parent: it recovers its entirety SELECT @ bgp = NMC_BG, @ bdp = NMC_BD, @ nivp = NMC_NIVEAU FROM T_NOMENCLATURE_NMC WHERE NMC_ID = @ id_parent - insertion of a father IF @ mode = 'P' BEGIN -- Shift all right colatéral UPDATE T_NOMENCLATURE_NMC SET NMC_BD = NMC_BD + 2 WHERE NMC_BD> bdp IF @ @ @ ERROR <> 0 BEGIN GOTO LBL_ERROR RETURN END UPDATE T_NOMENCLATURE_NMC SET NMC_BG = NMC_BG + 2 WHERE NMC_BG> bdp IF @ @ @ ERROR < > 0 BEGIN RETURN END GOTO LBL_ERROR - together referred Décalalage down UPDATE T_NOMENCLATURE_NMC SET NMC_BG = NMC_BG + 1, NMC_BD = NMC_BD + 1, NMC_NIVEAU = NMC_NIVEAU + 1 WHERE NMC_BG> = @ bgp AND NMC_BD <= bdp IF @ @ @ ERROR <> 0 BEGIN RETURN END GOTO LBL_ERROR - Insertion of the new father INSERT INTO T_NOMENCLATURE_NMC (NMC_LIBELLE, NMC_DESCRIPTION, NMC_NIVEAU, NMC_BG, NMC_BD) VALUES (@ lib, @ desc, @ nivp, @ bgp, @ bdp + 2) IF @ @ ERROR <> 0 BEGIN RETURN END GOTO LBL_ERROR END - Inserting a big brother mode @ IF = 'GF' BEGIN - Limit sup. UPDATE T_NOMENCLATURE_NMC SET NMC_BD = NMC_BD + 2 WHERE NMC_BD> bgp IF @ @ @ ERROR <> 0 BEGIN RETURN END GOTO LBL_ERROR - Limit inf. UPDATE T_NOMENCLATURE_NMC SET NMC_BG = NMC_BG + 2 WHERE NMC_BG> bgp IF = @ @ @ ERROR <> 0 BEGIN END GOTO LBL_ERROR RETURN SET bgi = @ @ @ bgp SET bdi = @ bgp + 1 = nivi SET @ @ nivp INSERT INTO T_NOMENCLATURE_NMC ( NMC_LIBELLE, NMC_DESCRIPTION, NMC_NIVEAU, NMC_BG, NMC_BD) VALUES (@ lib, @ desc, @ nivi, @ bgi, @ bdi) IF @ @ ERROR <> 0 BEGIN RETURN END GOTO LBL_ERROR END - Inserting a little brother IF @ mode = 'PF' BEGIN - Limit sup. UPDATE T_NOMENCLATURE_NMC SET NMC_BD = NMC_BD + 2 WHERE NMC_BD> bdp IF @ @ @ ERROR <> 0 BEGIN RETURN END GOTO LBL_ERROR - Limit inf. UPDATE T_NOMENCLATURE_NMC SET NMC_BG = NMC_BG + 2 WHERE NMC_BG> = bdp IF @ @ @ ERROR <> 0 BEGIN GOTO LBL_ERROR RETURN END SET @ @ = bgi bdp SET + 1 = @ @ bdi bdp + 2 = nivi SET @ @ nivp INSERT INTO T_NOMENCLATURE_NMC (NMC_LIBELLE, NMC_DESCRIPTION, NMC_NIVEAU, NMC_BG, NMC_BD) VALUES (@ lib, @ desc, @ nivi, @ bgi, @ bdi) IF @ @ ERROR <> 0 BEGIN RETURN END GOTO LBL_ERROR END - Insertion of an elder son IF @ mode = 'FA' BEGIN - Limit sup. UPDATE T_NOMENCLATURE_NMC SET NMC_BD = NMC_BD + 2 WHERE NMC_BD> bgp IF @ @ @ ERROR <> 0 BEGIN RETURN END GOTO LBL_ERROR - Limit inf. UPDATE T_NOMENCLATURE_NMC SET NMC_BG = NMC_BG + 2 WHERE NMC_BG> bgp IF @ @ @ ERROR <> 0 BEGIN GOTO LBL_ERROR RETURN END SET @ bgi = @ bgp + 1 = bdi SET @ @ bgp + 2 = nivi SET @ @ nivp + 1 INSERT INTO T_NOMENCLATURE_NMC (NMC_LIBELLE, NMC_DESCRIPTION, NMC_NIVEAU, NMC_BG, NMC_BD) VALUES (@ lib, @ desc, @ nivi, @ bgi, @ bdi) IF @ @ ERROR <> 0 BEGIN RETURN END GOTO LBL_ERROR END - Inserting a son IF @ cadet mode = 'FC' BEGIN - Limit sup. UPDATE T_NOMENCLATURE_NMC SET NMC_BD = NMC_BD + 2 WHERE NMC_BD> = bdp IF @ @ @ ERROR <> 0 BEGIN RETURN END GOTO LBL_ERROR - Limit inf. UPDATE T_NOMENCLATURE_NMC SET NMC_BG = NMC_BG + 2 WHERE NMC_BG> bdp IF @ @ @ ERROR <> 0 BEGIN GOTO LBL_ERROR RETURN END SET @ bgi bdp SET = @ @ @ = bdi bdp + 1 = nivi SET @ @ nivp + 1 INSERT INTO T_NOMENCLATURE_NMC (NMC_LIBELLE, NMC_DESCRIPTION, NMC_NIVEAU, NMC_BG, NMC_BD) VALUES (@ lib, @ desc, @ nivi, @ bgi, @ bdi) IF @ @ ERROR <> 0 BEGIN RETURN END GOTO LBL_ERROR END - referring to the ID of 'element inserted SELECT @ @ IDENTITY COMMIT TRANSACTION INSERT_NOMENCLATURE RETURN LBL_ERROR: ROLLBACK TRANSACTION INSERT_NOMENCLATURE


-- Procedure of removing the tree [Frédéric Brouard, Philippe Boucault 25/09/2002] CREATE PROCEDURE SP_DEL_NOMENCLATURE @ int id, - identifying the target of suppression @ recurs bit - the method of removal (or non-recursive ): - 0 => removes only on that element and it retains the subtree - 1 => on that element and removes the subtree AS DECLARE @ OK int DECLARE @ bgp int - simply left the target DECLARE @ bdp int - terminal right of the target DECLARE @ int delta - variance introduced by the deletion of subtree SET NOCOUNT ON - management of side effects IF @ id IS NULL BEGIN RAISERROR ( 'Removing impossible without identifying set! " 16, 1) RETURN END IF @ recurs IS NULL BEGIN RAISERROR ( 'Removing impossible without indication of recursion!', 16, 1) RETURN END - starting transaction SET TRANSACTION ISOLATION LEVEL SERIALIZABLE BEGIN TRANSACTION DELETE_NOMENCLATURE - There are always? SELECT OK @ = count (*) FROM T_NOMENCLATURE_NMC WHERE NMC_ID id = @ @ OK IF = 0 @ OK OR IS NULL BEGIN RAISERROR ( 'Removing impossible, a non-existent! (TABLE T_NOMENCLATURE_NMC)', 16, 1) GOTO LBL_ERROR RETURN END -- -- Recovery of terminals target SELECT @ bgp = NMC_BG, @ bdp = NMC_BD FROM T_NOMENCLATURE_NMC WHERE NMC_ID IF id = @ @ @ ERROR <> 0 BEGIN RETURN END GOTO LBL_ERROR - Removing recursive? IF @ recurs = 1 BEGIN - YES! while under the tree should be deleted - Calculation of Delta Delta SET @ @ = bdp - @ bgp + 1 - removal of all elements T_NOMENCLATURE_NMC DELETE FROM WHERE NMC_BG> = @ bgp AND NMC_BD <= bdp IF @ @ @ ERROR < > 0 BEGIN RETURN END GOTO LBL_ERROR - shift terminals left UPDATE T_NOMENCLATURE_NMC SET NMC_BG = NMC_BG - @ delta WHERE NMC_BG> bdp IF @ @ @ ERROR <> 0 BEGIN RETURN END GOTO LBL_ERROR - shift terminals straight UPDATE T_NOMENCLATURE_NMC SET NMC_BD = NMC_BD - @ delta WHERE NMC_BD> bdp IF @ @ @ ERROR <> 0 BEGIN GOTO LBL_ERROR RETURN END END ELSE BEGIN - NOT! removes only one element - removing the element T_NOMENCLATURE_NMC DELETE FROM WHERE NMC_ID IF id = @ @ @ ERROR <> 0 BEGIN RETURN END GOTO LBL_ERROR - gap terminals and level of the tree under the deleted item UPDATE T_NOMENCLATURE_NMC SET NMC_BG = NMC_BG - 1, NMC_BD = NMC_BD - 1, NMC_NIVEAU = NMC_NIVEAU - 1 WHERE NMC_BG> @ bgp AND NMC_BD <bdp IF @ @ @ ERROR <> 0 BEGIN RETURN END GOTO LBL_ERROR - shift terminals left elements located on the right of the deleted item UPDATE T_NOMENCLATURE_NMC SET NMC_BG = NMC_BG - 2 WHERE NMC_BG> bdp IF @ @ @ ERROR <> 0 BEGIN RETURN END GOTO LBL_ERROR - shift terminals straight elements located on the right of the deleted item UPDATE T_NOMENCLATURE_NMC SET NMC_BD = NMC_BD - 2 WHERE NMC_BD> bdp IF @ @ @ ERROR <> 0 BEGIN GOTO LBL_ERROR RETURN END COMMIT END TRANSACTION DELETE_NOMENCLATURE RETURN LBL_ERROR: ROLLBACK TRANSACTION DELETE_NOMENCLATURE RETURN


-- Carrying out the request for summary: CREATE VIEW V_NOMENCLATURE_NMC AS SELECT NMC_ID, CAST (SPACE (NMC_NIVEAU) + NMC_LIBELLE AS VARCHAR (64)) AS NMC_LIBELLE, NMC_NIVEAU, NMC_BG, NMC_BD, (SELECT COUNT (*) FROM T_NOMENCLATURE_NMC T2 WHERE T2 . NMC_BG> T1.NMC_BG AND T2.NMC_BD <T1.NMC_BD) AS NMC_NBR_DESCENDANT, NMC_DESCRIPTION FROM T_NOMENCLATURE_NMC T1

-- Thursday test data: insertion in the tree of the following nomenclature
METHODS
    MERISE
       Power Designor
    UML
       Rational Rose
LANGUAGES
    Pascal
       Delphi
    Basic
       MS Visual Basic
    ASP
    PHP
    SQL Intégrés
       MS Transact SQL
       Oracle PL/SQL
       InterBase ISQL
SGBDR
    Microsoft
       Access
       SQL Server
          SQL Server 7
          SQL Server 2000
          MSDE
    Borland
       InterBase
    Oracle
    IBM
       DB2

SP_INS_NOMENCLATURE 'METHODES', NULL, NULL, 'GF'

NMC_ID NMC_LIBELLE NMC_NIVEAU NMC_BG NMC_BD NMC_NBR_DESCENDANT
----------- -------------------------------- ----------- ----------- ----------- ------------------
1 METHODES 0 1 2 0

SP_INS_NOMENCLATURE 'MERISE', NULL, 1 , 'FA'

NMC_ID NMC_LIBELLE NMC_NIVEAU NMC_BG NMC_BD NMC_NBR_DESCENDANT
----------- -------------------------------- ----------- ----------- ----------- ------------------
1 METHODES 0 1 4 1
2 MERISE 1 2 3 0

SP_INS_NOMENCLATURE 'Power Designor', NULL, 2 , 'FA'

NMC_ID NMC_LIBELLE NMC_NIVEAU NMC_BG NMC_BD NMC_NBR_DESCENDANT
----------- -------------------------------- ----------- ----------- ----------- ------------------
1 METHODES 0 1 6 2
2 MERISE 1 2 5 1
3 Power Designor 2 3 4 0

SP_INS_NOMENCLATURE 'Rational Rose', NULL, 3 , 'PF'

NMC_ID NMC_LIBELLE NMC_NIVEAU NMC_BG NMC_BD NMC_NBR_DESCENDANT
----------- -------------------------------- ----------- ----------- ----------- ------------------
1 METHODES 0 1 8 3
2 MERISE 1 2 7 2
3 Power Designor 2 3 4 0
4 Rational Rose 2 5 6 0

SP_INS_NOMENCLATURE 'UML', NULL, 4 , 'P'

NMC_ID NMC_LIBELLE NMC_NIVEAU NMC_BG NMC_BD NMC_NBR_DESCENDANT
----------- -------------------------------- ----------- ----------- ----------- ------------------
1 METHODES 0 1 10 4
2 MERISE 1 2 9 3
3 Power Designor 2 3 4 0
5 UML 2 5 8 1
4 Rational Rose 3 6 7 0

SP_DEL_NOMENCLATURE 5, 1

NMC_ID NMC_LIBELLE NMC_NIVEAU NMC_BG NMC_BD NMC_NBR_DESCENDANT
----------- -------------------------------- ----------- ----------- ----------- ------------------
1 METHODES 0 1 6 2
2 MERISE 1 2 5 1
3 Power Designor 2 3 4 0

SP_INS_NOMENCLATURE 'UML', NULL, 2 , 'PF'

NMC_ID NMC_LIBELLE NMC_NIVEAU NMC_BG NMC_BD NMC_NBR_DESCENDANT
----------- -------------------------------- ----------- ----------- ----------- ------------------
1 METHODES 0 1 8 3
2 MERISE 1 2 5 1
3 Power Designor 2 3 4 0
6 UML 1 6 7 0

SP_INS_NOMENCLATURE 'Rational Rose', NULL, 6 , 'FA'

NMC_ID NMC_LIBELLE NMC_NIVEAU NMC_BG NMC_BD NMC_NBR_DESCENDANT
----------- -------------------------------- ----------- ----------- ----------- ------------------
1 METHODES 0 1 10 4
2 MERISE 1 2 5 1
3 Power Designor 2 3 4 0
6 UML 1 6 9 1
7 Rational Rose 2 7 8 0
etc...
La cerise sur le gâteau...
Voici une vue permettant de réaliser un flux XML de l'arbre :

CREATE VIEW V_TREE_XML_NOMENCLATURE_TXN AS SELECT TOP 100 PERCENT WITH TIES BORNE, LIGNE FROM (SELECT -1 AS BORNE, CAST('<?xml version="1.0" encoding="ISO-8859-1"?>' AS VARCHAR(1024)) AS LIGNE FROM V_NOMENCLATURE_NMC WHERE NMC_ID = (SELECT MIN(NMC_ID) FROM V_NOMENCLATURE_NMC) UNION SELECT 0 AS NMC_BG, CAST('<document>' AS VARCHAR(1024)) AS LIGNE FROM V_NOMENCLATURE_NMC WHERE NMC_ID = (SELECT MIN(NMC_ID) FROM V_NOMENCLATURE_NMC) UNION SELECT NMC_BG AS BORNE, SPACE(NMC_NIVEAU) + '<TreeNode><Data LV="'+ CAST(NMC_NIVEAU AS VARCHAR(5))+'"' + ' BG="'+CAST(NMC_BG AS VARCHAR(5))+'"' + ' BD="'+CAST(NMC_BD AS VARCHAR(5))+'"' + ' ID="'+CAST(NMC_ID AS VARCHAR(5))+'"><Name>' + RTRIM(LTRIM(NMC_LIBELLE))+'</Name>' AS LIGNE FROM V_NOMENCLATURE_NMC UNION SELECT NMC_BD, CAST(SPACE(NMC_NIVEAU) + '</Data></TreeNode>' AS VARCHAR(1024)) FROM V_NOMENCLATURE_NMC UNION SELECT (SELECT MAX(NMC_BD) + 1 FROM V_NOMENCLATURE_NMC) AS NMC_BG, CAST('</document>' AS VARCHAR(1024)) AS LIGNE FROM V_NOMENCLATURE_NMC WHERE NMC_ID = (SELECT MIN(NMC_ID) FROM V_NOMENCLATURE_NMC)) T ORDER BY BORNE


SELECT LIGNE FROM V_TREE_XML_NOMENCLATURE_TXN

LIGNE
----------------------------------------------------------------------------------------------------
<?xml version="1.0" encoding="ISO-8859-1"?>
<document>
<TreeNode><Data LV="0" BG="1" BD="10" ID="1"><Name>METHODES</Name>
  <TreeNode><Data LV="1" BG="2" BD="5" ID="2"><Name>MERISE</Name>
   <TreeNode><Data LV="2" BG="3" BD="4" ID="3"><Name>Power Designor</Name>
   </Data></TreeNode>
  </Data></TreeNode>
  <TreeNode><Data LV="1" BG="6" BD="9" ID="6"><Name>UML</Name>
   <TreeNode><Data LV="2" BG="7" BD="8" ID="7"><Name>Rational Rose</Name>
   </Data></TreeNode>
  </Data></TreeNode>
</Data></TreeNode>
</document>