Nested Set Model Question - SQL Server Forums

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 2000 Forums

SQL Server Development (2000)

Nested Set Model Question

Author

Topic

Page47
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2003-01-09 : 14:07:45

Say you have a nested set ...


create table tree (
    leaf varchar(20) not null primary key nonclustered,
    l    int not null unique,
    r    int not null unique,
    unique clustered (l,r),
    check(l<r) )

insert tree values ('evoymhzhk',4,13)
insert tree values ('hr',19,20)
insert tree values ('mr',2,15)
insert tree values ('n',17,18)
insert tree values ('o',5,10)
insert tree values ('r',16,21)
insert tree values ('root',1,22)
insert tree values ('uc',6,7)
insert tree values ('uiniatklu',3,14)
insert tree values ('vtbwj',11,12)
insert tree values ('w',8,9)

How do you write a query to return the nodes exactly @levels down/up from a given @leaf?

I've mastered selecting an entire 'upline' or 'downline' of a given @leaf, but I can't seem to come up with an optimized way to get "my direct children" or "my direct parents".

I have a working query, which I can supply on request, but I'd like to find a better way. Who are "evoymhzhk's" children, 1 level down? Answer: "o" and "vtbwj".

Jay White
{0}

jsmith8858
Dr. Cross Join

7423 Posts

Posted - 2003-01-09 : 14:23:48

jay -- do we need some sort of ID field on these records?

- Jeff

Page47
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2003-01-09 : 14:28:55

... bwahahaha!!

~~EDIT: Jeff, I bet that now that you've de-railed by thread, I won't get any replies~~

Jay White
{0}

Edited by - Page47 on 01/09/2003 14:31:06

robvolk
Most Valuable Yak

15732 Posts

Posted - 2003-01-09 : 14:29:22

SQL For Smarties, page 453:

CREATE VIEW ImmediateSubordinates (boss, worker, lft, rgt) AS
SELECT Managers.leaf AS Boss, Workers.leaf AS Worker,
Workers.l AS lft, Workers.r AS rgt
FROM tree Managers, tree Workers
WHERE Workers.l BETWEEN Managers.l AND Managers.r
AND NOT EXISTS --no middle manager between the boss and us
(SELECT * FROM tree MidMgr
WHERE MidMgr.l BETWEEN Managers.l AND Managers.r
AND Workers.l BETWEEN MidMgr.l AND MidMgr.r
AND MidMgr.leaf NOT IN (Workers.leaf, Managers.leaf))

I changed the original to match the structure you posted, but it should work. And if you don't already have SQL For Smarties....welllllllll?

setbasedisthetruepath
Used SQL Salesman

992 Posts

Posted - 2003-01-09 : 14:30:51

And n-levels down?

Jonathan
{0}

robvolk
Most Valuable Yak

15732 Posts

Posted - 2003-01-09 : 14:33:30

There is a way to do it, it may not be listed exactly that way in SQL For Smarties, but I've seen a formula for it. Check all of Joe's posts on SQL Team, I wouldn't be surprised if he posted it here already. If not, if you look at the basics he provides in the book you'll be able to figure it out.

byrmol
Shed Building SQL Farmer

1591 Posts

Posted - 2003-01-09 : 15:01:56

Jay,

I would have thought you first had to find what level you are talking about ..GROUP BY, COUNT etc... Then find the nodes that have a level N away from the target Level .. Then a BETWEEN to restrict the nodes to the same path...

DavidM

"SQL-3 is an abomination.."

jsmith8858
Dr. Cross Join

7423 Posts

Posted - 2003-01-09 : 15:58:08

How about this?? should work pretty easy. Maybe not totally efficient; let me know, I can make it more efficient if we need to.

Of course, filter the results to return only the level down from the starting point that you want.

-------

declare @t table (
leaf varchar(20) not null primary key nonclustered,
l int not null unique,
r int not null unique,
unique clustered (l,r),
check(l<r) )

insert @t values ('evoymhzhk',4,13)
insert @t values ('hr',19,20)
insert @t values ('mr',2,15)
insert @t values ('n',17,18)
insert @t values ('o',5,10)
insert @t values ('r',16,21)
insert @t values ('root',1,22)
insert @t values ('uc',6,7)
insert @t values ('uiniatklu',3,14)
insert @t values ('vtbwj',11,12)
insert @t values ('w',8,9)

