| Subject | Re: [ib-support] Tree as adjaceny List conversion to nested set. |
|---|---|
| Author | Jem Rayfield |
| Post date | 2003-02-07T10:06:21Z |
John,
Please find a solution for converting a adjacency tree list to a hash set and
a couple of hash-set tree functions for finding sub/parent trees.
I hope its of some use. If you spot anything you would change please let me know.
Cheers
Jem Rayfield
/* Moves Adjacency list to nested set implementation */
/* Tree operations much faster and removes redundancy */
/* Calculating sub/parent trees quicker */
/* Adjacency list */
CREATE TABLE COST_CENTER_IMPORT (
COST_CENTER CHAR( 10 ) NOT NULL PRIMARY KEY,
PARENT_COST_CENTER CHAR( 10 ) DEFAULT NULL,
DESCRIPTION VARCHAR( 255 )
);
/* Nested set implementation */
CREATE TABLE COST_CENTER_TREE (
COST_CENTRE CHAR( 10 ) NOT NULL,
LEFT_ID INTEGER NOT NULL UNIQUE CHECK( LEFT_ID > 0 ),
RIGHT_ID INTEGER NOT NULL UNIQUE CHECK( RIGHT_ID > 1 ),
CONSTRAINT order_ok CHECK( LEFT_ID < RIGHT_ID )
);
/* Get Sub-Set from nested set */
CREATE PROCEDURE GET_SUB_TREE
(
COST_CENTER_PASSED CHAR( 10 )
)
RETURNS
(
COST_CENTER CHAR( 10 )
)
AS
BEGIN
FOR
SELECT P1.COST_CENTRE
FROM COST_CENTER_TREE P1, COST_CENTER_TREE P2
WHERE P1.LEFT_ID BETWEEN P2.LEFT_ID AND P2.RIGHT_ID
AND P2.COST_CENTRE = :COST_CENTER_PASSED
INTO
:COST_CENTER
DO
BEGIN
SUSPEND;
END
END
/* Get a parent tree from nested set */
CREATE PROCEDURE GET_PARENT_TREE
(
COST_CENTER_PASSED CHAR( 10 )
)
RETURNS
(
COST_CENTER CHAR( 10 )
)
AS
BEGIN
FOR
SELECT
P2.COST_CENTRE
FROM
COST_CENTER_TREE P1, COST_CENTER_TREE P2
WHERE
P1.LEFT_ID BETWEEN P2.LEFT_ID AND P2.RIGHT_ID
AND
P1.COST_CENTRE = :COST_CENTER_PASSED
INTO
:COST_CENTER
DO
BEGIN
SUSPEND;
END
END
/* Table for adjacent list conversion temp calc table */
CREATE TABLE COST_CENTER_STACK (
STACK_TOP INTEGER NOT NULL,
COST_CENTER CHAR(10) NOT NULL,
LEFT_ID INTEGER,
RIGHT_ID INTEGER
);
/* moves data from stack to set */
/* delete all stack data */
CREATE PROCEDURE MOVE_STACK_TO_SET
AS
DECLARE VARIABLE COST_CENTER CHAR( 10 );
DECLARE VARIABLE LEFT_ID INTEGER;
DECLARE VARIABLE RIGHT_ID INTEGER;
BEGIN
FOR
SELECT
COST_CENTER, LEFT_ID, RIGHT_ID
FROM
COST_CENTER_STACK
INTO
:COST_CENTER, :LEFT_ID, :RIGHT_ID
DO
BEGIN
INSERT INTO COST_CENTER_TREE
( COST_CENTRE, LEFT_ID, RIGHT_ID )
VALUES
( :COST_CENTER, :LEFT_ID, :RIGHT_ID );
END
DELETE FROM COST_CENTER_STACK;
END;
/* Convert the adjacency list into a nested set */
CREATE PROCEDURE LIST_TO_SET
AS
DECLARE VARIABLE COUNTER INTEGER;
DECLARE VARIABLE MAX_COUNTER INTEGER;
DECLARE VARIABLE CURRENT_STACK_TOP INTEGER;
DECLARE VARIABLE PARENT CHAR( 10 );
DECLARE VARIABLE ANY_CHILDREN INTEGER;
DECLARE VARIABLE TREE_COST_CENTER CHAR( 10 );
BEGIN
/* delete all set data */
DELETE FROM COST_CENTER_TREE;
COUNTER = 2;
CURRENT_STACK_TOP = 1;
/* Get Maximum leaf right_id */
SELECT
COUNT( * )
FROM
COST_CENTER_IMPORT
INTO
:MAX_COUNTER;
MAX_COUNTER = MAX_COUNTER * 2;
/* Get the root node from the tree implementation */
SELECT
COST_CENTER
FROM
COST_CENTER_IMPORT
WHERE
PARENT_COST_CENTER IS NULL
INTO
:PARENT;
/* Insert tree root node into nested set */
INSERT INTO COST_CENTER_STACK
( STACK_TOP, COST_CENTER, LEFT_ID, RIGHT_ID )
VALUES
( 1, :PARENT, 1, :MAX_COUNTER );
/* Delete the root node from the tree */
DELETE FROM
COST_CENTER_IMPORT
WHERE
PARENT_COST_CENTER IS NULL;
/* Create the nodes and assign right/left ids */
WHILE ( COUNTER <= ( MAX_COUNTER - 1 ) )
DO
BEGIN
ANY_CHILDREN = 0;
/* Are there any children for current node */
SELECT
COUNT( * ) , MIN( T1.COST_CENTER)
FROM
COST_CENTER_STACK S1,
COST_CENTER_IMPORT T1
WHERE
S1.COST_CENTER = T1.PARENT_COST_CENTER
AND
S1.STACK_TOP = :CURRENT_STACK_TOP
INTO
:ANY_CHILDREN, :TREE_COST_CENTER;
/* found some children so add to nested set */
IF ( ANY_CHILDREN > 0 ) THEN
BEGIN
/* Grab Tree node and add as set element */
/* Set the LEFT_ID value */
INSERT INTO COST_CENTER_STACK
( STACK_TOP, COST_CENTER, LEFT_ID )
VALUES
( :CURRENT_STACK_TOP + 1, :TREE_COST_CENTER, :COUNTER );
/* Remove Tree node */
DELETE FROM COST_CENTER_IMPORT
WHERE
COST_CENTER = :TREE_COST_CENTER;
/* Inc the counters */
COUNTER = :COUNTER + 1;
CURRENT_STACK_TOP = :CURRENT_STACK_TOP + 1;
END
ELSE
BEGIN
/* Pop items off the stack */
/* Set the RIGHT_ID value */
UPDATE
COST_CENTER_STACK
SET
RIGHT_ID = :COUNTER,
STACK_TOP = -STACK_TOP
WHERE
STACK_TOP = :CURRENT_STACK_TOP;
COUNTER = :COUNTER + 1;
CURRENT_STACK_TOP = :CURRENT_STACK_TOP - 1;
END
END
EXECUTE PROCEDURE MOVE_STACK_TO_SET;
END
/* -- Test Data for tree -- */
INSERT INTO "COST_CENTER_IMPORT" ("COST_CENTER", "PARENT_COST_CENTER", "DESCRIPTION") VALUES ('A', NULL, NULL);
INSERT INTO "COST_CENTER_IMPORT" ("COST_CENTER", "PARENT_COST_CENTER", "DESCRIPTION") VALUES ('B', 'A', NULL);
INSERT INTO "COST_CENTER_IMPORT" ("COST_CENTER", "PARENT_COST_CENTER", "DESCRIPTION") VALUES ('C', 'A', NULL);
INSERT INTO "COST_CENTER_IMPORT" ("COST_CENTER", "PARENT_COST_CENTER", "DESCRIPTION") VALUES ('D', 'B', NULL);
INSERT INTO "COST_CENTER_IMPORT" ("COST_CENTER", "PARENT_COST_CENTER", "DESCRIPTION") VALUES ('E', 'B', NULL);
INSERT INTO "COST_CENTER_IMPORT" ("COST_CENTER", "PARENT_COST_CENTER", "DESCRIPTION") VALUES ('F', 'B', NULL);
INSERT INTO "COST_CENTER_IMPORT" ("COST_CENTER", "PARENT_COST_CENTER", "DESCRIPTION") VALUES ('G', 'C', NULL);
INSERT INTO "COST_CENTER_IMPORT" ("COST_CENTER", "PARENT_COST_CENTER", "DESCRIPTION") VALUES ('H', 'C', NULL);
INSERT INTO "COST_CENTER_IMPORT" ("COST_CENTER", "PARENT_COST_CENTER", "DESCRIPTION") VALUES ('I', 'D', NULL);
INSERT INTO "COST_CENTER_IMPORT" ("COST_CENTER", "PARENT_COST_CENTER", "DESCRIPTION") VALUES ('J', 'D', NULL);
INSERT INTO "COST_CENTER_IMPORT" ("COST_CENTER", "PARENT_COST_CENTER", "DESCRIPTION") VALUES ('K', 'I', NULL);
INSERT INTO "COST_CENTER_IMPORT" ("COST_CENTER", "PARENT_COST_CENTER", "DESCRIPTION") VALUES ('L', 'I', NULL);
INSERT INTO "COST_CENTER_IMPORT" ("COST_CENTER", "PARENT_COST_CENTER", "DESCRIPTION") VALUES ('M', 'H', NULL);
INSERT INTO "COST_CENTER_IMPORT" ("COST_CENTER", "PARENT_COST_CENTER", "DESCRIPTION") VALUES ('N', 'H', NULL);
INSERT INTO "COST_CENTER_IMPORT" ("COST_CENTER", "PARENT_COST_CENTER", "DESCRIPTION") VALUES ('O', 'N', NULL);
/* -- Testing -- */
/* Perform the conversion from tree to nested set */
EXECUTE PROCEDURE LIST_TO_SET;
/* Collect a sub tree from nested set */
SELECT * FROM GET_SUB_TREE( 'C' );
/* NOTE Results should be C, G, H, M, N, O */
/* Collect parent tree from nested set */
SELECT * FROM GET_PARENT_TREE( 'C' );
/* Should return C, A */
John Croft <jcroft@...>
06/02/2003 11:42 AM EST
Please respond to ib-support
To: ib-support@yahoogroups.com
cc:
bcc:
Subject: Re: [ib-support] Tree as adjaceny List conversion to nested set.
Jem -
Here is the procedure along with the tables that it works from. My tree
is slightly different in that sub-nodes on each level are ordered so you
will need to adjust for that. I would like to see your final results as
I might have a need for that in the future.
- John Croft
CREATE TABLE TREE_TBL (
NODE_ID INTEGER NOT NULL,
NODE_PRIOR INTEGER DEFAULT 0 NOT NULL,
NODE_NEXT INTEGER DEFAULT 0 NOT NULL,
PARENT_NODE_ID INTEGER DEFAULT 0 NOT NULL
);
CREATE TABLE NODE_TBL (
NODE_ID INTEGER NOT NULL,
NODE_NAME CHAR(64) CHARACTER SET NONE NOT NULL
);
BEGIN
NODE_LEVEL = 0;
NODE_LEVEL_ORDER = 0;
current_node_id = 0;
parent_node_id = 0;
next_node_id = 0;
prior_node_id = 0;
leaf = 0;
SELECT MIN(NODE_ID)
FROM TREE_TBL
WHERE PARENT_NODE_ID = 0 AND
NODE_PRIOR = 0
INTO :STARTING_NODE_ID;
WHILE (:STARTING_NODE_ID IS NOT NULL)
DO
BEGIN
/* Select starting node */
SELECT t.node_id, t.node_name, tt.node_next
FROM node_tbl t LEFT OUTER JOIN TREE_TBL tt
ON t.node_id = tt.node_id
WHERE t.node_id = :STARTING_NODE_ID
INTO :node_id, :node_name, :next_node_id;
IF (leaf = 0) THEN
NODE_LEVEL = NODE_LEVEL + 1;
ELSE
leaf = 0;
NODE_LEVEL_ORDER = NODE_LEVEL_ORDER + 1;
SUSPEND;
/* Assign current node */
current_node_id = STARTING_NODE_ID;
IF (:node_id IS NOT NULL) THEN
BEGIN
SELECT min(c.node_id)
FROM TREE_TBL c
WHERE (c.parent_node_id = :STARTING_NODE_ID) AND
(c.node_prior = 0)
INTO :STARTING_NODE_ID;
IF (:STARTING_NODE_ID IS NOT NULL) THEN
BEGIN
leaf = 0;
parent_node_id = current_node_id;
prior_node_id = STARTING_NODE_ID;
END
ELSE
BEGIN
leaf = 1;
SELECT nc.node_id
FROM TREE_TBL nc
WHERE nc.parent_node_id = :parent_node_id AND
nc.node_id = :next_node_id
INTO :STARTING_NODE_ID;
IF (:STARTING_NODE_ID IS NOT NULL) THEN
BEGIN
prior_node_id = STARTING_NODE_ID;
END
ELSE
BEGIN
WHILE ((:STARTING_NODE_ID IS NULL) AND (NODE_LEVEL > 1))
DO
BEGIN
SELECT nn.parent_node_id, nn.node_next
FROM TREE_TBL nn
WHERE nn.node_id = :parent_node_id
INTO :parent_node_id, :next_node_id;
SELECT st.node_id
FROM TREE_TBL st
WHERE st.parent_node_id = :parent_node_id AND
st.node_id = :next_node_id
INTO :STARTING_NODE_ID;
NODE_LEVEL = NODE_LEVEL - 1;
IF (:STARTING_NODE_ID IS NOT NULL) THEN
prior_node_id = STARTING_NODE_ID;
END
END
END
END
END
END
Jem Rayfield wrote:
ib-support-unsubscribe@egroups.com
Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
Jem Rayfield
Technical Consultant
Deutsche Bank [/]
CIB - IT Infrastructure
Corporate and Investment Bank (CIB)
London
t: +44(20)754-51943
John Croft
<jcroft@compsolve To: ib-support@yahoogroups.com
.com> cc:
Subject: Re: [ib-support] Tree as adjaceny List conversion to nested set.
06/02/2003 16:42
Please respond to
ib-support
Jem -
Here is the procedure along with the tables that it works from. My tree
is slightly different in that sub-nodes on each level are ordered so you
will need to adjust for that. I would like to see your final results as
I might have a need for that in the future.
- John Croft
CREATE TABLE TREE_TBL (
NODE_ID INTEGER NOT NULL,
NODE_PRIOR INTEGER DEFAULT 0 NOT NULL,
NODE_NEXT INTEGER DEFAULT 0 NOT NULL,
PARENT_NODE_ID INTEGER DEFAULT 0 NOT NULL
);
CREATE TABLE NODE_TBL (
NODE_ID INTEGER NOT NULL,
NODE_NAME CHAR(64) CHARACTER SET NONE NOT NULL
);
BEGIN
NODE_LEVEL = 0;
NODE_LEVEL_ORDER = 0;
current_node_id = 0;
parent_node_id = 0;
next_node_id = 0;
prior_node_id = 0;
leaf = 0;
SELECT MIN(NODE_ID)
FROM TREE_TBL
WHERE PARENT_NODE_ID = 0 AND
NODE_PRIOR = 0
INTO :STARTING_NODE_ID;
WHILE (:STARTING_NODE_ID IS NOT NULL)
DO
BEGIN
/* Select starting node */
SELECT t.node_id, t.node_name, tt.node_next
FROM node_tbl t LEFT OUTER JOIN TREE_TBL tt
ON t.node_id = tt.node_id
WHERE t.node_id = :STARTING_NODE_ID
INTO :node_id, :node_name, :next_node_id;
IF (leaf = 0) THEN
NODE_LEVEL = NODE_LEVEL + 1;
ELSE
leaf = 0;
NODE_LEVEL_ORDER = NODE_LEVEL_ORDER + 1;
SUSPEND;
/* Assign current node */
current_node_id = STARTING_NODE_ID;
IF (:node_id IS NOT NULL) THEN
BEGIN
SELECT min(c.node_id)
FROM TREE_TBL c
WHERE (c.parent_node_id = :STARTING_NODE_ID) AND
(c.node_prior = 0)
INTO :STARTING_NODE_ID;
IF (:STARTING_NODE_ID IS NOT NULL) THEN
BEGIN
leaf = 0;
parent_node_id = current_node_id;
prior_node_id = STARTING_NODE_ID;
END
ELSE
BEGIN
leaf = 1;
SELECT nc.node_id
FROM TREE_TBL nc
WHERE nc.parent_node_id = :parent_node_id AND
nc.node_id = :next_node_id
INTO :STARTING_NODE_ID;
IF (:STARTING_NODE_ID IS NOT NULL) THEN
BEGIN
prior_node_id = STARTING_NODE_ID;
END
ELSE
BEGIN
WHILE ((:STARTING_NODE_ID IS NULL) AND (NODE_LEVEL > 1))
DO
BEGIN
SELECT nn.parent_node_id, nn.node_next
FROM TREE_TBL nn
WHERE nn.node_id = :parent_node_id
INTO :parent_node_id, :next_node_id;
SELECT st.node_id
FROM TREE_TBL st
WHERE st.parent_node_id = :parent_node_id AND
st.node_id = :next_node_id
INTO :STARTING_NODE_ID;
NODE_LEVEL = NODE_LEVEL - 1;
IF (:STARTING_NODE_ID IS NOT NULL) THEN
prior_node_id = STARTING_NODE_ID;
END
END
END
END
END
END
Jem Rayfield wrote:
ib-support-unsubscribe@egroups.com
Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
--
This e-mail may contain confidential and/or privileged information. If you are not the intended recipient (or have received this e-mail in error) please notify the sender immediately and destroy this e-mail. Any unauthorized copying, disclosure or distribution of the material in this e-mail is strictly forbidden.
Please find a solution for converting a adjacency tree list to a hash set and
a couple of hash-set tree functions for finding sub/parent trees.
I hope its of some use. If you spot anything you would change please let me know.
Cheers
Jem Rayfield
/* Moves Adjacency list to nested set implementation */
/* Tree operations much faster and removes redundancy */
/* Calculating sub/parent trees quicker */
/* Adjacency list */
CREATE TABLE COST_CENTER_IMPORT (
COST_CENTER CHAR( 10 ) NOT NULL PRIMARY KEY,
PARENT_COST_CENTER CHAR( 10 ) DEFAULT NULL,
DESCRIPTION VARCHAR( 255 )
);
/* Nested set implementation */
CREATE TABLE COST_CENTER_TREE (
COST_CENTRE CHAR( 10 ) NOT NULL,
LEFT_ID INTEGER NOT NULL UNIQUE CHECK( LEFT_ID > 0 ),
RIGHT_ID INTEGER NOT NULL UNIQUE CHECK( RIGHT_ID > 1 ),
CONSTRAINT order_ok CHECK( LEFT_ID < RIGHT_ID )
);
/* Get Sub-Set from nested set */
CREATE PROCEDURE GET_SUB_TREE
(
COST_CENTER_PASSED CHAR( 10 )
)
RETURNS
(
COST_CENTER CHAR( 10 )
)
AS
BEGIN
FOR
SELECT P1.COST_CENTRE
FROM COST_CENTER_TREE P1, COST_CENTER_TREE P2
WHERE P1.LEFT_ID BETWEEN P2.LEFT_ID AND P2.RIGHT_ID
AND P2.COST_CENTRE = :COST_CENTER_PASSED
INTO
:COST_CENTER
DO
BEGIN
SUSPEND;
END
END
/* Get a parent tree from nested set */
CREATE PROCEDURE GET_PARENT_TREE
(
COST_CENTER_PASSED CHAR( 10 )
)
RETURNS
(
COST_CENTER CHAR( 10 )
)
AS
BEGIN
FOR
SELECT
P2.COST_CENTRE
FROM
COST_CENTER_TREE P1, COST_CENTER_TREE P2
WHERE
P1.LEFT_ID BETWEEN P2.LEFT_ID AND P2.RIGHT_ID
AND
P1.COST_CENTRE = :COST_CENTER_PASSED
INTO
:COST_CENTER
DO
BEGIN
SUSPEND;
END
END
/* Table for adjacent list conversion temp calc table */
CREATE TABLE COST_CENTER_STACK (
STACK_TOP INTEGER NOT NULL,
COST_CENTER CHAR(10) NOT NULL,
LEFT_ID INTEGER,
RIGHT_ID INTEGER
);
/* moves data from stack to set */
/* delete all stack data */
CREATE PROCEDURE MOVE_STACK_TO_SET
AS
DECLARE VARIABLE COST_CENTER CHAR( 10 );
DECLARE VARIABLE LEFT_ID INTEGER;
DECLARE VARIABLE RIGHT_ID INTEGER;
BEGIN
FOR
SELECT
COST_CENTER, LEFT_ID, RIGHT_ID
FROM
COST_CENTER_STACK
INTO
:COST_CENTER, :LEFT_ID, :RIGHT_ID
DO
BEGIN
INSERT INTO COST_CENTER_TREE
( COST_CENTRE, LEFT_ID, RIGHT_ID )
VALUES
( :COST_CENTER, :LEFT_ID, :RIGHT_ID );
END
DELETE FROM COST_CENTER_STACK;
END;
/* Convert the adjacency list into a nested set */
CREATE PROCEDURE LIST_TO_SET
AS
DECLARE VARIABLE COUNTER INTEGER;
DECLARE VARIABLE MAX_COUNTER INTEGER;
DECLARE VARIABLE CURRENT_STACK_TOP INTEGER;
DECLARE VARIABLE PARENT CHAR( 10 );
DECLARE VARIABLE ANY_CHILDREN INTEGER;
DECLARE VARIABLE TREE_COST_CENTER CHAR( 10 );
BEGIN
/* delete all set data */
DELETE FROM COST_CENTER_TREE;
COUNTER = 2;
CURRENT_STACK_TOP = 1;
/* Get Maximum leaf right_id */
SELECT
COUNT( * )
FROM
COST_CENTER_IMPORT
INTO
:MAX_COUNTER;
MAX_COUNTER = MAX_COUNTER * 2;
/* Get the root node from the tree implementation */
SELECT
COST_CENTER
FROM
COST_CENTER_IMPORT
WHERE
PARENT_COST_CENTER IS NULL
INTO
:PARENT;
/* Insert tree root node into nested set */
INSERT INTO COST_CENTER_STACK
( STACK_TOP, COST_CENTER, LEFT_ID, RIGHT_ID )
VALUES
( 1, :PARENT, 1, :MAX_COUNTER );
/* Delete the root node from the tree */
DELETE FROM
COST_CENTER_IMPORT
WHERE
PARENT_COST_CENTER IS NULL;
/* Create the nodes and assign right/left ids */
WHILE ( COUNTER <= ( MAX_COUNTER - 1 ) )
DO
BEGIN
ANY_CHILDREN = 0;
/* Are there any children for current node */
SELECT
COUNT( * ) , MIN( T1.COST_CENTER)
FROM
COST_CENTER_STACK S1,
COST_CENTER_IMPORT T1
WHERE
S1.COST_CENTER = T1.PARENT_COST_CENTER
AND
S1.STACK_TOP = :CURRENT_STACK_TOP
INTO
:ANY_CHILDREN, :TREE_COST_CENTER;
/* found some children so add to nested set */
IF ( ANY_CHILDREN > 0 ) THEN
BEGIN
/* Grab Tree node and add as set element */
/* Set the LEFT_ID value */
INSERT INTO COST_CENTER_STACK
( STACK_TOP, COST_CENTER, LEFT_ID )
VALUES
( :CURRENT_STACK_TOP + 1, :TREE_COST_CENTER, :COUNTER );
/* Remove Tree node */
DELETE FROM COST_CENTER_IMPORT
WHERE
COST_CENTER = :TREE_COST_CENTER;
/* Inc the counters */
COUNTER = :COUNTER + 1;
CURRENT_STACK_TOP = :CURRENT_STACK_TOP + 1;
END
ELSE
BEGIN
/* Pop items off the stack */
/* Set the RIGHT_ID value */
UPDATE
COST_CENTER_STACK
SET
RIGHT_ID = :COUNTER,
STACK_TOP = -STACK_TOP
WHERE
STACK_TOP = :CURRENT_STACK_TOP;
COUNTER = :COUNTER + 1;
CURRENT_STACK_TOP = :CURRENT_STACK_TOP - 1;
END
END
EXECUTE PROCEDURE MOVE_STACK_TO_SET;
END
/* -- Test Data for tree -- */
INSERT INTO "COST_CENTER_IMPORT" ("COST_CENTER", "PARENT_COST_CENTER", "DESCRIPTION") VALUES ('A', NULL, NULL);
INSERT INTO "COST_CENTER_IMPORT" ("COST_CENTER", "PARENT_COST_CENTER", "DESCRIPTION") VALUES ('B', 'A', NULL);
INSERT INTO "COST_CENTER_IMPORT" ("COST_CENTER", "PARENT_COST_CENTER", "DESCRIPTION") VALUES ('C', 'A', NULL);
INSERT INTO "COST_CENTER_IMPORT" ("COST_CENTER", "PARENT_COST_CENTER", "DESCRIPTION") VALUES ('D', 'B', NULL);
INSERT INTO "COST_CENTER_IMPORT" ("COST_CENTER", "PARENT_COST_CENTER", "DESCRIPTION") VALUES ('E', 'B', NULL);
INSERT INTO "COST_CENTER_IMPORT" ("COST_CENTER", "PARENT_COST_CENTER", "DESCRIPTION") VALUES ('F', 'B', NULL);
INSERT INTO "COST_CENTER_IMPORT" ("COST_CENTER", "PARENT_COST_CENTER", "DESCRIPTION") VALUES ('G', 'C', NULL);
INSERT INTO "COST_CENTER_IMPORT" ("COST_CENTER", "PARENT_COST_CENTER", "DESCRIPTION") VALUES ('H', 'C', NULL);
INSERT INTO "COST_CENTER_IMPORT" ("COST_CENTER", "PARENT_COST_CENTER", "DESCRIPTION") VALUES ('I', 'D', NULL);
INSERT INTO "COST_CENTER_IMPORT" ("COST_CENTER", "PARENT_COST_CENTER", "DESCRIPTION") VALUES ('J', 'D', NULL);
INSERT INTO "COST_CENTER_IMPORT" ("COST_CENTER", "PARENT_COST_CENTER", "DESCRIPTION") VALUES ('K', 'I', NULL);
INSERT INTO "COST_CENTER_IMPORT" ("COST_CENTER", "PARENT_COST_CENTER", "DESCRIPTION") VALUES ('L', 'I', NULL);
INSERT INTO "COST_CENTER_IMPORT" ("COST_CENTER", "PARENT_COST_CENTER", "DESCRIPTION") VALUES ('M', 'H', NULL);
INSERT INTO "COST_CENTER_IMPORT" ("COST_CENTER", "PARENT_COST_CENTER", "DESCRIPTION") VALUES ('N', 'H', NULL);
INSERT INTO "COST_CENTER_IMPORT" ("COST_CENTER", "PARENT_COST_CENTER", "DESCRIPTION") VALUES ('O', 'N', NULL);
/* -- Testing -- */
/* Perform the conversion from tree to nested set */
EXECUTE PROCEDURE LIST_TO_SET;
/* Collect a sub tree from nested set */
SELECT * FROM GET_SUB_TREE( 'C' );
/* NOTE Results should be C, G, H, M, N, O */
/* Collect parent tree from nested set */
SELECT * FROM GET_PARENT_TREE( 'C' );
/* Should return C, A */
John Croft <jcroft@...>
06/02/2003 11:42 AM EST
Please respond to ib-support
To: ib-support@yahoogroups.com
cc:
bcc:
Subject: Re: [ib-support] Tree as adjaceny List conversion to nested set.
Jem -
Here is the procedure along with the tables that it works from. My tree
is slightly different in that sub-nodes on each level are ordered so you
will need to adjust for that. I would like to see your final results as
I might have a need for that in the future.
- John Croft
CREATE TABLE TREE_TBL (
NODE_ID INTEGER NOT NULL,
NODE_PRIOR INTEGER DEFAULT 0 NOT NULL,
NODE_NEXT INTEGER DEFAULT 0 NOT NULL,
PARENT_NODE_ID INTEGER DEFAULT 0 NOT NULL
);
CREATE TABLE NODE_TBL (
NODE_ID INTEGER NOT NULL,
NODE_NAME CHAR(64) CHARACTER SET NONE NOT NULL
);
BEGIN
NODE_LEVEL = 0;
NODE_LEVEL_ORDER = 0;
current_node_id = 0;
parent_node_id = 0;
next_node_id = 0;
prior_node_id = 0;
leaf = 0;
SELECT MIN(NODE_ID)
FROM TREE_TBL
WHERE PARENT_NODE_ID = 0 AND
NODE_PRIOR = 0
INTO :STARTING_NODE_ID;
WHILE (:STARTING_NODE_ID IS NOT NULL)
DO
BEGIN
/* Select starting node */
SELECT t.node_id, t.node_name, tt.node_next
FROM node_tbl t LEFT OUTER JOIN TREE_TBL tt
ON t.node_id = tt.node_id
WHERE t.node_id = :STARTING_NODE_ID
INTO :node_id, :node_name, :next_node_id;
IF (leaf = 0) THEN
NODE_LEVEL = NODE_LEVEL + 1;
ELSE
leaf = 0;
NODE_LEVEL_ORDER = NODE_LEVEL_ORDER + 1;
SUSPEND;
/* Assign current node */
current_node_id = STARTING_NODE_ID;
IF (:node_id IS NOT NULL) THEN
BEGIN
SELECT min(c.node_id)
FROM TREE_TBL c
WHERE (c.parent_node_id = :STARTING_NODE_ID) AND
(c.node_prior = 0)
INTO :STARTING_NODE_ID;
IF (:STARTING_NODE_ID IS NOT NULL) THEN
BEGIN
leaf = 0;
parent_node_id = current_node_id;
prior_node_id = STARTING_NODE_ID;
END
ELSE
BEGIN
leaf = 1;
SELECT nc.node_id
FROM TREE_TBL nc
WHERE nc.parent_node_id = :parent_node_id AND
nc.node_id = :next_node_id
INTO :STARTING_NODE_ID;
IF (:STARTING_NODE_ID IS NOT NULL) THEN
BEGIN
prior_node_id = STARTING_NODE_ID;
END
ELSE
BEGIN
WHILE ((:STARTING_NODE_ID IS NULL) AND (NODE_LEVEL > 1))
DO
BEGIN
SELECT nn.parent_node_id, nn.node_next
FROM TREE_TBL nn
WHERE nn.node_id = :parent_node_id
INTO :parent_node_id, :next_node_id;
SELECT st.node_id
FROM TREE_TBL st
WHERE st.parent_node_id = :parent_node_id AND
st.node_id = :next_node_id
INTO :STARTING_NODE_ID;
NODE_LEVEL = NODE_LEVEL - 1;
IF (:STARTING_NODE_ID IS NOT NULL) THEN
prior_node_id = STARTING_NODE_ID;
END
END
END
END
END
END
Jem Rayfield wrote:
>John,To unsubscribe from this group, send an email to:
>
>Yes please. Im sure it would be a good starting point.
>
>
>Thanks alot
>Jem Rayfield
>Technical Consultant
>Deutsche Bank [/]
>CIB - IT Infrastructure
>Corporate and Investment Bank (CIB)
>London
>t: +44(20)754-51943
>
>
>
> John Croft
> <jcroft@compsolve To: ib-support@yahoogroups.com
> .com> cc:
> Subject: Re: [ib-support] Tree as adjaceny List conversion to nested set.
> 06/02/2003 14:47
> Please respond to
> ib-support
>
>
>
>
>
>
>I have a stored procedure that will traverse the tree and you should be
>able to modify it to write the nested set records. Let me know if you
>want it.
>John Croft
>
>Jem Rayfield wrote:
>
>>Hi,
>>
>>I have a tree structure stored as an adjacency list
>>
>>create table tree (
>> id integer,
>> pid integer,
>> name varchar( 10 )
>>)
>>
>>
>>I want to convert this Tree into a nested set using the following
>>data structure.
>>
>>create table nested_set (
>> name varchar( 10 ),
>> left integer,
>> right integer
>>)
>>
>>
>>Has anyone got a URL/example stored-procedure for this type of
>>conversion?
>>
>>Thanks for any pointers.
>>
>>Jem Rayfield
>>Technical Consultant
>>Deutsche Bank [/]
>>CIB - IT Infrastructure
>>Corporate and Investment Bank (CIB)
>>London
>>t: +44(20)754-51943
>>
>>
>>
>>--
>>
>>This e-mail may contain confidential and/or privileged information. If you are not the intended recipient (or have received this e-mail in error) please notify the sender immediately and destroy this e-mail. Any unauthorized copying, disclosure or distribution of the material in this e-mail is strictly forbidden.
>>
>>
>>
>>
>>To unsubscribe from this group, send an email to:
>>ib-support-unsubscribe@egroups.com
>>
>>
>>
>>Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>>
>
>
>
>
>To unsubscribe from this group, send an email to:
>ib-support-unsubscribe@egroups.com
>
>
>
>Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>
>
>
>
>
>
>--
>
>This e-mail may contain confidential and/or privileged information. If you are not the intended recipient (or have received this e-mail in error) please notify the sender immediately and destroy this e-mail. Any unauthorized copying, disclosure or distribution of the material in this e-mail is strictly forbidden.
>
>
>
>
>To unsubscribe from this group, send an email to:
>ib-support-unsubscribe@egroups.com
>
>
>
>Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
ib-support-unsubscribe@egroups.com
Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
Jem Rayfield
Technical Consultant
Deutsche Bank [/]
CIB - IT Infrastructure
Corporate and Investment Bank (CIB)
London
t: +44(20)754-51943
John Croft
<jcroft@compsolve To: ib-support@yahoogroups.com
.com> cc:
Subject: Re: [ib-support] Tree as adjaceny List conversion to nested set.
06/02/2003 16:42
Please respond to
ib-support
Jem -
Here is the procedure along with the tables that it works from. My tree
is slightly different in that sub-nodes on each level are ordered so you
will need to adjust for that. I would like to see your final results as
I might have a need for that in the future.
- John Croft
CREATE TABLE TREE_TBL (
NODE_ID INTEGER NOT NULL,
NODE_PRIOR INTEGER DEFAULT 0 NOT NULL,
NODE_NEXT INTEGER DEFAULT 0 NOT NULL,
PARENT_NODE_ID INTEGER DEFAULT 0 NOT NULL
);
CREATE TABLE NODE_TBL (
NODE_ID INTEGER NOT NULL,
NODE_NAME CHAR(64) CHARACTER SET NONE NOT NULL
);
BEGIN
NODE_LEVEL = 0;
NODE_LEVEL_ORDER = 0;
current_node_id = 0;
parent_node_id = 0;
next_node_id = 0;
prior_node_id = 0;
leaf = 0;
SELECT MIN(NODE_ID)
FROM TREE_TBL
WHERE PARENT_NODE_ID = 0 AND
NODE_PRIOR = 0
INTO :STARTING_NODE_ID;
WHILE (:STARTING_NODE_ID IS NOT NULL)
DO
BEGIN
/* Select starting node */
SELECT t.node_id, t.node_name, tt.node_next
FROM node_tbl t LEFT OUTER JOIN TREE_TBL tt
ON t.node_id = tt.node_id
WHERE t.node_id = :STARTING_NODE_ID
INTO :node_id, :node_name, :next_node_id;
IF (leaf = 0) THEN
NODE_LEVEL = NODE_LEVEL + 1;
ELSE
leaf = 0;
NODE_LEVEL_ORDER = NODE_LEVEL_ORDER + 1;
SUSPEND;
/* Assign current node */
current_node_id = STARTING_NODE_ID;
IF (:node_id IS NOT NULL) THEN
BEGIN
SELECT min(c.node_id)
FROM TREE_TBL c
WHERE (c.parent_node_id = :STARTING_NODE_ID) AND
(c.node_prior = 0)
INTO :STARTING_NODE_ID;
IF (:STARTING_NODE_ID IS NOT NULL) THEN
BEGIN
leaf = 0;
parent_node_id = current_node_id;
prior_node_id = STARTING_NODE_ID;
END
ELSE
BEGIN
leaf = 1;
SELECT nc.node_id
FROM TREE_TBL nc
WHERE nc.parent_node_id = :parent_node_id AND
nc.node_id = :next_node_id
INTO :STARTING_NODE_ID;
IF (:STARTING_NODE_ID IS NOT NULL) THEN
BEGIN
prior_node_id = STARTING_NODE_ID;
END
ELSE
BEGIN
WHILE ((:STARTING_NODE_ID IS NULL) AND (NODE_LEVEL > 1))
DO
BEGIN
SELECT nn.parent_node_id, nn.node_next
FROM TREE_TBL nn
WHERE nn.node_id = :parent_node_id
INTO :parent_node_id, :next_node_id;
SELECT st.node_id
FROM TREE_TBL st
WHERE st.parent_node_id = :parent_node_id AND
st.node_id = :next_node_id
INTO :STARTING_NODE_ID;
NODE_LEVEL = NODE_LEVEL - 1;
IF (:STARTING_NODE_ID IS NOT NULL) THEN
prior_node_id = STARTING_NODE_ID;
END
END
END
END
END
END
Jem Rayfield wrote:
>John,To unsubscribe from this group, send an email to:
>
>Yes please. Im sure it would be a good starting point.
>
>
>Thanks alot
>Jem Rayfield
>Technical Consultant
>Deutsche Bank [/]
>CIB - IT Infrastructure
>Corporate and Investment Bank (CIB)
>London
>t: +44(20)754-51943
>
>
>
> John Croft
> <jcroft@compsolve To: ib-support@yahoogroups.com
> .com> cc:
> Subject: Re: [ib-support] Tree as adjaceny List conversion to nested set.
> 06/02/2003 14:47
> Please respond to
> ib-support
>
>
>
>
>
>
>I have a stored procedure that will traverse the tree and you should be
>able to modify it to write the nested set records. Let me know if you
>want it.
>John Croft
>
>Jem Rayfield wrote:
>
>>Hi,
>>
>>I have a tree structure stored as an adjacency list
>>
>>create table tree (
>> id integer,
>> pid integer,
>> name varchar( 10 )
>>)
>>
>>
>>I want to convert this Tree into a nested set using the following
>>data structure.
>>
>>create table nested_set (
>> name varchar( 10 ),
>> left integer,
>> right integer
>>)
>>
>>
>>Has anyone got a URL/example stored-procedure for this type of
>>conversion?
>>
>>Thanks for any pointers.
>>
>>Jem Rayfield
>>Technical Consultant
>>Deutsche Bank [/]
>>CIB - IT Infrastructure
>>Corporate and Investment Bank (CIB)
>>London
>>t: +44(20)754-51943
>>
>>
>>
>>--
>>
>>This e-mail may contain confidential and/or privileged information. If you are not the intended recipient (or have received this e-mail in error) please notify the sender immediately and destroy this e-mail. Any unauthorized copying, disclosure or distribution of the material in this e-mail is strictly forbidden.
>>
>>
>>
>>
>>To unsubscribe from this group, send an email to:
>>ib-support-unsubscribe@egroups.com
>>
>>
>>
>>Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>>
>
>
>
>
>To unsubscribe from this group, send an email to:
>ib-support-unsubscribe@egroups.com
>
>
>
>Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>
>
>
>
>
>
>--
>
>This e-mail may contain confidential and/or privileged information. If you are not the intended recipient (or have received this e-mail in error) please notify the sender immediately and destroy this e-mail. Any unauthorized copying, disclosure or distribution of the material in this e-mail is strictly forbidden.
>
>
>
>
>To unsubscribe from this group, send an email to:
>ib-support-unsubscribe@egroups.com
>
>
>
>Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
ib-support-unsubscribe@egroups.com
Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
--
This e-mail may contain confidential and/or privileged information. If you are not the intended recipient (or have received this e-mail in error) please notify the sender immediately and destroy this e-mail. Any unauthorized copying, disclosure or distribution of the material in this e-mail is strictly forbidden.