Hierachical structures - an overview

[Lennart Jonsson]

Re: Hierachical structures - an overview

Lee Fesperman <firstsql@ix.ne tcom.com> wrote in message news:<3FF8C953. 142F@ix.netcom. com>...[color=blue]
> Lennart Jonsson wrote:[color=green]
> >
> > "Mike MacSween" <mike.macsween. nospam@btintern et.com> wrote in message news:<3ff7e63a$ 0$52881$5a6aecb 4@news.aaisp.ne t.uk>...[color=darkred]
> > > I have an app I need a hierachical structure for. There seem to be 3 ways of[/color][/color][/color]

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

Thanks, I'll try to keep that in mind


Regards
/Lennart

[Mark Johnson]

Re: Hierachical structures - an overview

joe.celko@north face.edu (--CELKO--) wrote:
[color=blue][color=green][color=darkred]
>>> I have an app I need a hierachical structure for. There seem to be[/color][/color]
>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.[/color]

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]

Re: Hierachical structures - an overview

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" <mike.macsween. nospam@btintern et.com> wrote in message
news:3ff7e63a$0 $52881$5a6aecb4 @news.aaisp.net .uk...[color=blue]
> I have an app I need a hierachical structure for. There seem to be 3 ways[/color]
of[color=blue]
> 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[/color]
SQL[color=blue]
> 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
>
>
>[/color]

[Mikito Harakiri]

Re: Hierachical structures - an overview

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" <davem405@comca st.net> wrote in message
news:RKzPb.1156 74$I06.806127@a ttbi_s01...[color=blue]
> HI,
>
> You can use FirstSQL/J ORDBMS and access the data with CONNECT BY to get[/color]
at[color=blue]
> hierarchical data with recursive queries.
>
> See http://www.firstsql.com/connectby.shtml for complete details.
>
> Dave M.
> "Mike MacSween" <mike.macsween. nospam@btintern et.com> wrote in message
> news:3ff7e63a$0 $52881$5a6aecb4 @news.aaisp.net .uk...[color=green]
> > I have an app I need a hierachical structure for. There seem to be 3[/color][/color]
ways[color=blue]
> of[color=green]
> > 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[/color]
> SQL[color=green]
> > 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[/color][/color]
obvious[color=blue][color=green]
> > and stored in a single field.
> > Cons - None? The value in the 'path' field doesn't _appear_ to be[/color][/color]
atomic,[color=blue][color=green]
> > 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[/color][/color]
it[color=blue][color=green]
> > merely gives the ancestors, which isn't the same thing.
> >
> > Any other techniques?
> >
> > Any other pros and cons?
> >
> > Yours, Mike MacSween
> >
> >
> >[/color]
>
>[/color]