declare @Start varchar(40);

set @Start = 'evoymhzhk'

select T2.*,
(SELECT COUNT(*) FROM @t TT where T2.l BETWEEN TT.l and TT.r) -
(SELECT COUNT(*) FROM @t TT where T.l between TT.l and TT.r)
as Depth_of_Leaf_From_Start
from @t T
inner join
@t T2 ON t2.l between t.l and t.r
where t.leaf = @Start

- Jeff

jsmith8858
Dr. Cross Join

7423 Posts

Posted - 2003-01-10 : 07:57:03

Here's one more -- I realized that you said you want to go levels UP or DOWN, so based on the starting leaf, this returns a "relativeLevel" for every leaf in the tree:

> 0 means the leaf is N levels below the starting leaf
= 0 means the leaf IS the starting leaf
< 0 means the leaf is N levels directly above the starting leaf
Null means there is no direct relationship

I may not be returning the levels above exactly the way you want; I only return leafs directly above the starging point and none of its siblings -- i.e., there will always be exactly 1 leaf per level above the starting leaf.

Note that it looks like we are doing 2 cross joins, but it is really only one -- 1 pass through the tree just returns the one starting node.

BTW -- I learned to do all this from a "Database Fundamentals 101" book y'all suggested I read on the other thread a week ago...Thanks!

----

set nocount on

declare @t table (
leaf varchar(20) not null primary key nonclustered,
l int not null unique,
r int not null unique,
unique clustered (l,r),
check(l<r) )

insert @t values ('evoymhzhk',4,13)
insert @t values ('hr',19,20)
insert @t values ('mr',2,15)
insert @t values ('n',17,18)
insert @t values ('o',5,10)
insert @t values ('r',16,21)
insert @t values ('root',1,22)
insert @t values ('uc',6,7)
insert @t values ('uiniatklu',3,14)
insert @t values ('vtbwj',11,12)
insert @t values ('w',8,9)

declare @Start varchar(40);

set @Start = 'evoymhzhk'

set nocount off

SELECT StartLeaf, Leaf,
CASE WHEN LeafLevel < StartLevel AND DirectParent = 0 THEN Null ELSE LeafLevel - StartLevel END as RelativeLevel
FROM
(
select StartLeaf.Leaf as StartLeaf,
Leaf.Leaf,
SUM(CASE WHEN StartLeaf.l between CountLeaf.l and CountLeaf.r then 1 else 0 END) as StartLevel,
SUM(CASE WHEN Leaf.l between CountLeaf.l and CountLeaf.r THEN 1 ELSE 0 END) as LeafLevel,
MAX(CASE WHEN StartLeaf.l between Leaf.l and Leaf.r THEN 1 ELSE 0 END) as DirectParent
from @t StartLeaf
Cross join @t Leaf
cross join @t CountLeaf
WHERE StartLeaf.Leaf = @Start
GROUP BY StartLeaf.Leaf, Leaf.Leaf
) A

- Jeff

Edited by - jsmith8858 on 01/10/2003 08:13:19

Page47
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2003-01-10 : 09:29:14

Nice work Jeff, that was exactly what I was after ...

Jay White
{0}

Page47
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2003-01-10 : 14:31:47

I'm finding this to be a real shortcoming of the model. It seems that when you are concerned with levels the queries get slower and slower as you add nodes to the tree. At 1000 nodes "Gimme all the grandchildren of @leaf" runs quite reasonably. Increase that to 10,000 nodes and performance dies (>1 minute).

I toyed with using Rob's query as a materialized view exposing the Adjacency model view of the tree ... SQL doesn't allow you to index a view with an outer join <rolleyes>.

Joe, care shed some light?

Jay White
{0}

robvolk
Most Valuable Yak

15732 Posts

Posted - 2003-01-10 : 15:06:31

Any reason you can't use BOTH, and then write each query to pick the model that performs best for it? Add a lineage column to your tree table. It's not like they take up a huge amount of space, and keeping them in sync isn't all that hard (adjacency is practically on autopilot; certainly a lot less work than nested sets)

Edited by - robvolk on 01/10/2003 15:09:23

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources