Solved

From parent-child model to nested intervals in SQL Server

Posted on 2007-03-30
10
352 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
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
Celko refers parent relationship design as the "adjaceny model".  Not a very intuitive name IMHO.  
0
What Security Threats Are You Missing?

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

 
LVL 1

Author Comment

by:fischermx
Comment Utility
What SQL dialect is that ?
0
 
LVL 42

Expert Comment

by:dqmq
Comment Utility
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
Comment Utility
... and all the variables declaration and use, they're missing the "@".

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

Expert Comment

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

Author Comment

by:fischermx
Comment Utility
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

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Introduction In my previous article (http://www.experts-exchange.com/Microsoft/Development/MS-SQL-Server/SSIS/A_9150-Loading-XML-Using-SSIS.html) I showed you how the XML Source component can be used to load XML files into a SQL Server database, us…
For both online and offline retail, the cross-channel business is the most recent pattern in the B2C trade space.
This video shows how to set up a shell script to accept a positional parameter when called, pass that to a SQL script, accept the output from the statement back and then manipulate it in the Shell.
Via a live example, show how to set up a backup for SQL Server using a Maintenance Plan and how to schedule the job into SQL Server Agent.

743 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

18 Experts available now in Live!

Get 1:1 Help Now