Tree traversal 
Author Message
 Tree traversal
I am looking for more information concerning a tree traversal algorithm to set
left and right value o an MS SQL Server 2000 in a graphs Table


Sat, 15 Nov 2003 15:20:22 GMT
 Tree traversal

Serge,

you're talking about Joe Celko's nested model set?

/Lasse


I am looking for more information concerning a tree traversal algorithm to
set
left and right value o an MS SQL Server 2000 in a graphs Table



Sat, 15 Nov 2003 17:20:32 GMT
 Tree traversal
Yes it's about Joe Celko's nested model set
Quote:
-----Original Message-----
Serge,

you're talking about Joe Celko's nested model set?

/Lasse



I am looking for more information concerning a tree traversal algorithm to
set
left and right value o an MS SQL Server 2000 in a graphs Table

.



Sat, 15 Nov 2003 19:59:14 GMT
 Tree traversal
Serge,

Then consider purchasing Joe's book "SQL for Smarties".

-------------------------------------------
BP Margolin
Please reply only to the newsgroups.
When posting, inclusion of SQL (CREATE TABLE ..., INSERT ..., etc.) which
can be cut and pasted into Query Analyzer is appreciated.


Yes it's about Joe Celko's nested model set

Quote:
-----Original Message-----
Serge,

you're talking about Joe Celko's nested model set?

/Lasse



I am looking for more information concerning a tree traversal algorithm to
set
left and right value o an MS SQL Server 2000 in a graphs Table

.



Sun, 16 Nov 2003 00:57:51 GMT
 Tree traversal
If you have the adjacency list model table and you want to convert it to a nested sets model, then use the classic pushdown stack algorithm.  It will be something like this in SQL/PSM.

-- Tree holds the adjacency model
CREATE TABLE Tree
(emp CHAR(10) NOT NULL,
 boss CHAR(10));

INSERT INTO Tree
SELECT emp, boss FROM Personnel;

-- Stack starts empty, will holds the nested set model
CREATE TABLE Stack
(stack_top INTEGER NOT NULL,
 emp CHAR(10) NOT NULL,
 lft INTEGER,
 rgt INTEGER);

BEGIN ATOMIC
DECLARE counter INTEGER;
DECLARE max_counter INTEGER;
DECLARE current_top INTEGER;

SET counter = 2;
SET max_counter = 2 * (SELECT COUNT(*) FROM Tree);
SET current_top = 1;

INSERT INTO Stack
SELECT 1, emp, 1, NULL
  FROM Tree
 WHERE boss IS NULL;

DELETE FROM Tree
 WHERE boss IS NULL;

WHILE counter <= (max_counter - 2)
LOOP IF EXISTS (SELECT *
                   FROM Stack AS S1, Tree AS T1
                  WHERE S1.emp = T1.boss
                    AND S1.stack_top = current_top)
     THEN
     BEGIN -- push when top has subordinates and set lft value
       INSERT INTO Stack
       SELECT (current_top + 1), MIN(T1.emp), counter, NULL
         FROM Stack AS S1, Tree AS T1
        WHERE S1.emp = T1.boss
          AND S1.stack_top = current_top;

        DELETE FROM Tree
         WHERE emp = (SELECT emp
                        FROM Stack
                       WHERE stack_top = current_top + 1);

        SET counter = counter + 1;
        SET current_top = current_top + 1;
     END
     ELSE
     BEGIN  -- pop the stack and set rgt value
       UPDATE Stack
          SET rgt = counter,
              stack_top = -stack_top -- pops the stack
        WHERE stack_top = current_top
       SET counter = counter + 1;
       SET current_top = current_top - 1;
     END IF;
 END LOOP;
END;

--CELKO--

SQL guru at Trilogy
===========================
Please post DDL, so that people do not have to guess what the keys, constraints, Declarative Referential Integrity, datatypes, etc. in your schema are.

*** Sent via Developersdex http://www.developersdex.com ***
Don't just participate in USENET...get rewarded for it!



Sun, 16 Nov 2003 01:26:29 GMT
 
 [ 5 post ] 

 Relevant Pages 

1. Tree Traversal (Hierarchical Queries)

2. Tree traversal in sybase

3. Binary Tree Traversal in SQL SERVER 2000

4. Example Nonrecursive Tree Traversal

5. Complex Tree traversal program needed in PLSQL !!!

6. Tree Traversal In SQL

7. help with (Joe Celko) tree traversal routine

8. Self referencing table vs. tree traversal method

9. trees, WITH operator, and traversal

10. openXML and postorder traversal of document-tree

11. Databases, Data Structures, B Trees, B+ Trees, Patricia Trees

12. SQL and Table Structure for Graph Traversals


 
Powered by phpBB® Forum Software