Hierachical structures - an overview

[Mike MacSween]

I have an app I need a hierachical structure for. There seem to be 3 ways of
implementing this, as far as I can see:

1. Adjacency list.
Pros - intuitive and relatively simple
Cons - not easily accesible via standard SQL, needs recusive queries to
crawl up or down the structure. I'll be doing this in Jet or perhaps MS SQL
Server, so Oracle's Connect by is out.

2. Nested Sets a la Joe Celko's BOM.
Pros - easy to access the structure via standard SQL
Cons - expensive/complex when the structure changes frequently.

3. Materialised Paths.
Pros - easy to access the structure via standSQL, the hierachy is obvious
and stored in a single field.
Cons - None? The value in the 'path' field doesn't _appear_ to be atomic,
that might well be a debatable point.

1a. Adjacency list + as per:
http://fungus.teststation.com/~jon/t...eeHandling.htm
Not sure about this. It claims to give the path upwards. It looks like it
merely gives the ancestors, which isn't the same thing.

Any other techniques?

Any other pros and cons?

Yours, Mike MacSween

[Lyle Fairfield]

"Mike MacSween" <mi******************@btinternet.com> wrote in
news:3f***********************@news.aaisp.net.uk:

I have an app I need a hierachical structure for. There seem to be 3
ways of implementing this, as far as I can see:

1. Adjacency list.
Pros - intuitive and relatively simple
Cons - not easily accesible via standard SQL, needs recusive queries to
crawl up or down the structure. I'll be doing this in Jet or perhaps MS
SQL Server, so Oracle's Connect by is out.

2. Nested Sets a la Joe Celko's BOM.
Pros - easy to access the structure via standard SQL
Cons - expensive/complex when the structure changes frequently.

3. Materialised Paths.
Pros - easy to access the structure via standSQL, the hierachy is
obvious and stored in a single field.
Cons - None? The value in the 'path' field doesn't _appear_ to be
atomic, that might well be a debatable point.

1a. Adjacency list + as per:
http://fungus.teststation.com/~jon/t...eeHandling.htm
Not sure about this. It claims to give the path upwards. It looks like
it merely gives the ancestors, which isn't the same thing.

Any other techniques?

Any other pros and cons?

Yours, Mike MacSween

A Google Search for "Hierarchical Databases" brings up several thousand
(3860) references. The first twenty are somewhat similar, but scarcely
definitive in any helpful (to me) way. Generally they are described as
being like trees, or directory structures, or "Information Management
Systems" of the past. One points out a common problem: a child with more
than one parent.

I think you have been descriptive of your needs in another thread. But
perhaps, in this one, you could delineate a particular problem or situation
dealing effectively with which requires specific design consideration.

I would find this helpful.

