Closing gaps in Celko-tree

Hello
I've been using that nested modeltree that Celko uses, and it's superb, but
I've encountered a problem with a table (some unforseen things happened when
i tried to move subtrees from A to B), and a really huge tree ended up with
gaps, structure of tree isnt messed up or anything, just has gaps here and
there.
I got SQL For Smarties (which is a great book btw..) but I cant get that
code to work no matter how I try in sql 2000.
Any of you guys got some neat update or something?
/LasseWhy does it matter if there are gaps?
In the one project I've used that technique on, we actually implemented gaps
on purpose in order to reduce the number of updates that would have to take
place any time a new row was inserted... Gaps do not change the behavior of
the mathematics.
Adam Machanic
Pro SQL Server 2005, available now
http://www.apress.com/book/bookDisplay.html?bID=457
--
"Lasse Edsvik" <lasse@.nospam.com> wrote in message
news:%23PZl6YfFGHA.1288@.TK2MSFTNGP09.phx.gbl...
> Hello
> I've been using that nested modeltree that Celko uses, and it's superb,
> but
> I've encountered a problem with a table (some unforseen things happened
> when
> i tried to move subtrees from A to B), and a really huge tree ended up
> with
> gaps, structure of tree isnt messed up or anything, just has gaps here and
> there.
> I got SQL For Smarties (which is a great book btw..) but I cant get that
> code to work no matter how I try in sql 2000.
> Any of you guys got some neat update or something?
> /Lasse
>|||Adam,
i dont quite agree, first of all, its easier to see if the tree is "valid"
(for debugging), 2nd, you dont have to have some subquery to determine if
its the last node in tree since lft-rgt=1 then (or x0 and x1 as i call them
in my design). And 3rd when you acctually going to use the values to display
a graph, it'd looked messed up.
sure it may work, but i'm allergic to "works but not quite correct", i'm
sure a Dell server with 2 xeon cpu's and 4gb ram can handle a few updates to
fix the gaps.
"Adam Machanic" <amachanic@.hotmail._removetoemail_.com> wrote in message
news:u2URrdfFGHA.2704@.TK2MSFTNGP15.phx.gbl...
> Why does it matter if there are gaps?
> In the one project I've used that technique on, we actually implemented
gaps
> on purpose in order to reduce the number of updates that would have to
take
> place any time a new row was inserted... Gaps do not change the behavior
of
> the mathematics.
>
> --
> Adam Machanic
> Pro SQL Server 2005, available now
> http://www.apress.com/book/bookDisplay.html?bID=457
> --
>
> "Lasse Edsvik" <lasse@.nospam.com> wrote in message
> news:%23PZl6YfFGHA.1288@.TK2MSFTNGP09.phx.gbl...
and
>|||Lasse Edsvik wrote:
> Adam,
> i dont quite agree, first of all, its easier to see if the tree is "valid"
> (for debugging), 2nd, you dont have to have some subquery to determine if
> its the last node in tree since lft-rgt=1 then (or x0 and x1 as i call the
m
> in my design). And 3rd when you acctually going to use the values to displ
ay
> a graph, it'd looked messed up.
> sure it may work, but i'm allergic to "works but not quite correct", i'm
> sure a Dell server with 2 xeon cpu's and 4gb ram can handle a few updates
to
> fix the gaps.
>
Hi Lasse,
Just thrown this together, test first:
create table Numbers (
Num int not null
)
go
insert into Numbers (Num)
select a.a * 100 + b.b * 10 + c.c
from
(select 0 as a union select 1 union select 2 union select 3 union
select 4 union select 5 union select 6 union select 7 union select 8
union select 9) a,
(select 0 as b union select 1 union select 2 union select 3 union
select 4 union select 5 union select 6 union select 7 union select 8
union select 9) b,
(select 0 as c union select 1 union select 2 union select 3 union
select 4 union select 5 union select 6 union select 7 union select 8
union select 9) c
go
create table Blah (
ID int not null,
X0 int not null,
X1 int not null,
CONSTRAINT CK_Valid CHECK(0 <= X0 and X0 < X1)
)
go
insert into Blah (ID,X0,X1)
select 1,0,500 union all
select 2,2,250 union all
select 3,251,499 union all
select 4,55,56 union all
select 5,90,94 union all
select 6,300,400
go
update
Blah
set X0 = b.X0 - decr.DecX0,
X1 = b.X1 - decr.DecX1
from
Blah b
inner join
(select
ID,X0,X1,
(select count(*) from Numbers where Num < b.X0 and Num not in (select
X0 from Blah) and Num not in (select X1 from Blah)) as DecX0,
(select count(*) from Numbers where Num < b.X1 and Num not in (select
X1 from Blah) and Num not in (select X0 from Blah)) as DecX1
from
Blah b) decr
on
b.ID = decr.ID
go
select * from Blah
go
drop table Blah
go
drop table Numbers
go
course if you've already got a numbers table, I'd take out the first
and last steps. If you don't, create one (course, you might need a
larger range, depending on your system). If you do have one, I'd
recommend removing some bits from my script (like the drop...)
Damien|||CREATE VIEW LftRgt(seq)
AS SELECT lft FROM Tree
UNION ALL
SELECT rgt FROM Tree;
UPDATE Tree
SET lft = (SELECT COUNT(*)
FROM LftRgt
WHERE seq <= lft),
rgt = (SELECT COUNT(*)
FROM LftRgt
WHERE seq <= rgt);
This will preserve the algebriac property that (rgt-lft +1)/2 = size of
subtree rooted at this node.
--CELKO--
Please post DDL in a human-readable format and not a machine-generated
one. This way people do not have to guess what the keys, constraints,
DRI, datatypes, etc. in your schema are. Sample data is also a good
idea, along with clear specifications.
*** Sent via Developersdex http://www.examnotes.net ***|||>> Why does it matter if there are gaps? In the one project I've used
that technique on, we actually implemented gaps on purpose in order to
reduce the number of updates that would have to take place any time a
new row was inserted... Gaps do not change the behavior of
the mathematics <<
Not quite. The "between-ness" property is handy for structural queries.
But the "algebraic" property (contigous lft-rgt numbering) provides a
simple validation of the tree and give you the size of the subtree at
that node = (rgt-lft+1)/2.
I have some material on using gaps to speed up updates in TREES &
HIERARCHY IN SQL.
--CELKO--
Please post DDL in a human-readable format and not a machine-generated
one. This way people do not have to guess what the keys, constraints,
DRI, datatypes, etc. in your schema are. Sample data is also a good
idea, along with clear specifications.
*** Sent via Developersdex http://www.examnotes.net ***|||--CELKO-- wrote:
> the "algebraic" property (contigous lft-rgt numbering) provides a
> simple validation of the tree
Can this constraint be written formally?|||Celko,
well, im not sure if i'm way off, but when I run that update lft and rgt
gets same values...
view looks like this:
seq
1
2
3
9
11
14
22
8
4
10
16
15
Not sure if you or me need a coffee here :) I'll have one extra atleast :)
"--CELKO--" <remove.jcelko212@.earthlink.net> wrote in message
news:epclMltFGHA.3100@.tk2msftngp13.phx.gbl...
> CREATE VIEW LftRgt(seq)
> AS SELECT lft FROM Tree
> UNION ALL
> SELECT rgt FROM Tree;
> UPDATE Tree
> SET lft = (SELECT COUNT(*)
> FROM LftRgt
> WHERE seq <= lft),
> rgt = (SELECT COUNT(*)
> FROM LftRgt
> WHERE seq <= rgt);
> This will preserve the algebriac property that (rgt-lft +1)/2 = size of
> subtree rooted at this node.
>
> --CELKO--
> Please post DDL in a human-readable format and not a machine-generated
> one. This way people do not have to guess what the keys, constraints,
> DRI, datatypes, etc. in your schema are. Sample data is also a good
> idea, along with clear specifications.
>
> *** Sent via Developersdex http://www.examnotes.net ***|||Did you select from the view with an ORDER BY clause?
Adam Machanic
Pro SQL Server 2005, available now
http://www.apress.com/book/bookDisplay.html?bID=457
--
"Lasse Edsvik" <lasse@.nospam.com> wrote in message
news:%23vtw$X1FGHA.2300@.TK2MSFTNGP15.phx.gbl...
> Celko,
> well, im not sure if i'm way off, but when I run that update lft and rgt
> gets same values...
> view looks like this:
> seq
> 1
> 2
> 3
> 9
> 11
> 14
> 22
> 8
> 4
> 10
> 16
> 15
> Not sure if you or me need a coffee here :) I'll have one extra atleast :)
>
> "--CELKO--" <remove.jcelko212@.earthlink.net> wrote in message
> news:epclMltFGHA.3100@.tk2msftngp13.phx.gbl...
>|||Adam,
I dont see how:
SELECT COUNT(*)
FROM LftRgt
WHERE seq <= rgt
and...
SELECT COUNT(*)
FROM LftRgt
WHERE seq <= lft
would get different values with an order by clause
"Adam Machanic" <amachanic@.hotmail._removetoemail_.com> wrote in message
news:O5A9Hr3FGHA.1760@.TK2MSFTNGP10.phx.gbl...
> Did you select from the view with an ORDER BY clause?
>
> --
> Adam Machanic
> Pro SQL Server 2005, available now
> http://www.apress.com/book/bookDisplay.html?bID=457
> --
>
> "Lasse Edsvik" <lasse@.nospam.com> wrote in message
> news:%23vtw$X1FGHA.2300@.TK2MSFTNGP15.phx.gbl...
:)
>