|
Preamble
Here is a tree whose data represents families of vehicles:  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 FAMILLE
(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 FAMILLE WHERE FAM_ID = (SELECT FAM_PERE FROM FAMILLE WHERE FAM_ID = 12) | FAM_ID FAM_LIB FAM_PERE
----------- ---------------- -----------
3 Aerien 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
reponse = reponse + ', ' + (SELECT FAM_LIB
FROM FAMILLE
WHERE FAM_ID = ID)
if id = 0
then
return
else
id = (SELECT FAM_PERE
FROM FAMILLE
WHERE FAM_ID = 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:
* Sheets 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: 
Of this figure, we can already see that:
* The number of assigned number is double the number of elements
* All the leaves have a long interval 1 (Point right - simply left = 1)
* A contrario, 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:  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
11 12 ULM
14 15 Military
16 17 Tourism
18 19 Civil
23 24 Cycling
25 26 Car
... | 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
----------- ----------- ----------------
23 24 Cycling
25 26 Car
27 28 Truck
30 31 Side-car
32 33 Trail |
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
22 35 Terrestrial
29 34 Moto
36 43 Marin | 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
22 35 Terrestrial
29 34 Moto
36 43 Marin | 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
----------- ----------- ----------------
23 24 Cycling
25 26 Car
27 28 Truck
29 34 Moto
30 31 Side-car
32 33 Trail | 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
----------- ----------- ----------------
22 35 Terrestrial
23 24 Cycling
25 26 Car
27 28 Truck
29 34 Moto
30 31 Side-car
32 33 Trail | 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
11 12 ULM
13 20 Aircraft
14 15 Military
16 17 Tourism
18 19 Civil
36 43 Marin
37 38 Plate Windsurfing
39 40 Paquebot
41 42 Sailboat |
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
11 12 ULM
13 20 Aircraft
14 15 Military
16 17 Tourism
18 19 Civil
36 43 Marin
37 38 Plate Windsurfing
39 40 Paquebot
41 42 Sailboat | 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
24 37 Terrestrial | 2.8. Finding the root of the tree
If all insertions are always made by the right, the root has an interval whose left side is a: SELECT *
FROM NEW_FAMILLE
WHERE NFM_BG = 1 Otherwise, one can find the root of the application, meaning that the research on the element of a length of the interval to a unit is nearly double the number of elements: SELECT *
FROM NEW_FAMILLE
WHERE (NFM_BD - NFM_BG + 1) / 2 = (SELECT COUNT(*)
FROM NEW_FAMILLE) | NFM_BG NFM_BD NFM_LIB
----------- ----------- ----------------
1 44 Transport | It may also simply seek the element that has the greatest length intervals: SELECT *
FROM NEW_FAMILLE
WHERE (NFM_BD - NFM_BG) = (SELECT MAX(NFM_BD - NFM_BG)
FROM NEW_FAMILLE Who, of course, leads to the same result.
2.9. Counting leaves
These are many elements for which the length of the interval is one: SELECT COUNT(*) AS FEUILLES
FROM NEW_FAMILLE
WHERE NFM_BG = NFM_BD -1 | FEUILLES
-----------
16 |
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 NOEUDS
FROM NEW_FAMILLE
WHERE NFM_BG <> NFM_BD -1 | NOEUDS
-----------
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 téléscopage 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 BORNE
FROM MaTable
UNION ALL
SELECT BORNE_GAUCHE AS BORNE
FROM MaTable))
et :
CONSTRAINT UNI_BORNE CHECK BORNE_GAUCHE
(VALUE NOT IN
(SELECT BORNE_DROITE AS BORNE
FROM MaTable
UNION ALL
SELECT BORNE_GAUCHE AS BORNE
FROM 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 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,
constraint PK_T_NOMENCLATURE_NMC primary key (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
CREATE PROCEDURE SP_INS_NOMENCLATURE
@lib varchar(32), - the wording to
@desc varchar(1024), - description insert
@id_parent int, - Ancestor brother or point of origin of the insertion mode
@mode char(2) - the insertion
Son Aine
Son Cadet
Big Brother
Little Brother
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 @mode IS NULL OR @lib 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, mode inconnu !', 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
IF @OK = 0 OR @OK 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 dans un arbre pour un collatéral sans précision du 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
IF @OK = 0 OR @OK IS NULL
BEGIN
RAISERROR ('Insertion impossible, le parent n''existe plus !', 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 colateral
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
GOTO LBL_ERROR
RETURN
END
- together referred Decalalage 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
GOTO LBL_ERROR
RETURN
END
- 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
GOTO LBL_ERROR
RETURN
END
END
- Inserting a big brother mode
IF @mode = 'GF'
BEGIN
- Limit sup.
UPDATE T_NOMENCLATURE_NMC
SET NMC_BD = NMC_BD + 2
WHERE NMC_BD > @bgp
IF @@ERROR <> 0
BEGIN
GOTO LBL_ERROR
RETURN
END
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
SET @bdi = @bgp + 1
SET @nivi = @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
GOTO LBL_ERROR
RETURN
END
END
- Inserting a little brother
IF @mode = 'PF'
BEGIN
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
GOTO LBL_ERROR
RETURN
END
SET @bgi = @bdp + 1
SET @bdi = @bdp + 2
SET @nivi = @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
GOTO LBL_ERROR
RETURN
END
END
- Insertion of an elder son
IF @mode = 'FA'
BEGIN
UPDATE T_NOMENCLATURE_NMC
SET NMC_BD = NMC_BD + 2
WHERE NMC_BD > @bgp
IF @@ERROR <> 0
BEGIN
GOTO LBL_ERROR
RETURN
END
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
SET @bdi = @bgp + 2
SET @nivi = @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
GOTO LBL_ERROR
RETURN
END
END
- Inserting a son
IF @mode = 'FC'
BEGIN
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
GOTO LBL_ERROR
RETURN
END
SET @bgi = @bdp
SET @bdi = @bdp + 1
SET @nivi = @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
GOTO LBL_ERROR
RETURN
END
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
CREATE PROCEDURE SP_DEL_NOMENCLATURE
@id int, - identifying the target of suppression
@recurs bit - the method of removal (or non-recursive ):
removes only on that element and it retains the subtree
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 @delta int - 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
IF @OK = 0 OR @OK 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 = @id
IF @@ERROR <> 0
BEGIN
GOTO LBL_ERROR
RETURN
END
- Removing recursive?
IF @recurs = 1
BEGIN
- YES! while under the tree should be deleted
- Calculation of Delta Delta
SET @delta = @bdp - @bgp + 1
- removal of all elements
DELETE FROM T_NOMENCLATURE_NMC
WHERE NMC_BG >= @bgp
AND NMC_BD <= @bdp
IF @@ERROR <> 0
BEGIN
GOTO LBL_ERROR
RETURN
END
- shift terminals left
UPDATE T_NOMENCLATURE_NMC
SET NMC_BG = NMC_BG - @delta
WHERE NMC_BG > @bdp
IF @@ERROR <> 0
BEGIN
GOTO LBL_ERROR
RETURN
END
- 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
DELETE FROM T_NOMENCLATURE_NMC
WHERE NMC_ID = @id
IF @@ERROR <> 0
BEGIN
GOTO LBL_ERROR
RETURN
END
- 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
GOTO LBL_ERROR
RETURN
END
- gap terminals and level of the tree under the deleted item
UPDATE T_NOMENCLATURE_NMC
SET NMC_BG = NMC_BG - 2
WHERE NMC_BG > @bdp
IF @@ERROR <> 0
BEGIN
GOTO LBL_ERROR
RETURN
END
- shift terminals left 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
END
COMMIT 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
METHODES
MERISE
Power Designor
UML
Rational Rose
LANGAGES
Pascal
Delphi
Basic
MS Visual Basic
ASP
PHP
SQL Integres
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... | The icing on the cake ...
Here is a view to achieve a stream of XML tree: 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> |
|