--
Lyle
(for e-mail refer to http://ffdba.com/contacts.htm)

[rkc]

"Mike MacSween" <mi******************@btinternet.com> wrote in message
news:3f***********************@news.aaisp.net.uk.. .

I have an app I need a hierachical structure for. There seem to be 3 ways of implementing this, as far as I can see:

All I can say is don't let factors associated with high stress enterprise
level
systems dissuade you from using a simple method that works just fine when
applied to a desktop application. There may be a point where recursive
methods are noticeably slow, but will you ever reach that point?

[Lennart Jonsson]

"Mike MacSween" <mi******************@btinternet.com> wrote in message news:<3f***********************@news.aaisp.net.uk> ...

I have an app I need a hierachical structure for. There seem to be 3 ways of
implementing this, as far as I can see:

[...]

1a. Adjacency list + as per:
http://fungus.teststation.com/~jon/t...eeHandling.htm
Not sure about this. It claims to give the path upwards. It looks like it
merely gives the ancestors, which isn't the same thing.

In what way does this differ? Are you meaning that the set of
ancestors is unordered, compared to the path? In that case the path is
easy to create from the ancestor set.

It is also possible to create a total ordering of a subtree and
thereby do, for example an inorder traversal. However, this becomes
impractical for relatively small subtrees since the total ordering is
prox O(n^2) (where n is the cardinality of the ancestor relation for
the subtree)

Any other techniques?

Recursive SQL. It is supported by atleast two databases, DB2 (WITH)
and Oracle (CONNECT BY).

+ You dont have to change anything in the way data is represented
(assuming adj. ,list)

- Performance (I have tried it far to little to claim this, but this
is my impression so far)

Also, IMO the syntax/semantics is a bit weird (compared to other
languages, I've encountered)

[...]

Kind regards
/Lennart

[Mike MacSween]

"Lyle Fairfield" <Mi************@Invalid.Com> wrote in message
news:Xn*******************@130.133.1.4...

A Google Search for "Hierarchical Databases" brings up several thousand
(3860) references. The first twenty are somewhat similar, but scarcely
definitive in any helpful (to me) way. Generally they are described as
being like trees, or directory structures, or "Information Management
Systems" of the past.
Thanks Lyle. Yes, I've done Google searches, and come up with the 3
approaches I've quoted. That's the reason for this post.
One points out a common problem: a child with more
than one parent.
Yes, and I've just established from the client that that isn't a
requirement. Thank god.
I think you have been descriptive of your needs in another thread. But
perhaps, in this one, you could delineate a particular problem or situation dealing effectively with which requires specific design consideration.

Sure. But I'll briefly re-iterate for the benefit of anyone who hasn't seen
those threads. It's an orchestral management system. The area of the schema
that I think needs to be hierachical is the Tour-Concerts section. Like
this:

World Tour has
Regional sections has
Country tours has
State tours has
City concerts has
Rehearsal, afternoon concert, evening concert.

But the hierachy could range from that (5-10 levels would do it, I think) to
a simple string quartet playing at a wedding - 1 level.

People (musicians) can be booked in at any level. An arranger (writes music)
for the whole tour, but doesn't need to turn up at anything else. Players
need to be booked in at the lowest level, the concert. And any level in
between.

Potential problem: Let's say I use an adjacency list as a structure. When
the client calls me, she says - 'Can I book you for Carousel next year Mike,
not sure of the dates but its 19-26 of October'. I say OK. All she has so
far is a single event, lasting a week. So once I'm booked on it I'm a record
in a junction table between the Events table and the Musicians table. Then
she finds out the dates. She enters them, as 'sub-events' of the week long
event. Children of the parent. No doubt I have some event handler that says
'you are entering dates for this show, do you want everyone so far booked
onto the show to be booked onto each event' or some such. She clicks yes.
There are now 2 entries (probably 8, one for the week, one for each night)
in that junction table. At a relational level it looks OK. But at a
'logical' level I'm entered twice for the same 'thing'. There should be no
need for me to be entered for both the parent and the child. If I'm entered
for the child it's obvious I'm entered for the parent too. Update query
needed? Probably. At which point the difficulty of querying up the tree
using standard SQL in an adjacency list might be a problem. There's more.
What if she deletes every single sub event when she realises she's got it
wrong. She'll have to re-enter the musos onto the parent event. But maybe
rare enough not to worry about.

Cheers, Mike

[Mike MacSween]

"Lennart Jonsson" <le*****@kommunicera.umea.se> wrote in message

1a. Adjacency list + as per:
http://fungus.teststation.com/~jon/t...eeHandling.htm
Not sure about this. It claims to give the path upwards. It looks like it merely gives the ancestors, which isn't the same thing.

Thanks you for putting me onto that in the first place
In what way does this differ? Are you meaning that the set of
ancestors is unordered, compared to the path?
I think so
In that case the path is
easy to create from the ancestor set.
No doubt. I'll have a go (unless you can do it off the top of your head).
It is also possible to create a total ordering of a subtree and
thereby do, for example an inorder traversal. However, this becomes
impractical for relatively small subtrees since the total ordering is
prox O(n^2) (where n is the cardinality of the ancestor relation for
the subtree)

Any other techniques?

Recursive SQL. It is supported by atleast two databases, DB2 (WITH)
and Oracle (CONNECT BY).

This will be Jet or SQL Server.

Thanks, Mike MacSween

[Mike MacSween]

"rkc" <rk*@yabba.dabba.do.rochester.rr.nope> wrote in message
news:HM*******************@twister.nyroc.rr.com...

"Mike MacSween" <mi******************@btinternet.com> wrote in message
news:3f***********************@news.aaisp.net.uk.. .

I have an app I need a hierachical structure for. There seem to be 3

ways of

implementing this, as far as I can see:

All I can say is don't let factors associated with high stress enterprise
level
systems dissuade you from using a simple method that works just fine when
applied to a desktop application. There may be a point where recursive
methods are noticeably slow, but will you ever reach that point?

You may very well be right. I could well end up using a maximum number of
levels. Which would no doubt make any recursive queries easier to write and
faster to run. Even perhaps having a 'level' field in each event.

Yours, Mike MacSween

[--CELKO--]

>> I have an app I need a hierachical structure for. There seem to be
3 ways of implementing this, as far as I can see: <<

I have a whole book on "Trees & Hierarchy in SQL" in production now,
which is due out in April 2004. There are several variations on these
three basic methods.

For example, Vadim T. has a modified Nested Sets model, the "Nested
Intervals" that uses (a,b) pairs of integers to represent rational
numbers so that you can do frequent insertions.

I am obligated to defend the nested sets model, since I made it
popular in SQL FOR SMARTIES.

[Paul]

mi******************@btinternet.com says...

World Tour has
Regional sections has
Country tours has
State tours has
City concerts has
Rehearsal, afternoon concert, evening concert. But the hierachy could range from that (5-10 levels would do it, I think) to
a simple string quartet playing at a wedding - 1 level.

Why not have a table

World tour

a table

Regional section

a table

Country tour

a table

State tour

a table

City concert

& further down if necessary?
I've followed this a wee bit, and am puzzled as to why different tables
cannot do what you want, as opposed to having all the data in one table
- maybe you could clarify?

Paul...

--
plinehan y_a_h_o_o and d_o_t com
C++ Builder 5 SP1, Interbase 6.0.1.6 IBX 5.04 W2K Pro
Please do not top-post.

"XML avoids the fundamental question of what we should do,
by focusing entirely on how we should do it."

quote from http://www.metatorial.com

[Roger]

I'm not sure why 'nested sets are expensive when the structure
changes' ??
in the mdb example that I emailed you, the fields subject, content and
communication date could be put in tblContact (or a new one) so that
the mechanism to add nodes to trees never changes, just the contents
of ornament (tblContact or tbl...) does

"Mike MacSween" <mi******************@btinternet.com> wrote in message news:<3f***********************@news.aaisp.net.uk> ...

I have an app I need a hierachical structure for. There seem to be 3 ways of
implementing this, as far as I can see:

1. Adjacency list.
Pros - intuitive and relatively simple
Cons - not easily accesible via standard SQL, needs recusive queries to
crawl up or down the structure. I'll be doing this in Jet or perhaps MS SQL
Server, so Oracle's Connect by is out.

2. Nested Sets a la Joe Celko's BOM.
Pros - easy to access the structure via standard SQL
Cons - expensive/complex when the structure changes frequently.

3. Materialised Paths.
Pros - easy to access the structure via standSQL, the hierachy is obvious
and stored in a single field.
Cons - None? The value in the 'path' field doesn't _appear_ to be atomic,
that might well be a debatable point.

1a. Adjacency list + as per:
http://fungus.teststation.com/~jon/t...eeHandling.htm
Not sure about this. It claims to give the path upwards. It looks like it
merely gives the ancestors, which isn't the same thing.

Any other techniques?

Any other pros and cons?

Yours, Mike MacSween

[Mike MacSween]

"Paul" <pa**@not.a.chance.ie> wrote in message
news:MP************************@news1.eircom.net.. .

Why not have a table

World tour

a table

Regional section

a table

Country tour

a table

State tour

a table

City concert

& further down if necessary?
I've followed this a wee bit, and am puzzled as to why different tables
cannot do what you want, as opposed to having all the data in one table
- maybe you could clarify?

Because sometimes it's just - Simon Foreman's Barmitzvah. One event

Mike

[Mike MacSween]

"Roger" <le*********@natpro.com> wrote in message
news:8c**************************@posting.google.c om...

I'm not sure why 'nested sets are expensive when the structure
changes' ??
in the mdb example that I emailed you, the fields subject, content and
communication date could be put in tblContact (or a new one) so that
the mechanism to add nodes to trees never changes, just the contents
of ornament (tblContact or tbl...) does

I'll look at it in more detail. Thanks very much Roger for sending me that.

Yours, Mike

[Lyle Fairfield]

"Mike MacSween" <mi******************@btinternet.com> wrote in
news:3f***********************@news.aaisp.net.uk:

"Lyle Fairfield" <Mi************@Invalid.Com> wrote in message
news:Xn*******************@130.133.1.4...

A Google Search for "Hierarchical Databases" brings up several thousand
(3860) references. The first twenty are somewhat similar, but scarcely
definitive in any helpful (to me) way. Generally they are described as
being like trees, or directory structures, or "Information Management
Systems" of the past.

Thanks Lyle. Yes, I've done Google searches, and come up with the 3
approaches I've quoted. That's the reason for this post.

One points out a common problem: a child with more
than one parent.

Yes, and I've just established from the client that that isn't a
requirement. Thank god.

I think you have been descriptive of your needs in another thread. But
perhaps, in this one, you could delineate a particular problem or

situation

dealing effectively with which requires specific design consideration.

Sure. But I'll briefly re-iterate for the benefit of anyone who hasn't
seen those threads. It's an orchestral management system. The area of
the schema that I think needs to be hierachical is the Tour-Concerts
section. Like this:

World Tour has
Regional sections has
Country tours has
State tours has
City concerts has
Rehearsal, afternoon concert, evening concert.

But the hierachy could range from that (5-10 levels would do it, I
think) to a simple string quartet playing at a wedding - 1 level.

People (musicians) can be booked in at any level. An arranger (writes
music) for the whole tour, but doesn't need to turn up at anything else.
Players need to be booked in at the lowest level, the concert. And any
level in between.

Potential problem: Let's say I use an adjacency list as a structure.
When the client calls me, she says - 'Can I book you for Carousel next
year Mike, not sure of the dates but its 19-26 of October'. I say OK.
All she has so far is a single event, lasting a week. So once I'm booked
on it I'm a record in a junction table between the Events table and the
Musicians table. Then she finds out the dates. She enters them, as
'sub-events' of the week long event. Children of the parent. No doubt I
have some event handler that says 'you are entering dates for this show,
do you want everyone so far booked onto the show to be booked onto each
event' or some such. She clicks yes. There are now 2 entries (probably
8, one for the week, one for each night) in that junction table. At a
relational level it looks OK. But at a 'logical' level I'm entered twice
for the same 'thing'. There should be no need for me to be entered for
both the parent and the child. If I'm entered for the child it's obvious
I'm entered for the parent too. Update query needed? Probably. At which
point the difficulty of querying up the tree using standard SQL in an
adjacency list might be a problem. There's more. What if she deletes
every single sub event when she realises she's got it wrong. She'll have
to re-enter the musos onto the parent event. But maybe rare enough not
to worry about.

Cheers, Mike

I would be inclined to reverse the hierachy, I think, starting with events
(at the top), which may be linked to "acts" or descriptors such as "state
tour". Something dynamic like musicians who are members of acts could be
handled by linking the event-act link to musicians, (I've done something a
tiny bit like this with telephone numbers where a person is linked to 6
numbers, and the links are linked to type, such as home, office, table)
while static items such as state tours which are members of country tours
could be mapped directly.
An act could, of course, be a solo.

--
Lyle
(for e-mail refer to http://ffdba.com/contacts.htm)

[Lee Fesperman]

Lennart Jonsson wrote:

"Mike MacSween" <mi******************@btinternet.com> wrote in message news:<3f***********************@news.aaisp.net.uk> ...

I have an app I need a hierachical structure for. There seem to be 3 ways of
implementing this, as far as I can see:

....

Any other techniques?

Recursive SQL. It is supported by atleast two databases, DB2 (WITH)
and Oracle (CONNECT BY).

Recursive SQL is also supported by FirstSQL/J (see my sig). It uses an Oracle-like
CONNECT BY syntax.

--
Lee Fesperman, FirstSQL, Inc. (http://www.firstsql.com)
================================================== ============
* The Ultimate DBMS is here!
* FirstSQL/J Object/Relational DBMS (http://www.firstsql.com)

[Lennart Jonsson]

"Mike MacSween" <mi******************@btinternet.com> wrote in message news:<3f***********************@news.aaisp.net.uk> ...

"Lennart Jonsson" <le*****@kommunicera.umea.se> wrote in message

1a. Adjacency list + as per:
http://fungus.teststation.com/~jon/t...eeHandling.htm
Not sure about this. It claims to give the path upwards. It looks like it merely gives the ancestors, which isn't the same thing.

Thanks you for putting me onto that in the first place

In what way does this differ? Are you meaning that the set of
ancestors is unordered, compared to the path?

I think so

Guess it all comes down to how path is defined. In the doc it is
defined as a union -> a set -> unorderd

In that case the path is
easy to create from the ancestor set.

No doubt. I'll have a go (unless you can do it off the top of your head).

Just count the number of ancestors for each ancestor in the path. I.e
something like:

select
p.ancestor_id,
(select count(1) from path where id = p.ancestor_id) as depth
from
path p
where
id = ?
order by depth

[...]

HTH
/Lennart

[Lennart Jonsson]

Lee Fesperman <fi******@ix.netcom.com> wrote in message news:<3F***********@ix.netcom.com>...

Lennart Jonsson wrote:

"Mike MacSween" <mi******************@btinternet.com> wrote in message news:<3f***********************@news.aaisp.net.uk> ...

I have an app I need a hierachical structure for. There seem to be 3 ways of

[...]
Recursive SQL is also supported by FirstSQL/J (see my sig). It uses an Oracle-like
CONNECT BY syntax.

Thanks, I'll try to keep that in mind
Regards
/Lennart

[Mark Johnson]

jo*******@northface.edu (--CELKO--) wrote:

I have an app I need a hierachical structure for. There seem to be

3 ways of implementing this, as far as I can see: <<

I have a whole book on "Trees & Hierarchy in SQL" in production now,
which is due out in April 2004. There are several variations on these
three basic methods.

For example, Vadim T. has a modified Nested Sets model, the "Nested
Intervals" that uses (a,b) pairs of integers to represent rational
numbers so that you can do frequent insertions.

I am obligated to defend the nested sets model, since I made it
popular in SQL FOR SMARTIES.

In your opinion, what ultimately might be the best general solution to
the problem - adjacency lists with recursive SQL? Materialized path
and the overhead to maintain it? Or your nested sets, with wide
intervals?

[David Morse]

HI,

You can use FirstSQL/J ORDBMS and access the data with CONNECT BY to get at
hierarchical data with recursive queries.

See http://www.firstsql.com/connectby.shtml for complete details.

Dave M.
"Mike MacSween" <mi******************@btinternet.com> wrote in message
news:3f***********************@news.aaisp.net.uk.. .

I have an app I need a hierachical structure for. There seem to be 3 ways of implementing this, as far as I can see:

1. Adjacency list.
Pros - intuitive and relatively simple
Cons - not easily accesible via standard SQL, needs recusive queries to
crawl up or down the structure. I'll be doing this in Jet or perhaps MS SQL Server, so Oracle's Connect by is out.

2. Nested Sets a la Joe Celko's BOM.
Pros - easy to access the structure via standard SQL
Cons - expensive/complex when the structure changes frequently.

3. Materialised Paths.
Pros - easy to access the structure via standSQL, the hierachy is obvious
and stored in a single field.
Cons - None? The value in the 'path' field doesn't _appear_ to be atomic,
that might well be a debatable point.

1a. Adjacency list + as per:
http://fungus.teststation.com/~jon/t...eeHandling.htm
Not sure about this. It claims to give the path upwards. It looks like it
merely gives the ancestors, which isn't the same thing.

Any other techniques?

Any other pros and cons?

Yours, Mike MacSween

[Mikito Harakiri]

The major problem with connect-by is that it doesn't seem to differentiate
between nodes and edges of the graph, which is very confusing for the end
user. For a graph being a tree the matter seems simple, as we can implicitly
associate a node with the adjacent edge (although, there is an confusing
ambiguity of 2 choices here as well). The second problem is that it is
difficult to cost connect-by access method. Basically if you sees the
execution plan with connect-by, then you can ignore the cost:-)

I'm awaiting SQL Server Yukon release (I assume there is free developers
version:-) to get my hands on "the latest and greatest" "recursive with"
method...

"David Morse" <da******@comcast.net> wrote in message
news:RKzPb.115674$I06.806127@attbi_s01...

HI,

You can use FirstSQL/J ORDBMS and access the data with CONNECT BY to get at hierarchical data with recursive queries.

See http://www.firstsql.com/connectby.shtml for complete details.

Dave M.
"Mike MacSween" <mi******************@btinternet.com> wrote in message
news:3f***********************@news.aaisp.net.uk.. .

I have an app I need a hierachical structure for. There seem to be 3 ways

of

implementing this, as far as I can see:

1. Adjacency list.
Pros - intuitive and relatively simple
Cons - not easily accesible via standard SQL, needs recusive queries to
crawl up or down the structure. I'll be doing this in Jet or perhaps MS

SQL

Server, so Oracle's Connect by is out.

2. Nested Sets a la Joe Celko's BOM.
Pros - easy to access the structure via standard SQL
Cons - expensive/complex when the structure changes frequently.

3. Materialised Paths.
Pros - easy to access the structure via standSQL, the hierachy is

obvious and stored in a single field.
Cons - None? The value in the 'path' field doesn't _appear_ to be atomic, that might well be a debatable point.

1a. Adjacency list + as per:
http://fungus.teststation.com/~jon/t...eeHandling.htm
Not sure about this. It claims to give the path upwards. It looks like it merely gives the ancestors, which isn't the same thing.

Any other techniques?

Any other pros and cons?

Yours, Mike MacSween