Solved

From parent-child model to nested intervals in SQL Server

Posted on 2007-03-30
10
355 Views
Last Modified: 2008-02-01
I have a table like this:

Create Table Category
(
CatID   Int Null,
CatName Varchar(20),
ParentID Int,
Lft Int,
Rgt Int)


Insert Into Category Values(1, 'Category 1', Null, Null, Null);
Insert Into Category Values(2, 'Category 2', 1, Null, Null);
Insert Into Category Values(3, 'Category 3', 1, Null, Null);
Insert Into Category Values(4, 'Category 4', 3, Null, Null);
Insert Into Category Values(5, 'Category 5', 3, Null, Null);
Insert Into Category Values(6, 'Category 6', 2, Null, Null);
Insert Into Category Values(7, 'Category 7', 2, Null, Null);

I want to fill the Lft and Rgt columns with values needed to handle the hierarchy with the nested intervals model.
I have right here, a Joe Celko's book solely dedicated to hierarchies and guess what, it doesn't explain exactly this.
0
Comment
Question by:fischermx
  • 5
  • 5
10 Comments
 
LVL 42

Expert Comment

by:dqmq
ID: 18827662
Insert Into Category Values(1, 'Category 1', Null, 1, 14);
Insert Into Category Values(2, 'Category 2', 1, 2, 7);
Insert Into Category Values(3, 'Category 3', 1, 8, 13);
Insert Into Category Values(4, 'Category 4', 3, 9, 10);
Insert Into Category Values(5, 'Category 5', 3, 11, 12);
Insert Into Category Values(6, 'Category 6', 2, 3, 4);
Insert Into Category Values(7, 'Category 7', 2, 5, 6);

Once lft and rgt are populated, you no longer need parentid column
0
 
LVL 1

Author Comment

by:fischermx
ID: 18827668
But the thing is, I have 12,000 rows in this table. Clearly you did this by hand/eye.

I'd like to know the <b>procedure</b> to generate the lft and rgt columns for these 12,000 rows.

0
 
LVL 1

Author Comment

by:fischermx
ID: 18827669
BTW, when in a given hierarchy table you just have the Parent ID column to help you represent the tree, what's the name of that model?
0
 
LVL 42

Accepted Solution

by:
dqmq earned 500 total points
ID: 18827693
Sure, I did it by hand/eye.   Here's Joe's procedure for converting from from the adjacency list to the nested set.  Perhaps you can adapt it to your table:

-- Tree holds the adjacency model
CREATE TABLE Tree
(emp CHAR(10) NOT NULL,   --CatID in your case
 boss CHAR(10));                  --ParentID in your case

INSERT INTO Tree
SELECT emp, boss FROM Personnel;    --From Category in your Case

-- 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, 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;





0
 
LVL 42

Expert Comment

by:dqmq
ID: 18827740
Celko refers parent relationship design as the "adjaceny model".  Not a very intuitive name IMHO.  
0
Control application downtime with dependency maps

Visualize the interdependencies between application components better with Applications Manager's automated application discovery and dependency mapping feature. Resolve performance issues faster by quickly isolating problematic components.

 
LVL 1

Author Comment

by:fischermx
ID: 18827795
What SQL dialect is that ?
0
 
LVL 42

Expert Comment

by:dqmq
ID: 18831003
I don't know.  But I only see a couple  statements that won't port to SQL SERVER:
BEGIN ATOMIC
WHILE... LOOP...  END LOOP
0
 
LVL 1

Author Comment

by:fischermx
ID: 18831141
... and all the variables declaration and use, they're missing the "@".

Anyway, I got it working. Thanks !
0
 
LVL 42

Expert Comment

by:dqmq
ID: 18832333
Whoa...I totally overlooked the "@".   Glad (Joe and) I could be of some help.  
0
 
LVL 1

Author Comment

by:fischermx
ID: 18832496
He is using standard SQL-92, that's why he got that syntax that seems not to match exactly any known DBMS.

0

Featured Post

Best Practices: Disaster Recovery Testing

Besides backup, any IT division should have a disaster recovery plan. You will find a few tips below relating to the development of such a plan and to what issues one should pay special attention in the course of backup planning.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

I wrote this interesting script that really help me find jobs or procedures when working in a huge environment. I could I have written it as a Procedure but then I would have to have it on each machine or have a link to a server-related search that …
Everyone has problem when going to load data into Data warehouse (EDW). They all need to confirm that data quality is good but they don't no how to proceed. Microsoft has provided new task within SSIS 2008 called "Data Profiler Task". It solve th…
Viewers will learn how to use the SELECT statement in SQL to return specific rows and columns, with various degrees of sorting and limits in place.
Viewers will learn how to use the SELECT statement in SQL and will be exposed to the many uses the SELECT statement has.

947 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

21 Experts available now in Live!

Get 1:1 Help Now