Nested Set Model (Trees): Clarification of Usage

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 (Trees): Clarification of Usage

Author

Topic

jmcbride
Starting Member

24 Posts

Posted - 2003-01-24 : 15:29:19

I have recently reviewed Joe Celko's article (http://www.intelligententerprise.com/001020/celko1_1.shtml)concerning designing and programming tables that hold "trees" of information (hierarchical listings). I now prefer his Nested Set Model over the typical Adjacency List Model.

I have some questions though about managing a Nested Set Model table and associated SQL statements. I do not completely understand this model but recognize that it is more effecient. How can I...

1. Add a leaf or branch to the middle of a structure? How do I go back and modify the entire structure to reflect this addition?
2. Delete a leaf or branch to the middle of a structure?

An associated SQL statement would be very helpful, along with a brief description.

THanks

--------------------
http://www.utsa.edu/

robvolk
Most Valuable Yak

15732 Posts

Posted - 2003-01-24 : 15:46:17

There are some links to Joe's earlier articles in this thread:

http://www.sqlteam.com/item.asp?ItemID=8866

They cover the various operations on nested set trees. He also covers them all in his book SQL For Smarties, which you should definitely buy if you want to do godlike things with SQL.

GreatInca
Posting Yak Master

102 Posts

Posted - 2003-01-25 : 12:20:04

Does the nested set model handle multiple parents per child? I think thats important for some category heirarchies.

How about not only querying underlings / childeren, but also cousins? or just all employees ranked lower than a person (all superviser level managers and all their employees with no particular middle manager in mind).

jmcbride
Starting Member

24 Posts

Posted - 2003-01-27 : 10:00:59

Ooh, that would be nice to know. Maybe you could just setup a seperate table to track extra relationships?

--------------------
http://www.utsa.edu/
(Joe) Joseph McBride

macka
Posting Yak Master

162 Posts

Posted - 2003-01-27 : 10:09:12

The nested set model handles trees quite well. But what you are referring to is a graph rather than a tree. Chapter 30 in Celko's - SQL for smarties covers this topic in some detail.

[url]http://www.amazon.com/exec/obidos/tg/detail/-/1558605762/qid=1043680152/sr=8-1/ref=sr_8_1/002-6168946-3216860?v=glance&s=books&n=507846#product-details[/url]

macka.

--
There are only 10 types of people in the world - Those who understand binary, and those who don't.

macka
Posting Yak Master

162 Posts

Posted - 2003-01-27 : 10:28:21

Has anyone come up with a good algorithmn for converting the adjacency model to nested sets, with the following proviso:

Children for a given parent must be ordered. For example, I have the following adjency model DDL:


CREATE TABLE Pages
(
PageID INTEGER NOT NULL,
Parent INTEGER,
DisplayOrder INTEGER NOT NULL
)

--and heres the DML:


INSERT INTO Pages (PageID,Parent,DisplayOrder)
SELECT 1,NULL,1
UNION
SELECT 2,1,1
UNION
SELECT 3,1,2
UNION
SELECT 4,1,3
UNION
SELECT 5,3,2
UNION
SELECT 6,3,3
UNION
SELECT 7,3,1

I need records 5,6 and 7 to be built in the order determined by the DisplayOrder column - in ascending order - ie. 7,5,6.

I've played with Page47's and Celko's code but to no avail.

Any ideas/pointers would be greatly appreciated.

Cheers,

macka.

--
There are only 10 types of people in the world - Those who understand binary, and those who don't.

GreatInca
Posting Yak Master

102 Posts

Posted - 2003-02-04 : 14:19:34

I have a table using adjancy currently its easy to update but its updated infrequently. So I use a pre-render table that for each row, has a base item, the reference item, its offset, common parent offset, and common parent id for every other item 6 levels up or six levels down (it goes up 6 then goes down 13 (+6 through 0 through -6). Therefore I can use a extremely quick and simple joinless query to find anything related to an item including cousins, 2nd cousins, etc... The disadvantage is that it takes about 30 minutes to rebuild whenever the base table gets changed (about once every few months).

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources