Nested Sets (Multiple Tree in the same table)

Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

All Forums

SQL Server 2008 Forums

SQL Server Administration (2008)

Nested Sets (Multiple Tree in the same table)

Author

Topic

dlusignan
Starting Member

3 Posts

Posted - 2009-10-26 : 11:08:21

Hi!

Is this possible to have multiple trees in the same table like this:
If yes, my next question will rely on Transact-SQL.


CategoryID  ParentID    Name                      Lft         Rgt
----------- ----------- ------------------------- ----------- ----
1           NULL        Actualité                 1           16
2           NULL        Culture                   1           18
31          2           Arts de la scène          2           3
33          1           Communautaire             2           3
34          2           Divers                    4           5
35          2           Babillard culturel        6           7
38          2           Expositions               8           9
40          2           Littérature               10          11
41          2           Loisirs culturels         12          13
42          1           Politique municipale      4           5
49          1           Environnement             6           7
50          1           Politique (autres)        8           9
51          2           Festivals                 14          15
52          2           Histoire et patrimoine    16          17
56          1           Santé                     10          11
57          1           Éducation                 12          13
59          1           Faits divers     	  14          15

Daniel

TG
Master Smack Fu Yak Hacker

6065 Posts

Posted - 2009-10-26 : 11:21:23

Yes. The ID/parentID construct is one way to model a hierarchy and of course multiple 'trees' can be represented in the same table (as you have demonstrated). But I'm not sure what you're [Lft] and [Rgt] columns signify. Perhaps I don't get the question...

Be One with the Optimizer
TG

dlusignan
Starting Member

3 Posts

Posted - 2009-10-26 : 11:41:15

Hi! Thanks for the answer. The use of Lft and Rgt permits you to define an order more easily for optimising the queries e.g.:


SELECT ca.CategoryID, ca.ParentID, ca.[Name], ca.Lft, ca.Rgt
FROM printedproducts.Category ca
WHERE Lft = (Rgt - 1)
AND ca.ParentID = 1

who give this result:


CategoryID  ParentID  Name                  Lft  Rgt
33	    1	      Communautaire	    2	 3
42	    1	      Politique municipale  4	 5
49	    1	      Environnement	    6	 7
50	    1	      Politique (autres)    8	 9
56	    1	      Santé	            10	 11
57	    1	      Éducation	            12	 13
59	    1	      Faits divers	    14	 15

as you can see, it's an easy and fast way of accessing all the children in a hierarchy. In a production environment, with large amount of data, you can add an index on both Lft and Rgt.

Daniel

TG
Master Smack Fu Yak Hacker

6065 Posts

Posted - 2009-10-26 : 12:59:15

So your parentID is really the Root ID, right? Can you express multiple nesting levels (like below)?

With just ID/ParentID you can support a full hierachy with unlimited roots and unlimited sub-trees. Here is an example using a Recursive CTE:


set nocount on
declare @h table (id int, pid int)
declare @n table (id int, name varchar(10))

----------------------
--sample date

--names
insert @n
select 1, 'name1' union all
select 2, 'name2' union all
select 3, 'name3' union all
select 4, 'name4' union all
select 5, 'name5' union all
select 6, 'name6' union all
select 7, 'name7'

--Hierachy
insert @h
select 1,null union all
select 2,1 union all
select 3,1 union all
select 4,2 union all
select 5,4 union all
select 6,null union all
select 7,6 

--add a circular reference to make sure our recursive cte deals with it
union all select 1,5 
----------------------

;with cte as
(
       --Anchor member (no reference to cte)
       select h.id
              ,h.pid
              ,m.name
              ,0 as lev
              ,convert(varchar(50), right('00' + convert(varchar,h.id),3)) as sort
       from   @n m
       join   @h h on h.id = m.id
       where  h.pid is null

       union all

       --recursion member because statement references cte
       select h.id
              ,h.pid
              ,m.name
              ,lev+1 

              -- datatyps must match (anchor and recusion member columns)
              ,convert(varchar(50), sort + '.' + right('00' + convert(varchar,h.id),3))

       from   @n m
       join   @h h on h.id = m.id
       join   cte y on y.id = h.pid

       --avoid a circular reference
       where  patindex('%' + right('00' + convert(varchar,h.id),3) + '%', sort) = 0
)

select replicate(space(2), lev) + name tree
       --,*
from cte
order by sort
--option (maxrecursion 10)

OUTPUT:
tree
------------
name1
  name2
    name4
      name5
  name3
name6
  name7

Be One with the Optimizer
TG

dlusignan
Starting Member

3 Posts

Posted - 2009-10-26 : 14:07:44

Hi! Yes you can.

Unfortunately, I can't figured out how to insert an image but, anyway, look at this snippet and try it in your Management Studio. You will figurate in the result, that it comes out with a boss employees relationship. Look at now, the way the columns Lft and Rgt are organized. You will easily figured out that everyone belongs to Albert but also, Donna, Eddie and Fred belong to Chuck.

I recommanded you this book:
Trees and Hierarchies in SQL For Smarties.

It's all about the subject.


declare @OrgChart TABLE
    (
      Member CHAR(10),
      Lft int,
      Rgt int
    )
    
insert @OrgChart
select 'Albert', 1, 12 union all
select 'Bert', 2, 3 union all
select 'Chuck', 4, 11 union all
select 'Donna', 5, 6 union all
select 'Eddie', 7, 8 union all
select 'Fred', 9, 10

SELECT Mgrs.member AS boss, Workers.member AS worker
FROM @Orgchart AS Mgrs, @Orgchart AS Workers
WHERE Workers.lft > Mgrs.lft
AND Workers.lft < Mgrs.rgt

Daniel

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources