Nested Set / Traversal Tree into Breadcrumb Trail

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 / Traversal Tree into Breadcrumb Trail

Author

Topic

AdyGould
Starting Member

3 Posts

Posted - 2004-04-05 : 18:34:33

I have been reading the various threads on SQLTeam.com and seen some pointers to the question I have a problem with, taking a Nested Set and creating a breadcrumb style trail for all nodes.

I have a database with locations complete with leftSide and rightSide numbering, and a locationID. DDL is:


CREATE TABLE tblLocations2 (
  locationID int(10) unsigned NOT NULL auto_increment,
  location varchar(128) NOT NULL default '',
  parent int(10) unsigned default NULL,
  leftSide int(10) unsigned default NULL,
  rightSide int(10) unsigned default NULL,
  PRIMARY KEY  (locationID),
  UNIQUE KEY locationID (locationID),
  KEY Location (location,parent)
);

INSERT INTO 
  tblLocations2 (locationID, location, parent, leftSide, rightSide) VALUES 
(1, 'World', NULL, 1, 102),
(2, 'Australia', 1, 2, 53),
(3, 'Western Australia', 2, 3, 24),
(4, 'New South Wales', 2, 25, 36),
(5, 'Australian Capital Territory', 2, 37, 40),
(6, 'Perth', 3, 4, 5),
(7, 'Canberra', 5, 38, 39),
(8, 'Sydney', 4, 26, 27),
(10, 'Bayswater', 3, 6, 7),
(11, 'Bassendean', 3, 8, 9),
(12, 'Tasmania', 2, 41, 46),
(13, 'Britain', 1, 54, 93),
(14, 'Greater London', 88, 56, 65),
(20, 'California', 16, 95, 100),
(16, 'United States of America', 1, 94, 101),
(17, 'San Francisco', 20, 96, 97),
(18, 'Victoria', 2, 47, 52),
(19, 'Melbourne', 18, 48, 49),
(25, 'Kalgoorlie-Boulder', 3, 10, 11),
(26, 'Northam', 3, 12, 13),
(27, 'Midland', 3, 14, 15),
(28, 'Fremantle', 3, 16, 17),
(29, 'Cottesloe', 3, 18, 19),
(30, 'City Beach', 3, 20, 21),
(31, 'Two Rocks', 3, 22, 23),
(32, 'Hobart', 12, 42, 43),
(33, 'Launceston', 12, 44, 45),
(34, 'London', 14, 57, 58),
(35, 'Putney', 14, 59, 60),
(36, 'Clapham', 14, 61, 62),
(37, 'Croydon', 14, 63, 64),
(38, 'Newcastle', 4, 28, 29),
(39, 'Parramatta', 4, 30, 31),
(40, 'Katoomba', 4, 32, 33),
(41, 'Wentworth Falls', 4, 34, 35),
(42, 'Geelong', 18, 50, 51),
(44, 'Oxfordshire', 88, 66, 71),
(45, 'Buckinghamshire', 88, 72, 77),
(46, 'Kent', 88, 78, 79),
(47, 'Cornwall', 88, 80, 81),
(48, 'Dorset', 88, 82, 83),
(50, 'Oxford', 44, 67, 68),
(51, 'Henley-On-Thames', 44, 69, 70),
(52, 'Marlow', 45, 73, 74),
(56, 'Los Angeles', 20, 98, 99),
(87, 'High Wycombe', 45, 75, 76),
(88, 'England', 13, 55, 84),
(89, 'Northern Ireland', 13, 85, 86),
(90, 'Scotland', 13, 87, 88),
(91, 'Wales', 13, 89, 92),
(96, 'Cardiff', 91, 90, 91);

I want to extract a list of locations similar to:


World
World -> Australia
World -> Australia -> Western Australia
World -> Australia -> Western Australia -> Perth 
World -> Australia -> Western Australia -> Albany
World -> Australia -> Victoria
World -> Australia -> Victoria -> Melbourne
World -> Britain
World -> Britain -> Oxfordshire
etc

The trails would also have hyperlinks put into them when the trails are displayed.

I've not used SQL Server in any detail so I'll be hacking a bit to understand any solutions.

Have you any pointers to where a solution may be found for this problem? I know of J Celco's book, but have not located it here in WA at this time.

To make things worse, I'm in need of implementing the solution in a few days

Many thanks in advance

AjarnMark
SQL Slashing Gunting Master

3246 Posts

Posted - 2004-04-05 : 18:52:54

Hmmm.... This DDL and DML is not from SQL Server is it? I'm guessing from the structure of your INSERT statement that it's mySQL. Is that correct?

Have you read the articles on this site on the subject of trees?

--------------------------------------------------------------
Find more words of wisdom at [url]http://weblogs.sqlteam.com/markc[/url]

ValterBorges
Master Smack Fu Yak Hacker

1429 Posts

Posted - 2004-04-05 : 19:46:10

This is a job for analysis services. Creating hierchies is a snap.

AdyGould
Starting Member

3 Posts

Posted - 2004-04-05 : 21:39:12

quote:
Originally posted by AjarnMark

Hmmm.... This DDL and DML is not from SQL Server is it? I'm guessing from the structure of your INSERT statement that it's mySQL. Is that correct?

It is, but that should make little difference as far as the main 'theory' of solving the problem is concerened...

quote:

Have you read the articles on this site on the subject of trees?

Yes I have, and I am trying to understand the 'stored procedures' of SQL Server - as I said, little experience with the system.

I'd be happy with a pseudo-code explanation

AdyGould
Starting Member

3 Posts

Posted - 2004-04-05 : 21:42:19

quote:
Originally posted by ValterBorges

This is a job for analysis services. Creating hierchies is a snap.

I've got the hierarchy set up, and the insert, delete and update recursive tree to nested set tree all working.

I can retrieve a SINGLE node's path, for example:

select * from tblLocations where leftSide <= 8 AND rightSide >= 9;

What I am asking for is the next level, a list of all paths for all branches / nodes of the tree.

xpandre
Posting Yak Master

212 Posts

Posted - 2004-04-06 : 02:13:53

[code]create table #tree (id int, sequence varchar(1000), levelNo int)

insert #tree select locationid, location, 1 from
tblLocations2
where Parent is null

declare @i int

select @i = 0
-- keep going until no more rows added
while @@rowcount > 0
begin
select @i = @i + 1
insert #tree
-- Get all children of previous level
select tblLocations2.locationid, sequence + space(5) + tblLocations2.location, @i + 1
from tblLocations2, #tree
where #tree.levelNo = @i
and tblLocations2.Parent = #tree.id
end

select * from #tree
drop table #tree[/code]

[url]http://www.nigelrivett.net/RetrieveTreeHierarchy.html[/url]

byrmol
Shed Building SQL Farmer

1591 Posts

Posted - 2004-04-06 : 02:34:19

Ady,

You seem to have a mixture of the adjacency list and nested set..ParentID is redundant for the nested set method...

The first thing you should do when working with the nested set method is to create a View which resolves the "Level"


CREATE VIEW LocationsLevel
AS
SELECT L.Location, COUNT(*) AS Level, L.LeftSide as OrderBy
FROM tblLocations2 L
CROSS JOIN tblLocations2 X
WHERE l.leftside between x.leftside and x.rightSide
GROUP BY L.Location, L.LeftSide, L.RightSide

Once this view is in place, most queiries are relatively easy...
You would be after this for the full list.


SELECT REPLICATE('-', Level) + Location as Location
FROM LocationsLevel
ORDER BY OrderBy

DavidM

"If you are not my family or friend, then I will discriminate against you"

ValterBorges
Master Smack Fu Yak Hacker

1429 Posts

Posted - 2004-04-22 : 09:38:30

[What I am asking for is the next level, a list of all paths for all branches / nodes of the tree.]

MDX which operates on dimensional hierarchies has all the tree functionality you want, parent, child, cousin, sibling, next, previous, lag, lead, and many others..

Of course this assumes your trying to do reporting and not data entry.

Check it out.

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources