I always thought hierarchies were quite useful in a databases ie good for representing structures of offices, people, product hierarchies etc. After suggesting them as a soloution to two posts this week ( 1 2 ) I find there appears to be some reluctance to using hierarchies - can anyone say why?

They are obviously a bit more involved than a simple join but it's not rocket science - I seem to remember Oracle even has extra functionality built into it's SQL to help. I do accept it's a bit more difficult to code, I also accept it's slightly slower than a simple join but these types of structure provide a lot of power.

Is there a better way of handling hierarchy information or do people just avoid these types of structures?

Mike

there is only a reluctance to use a hammer when clearly some other tool is more appropriate

also, i should like to point out that there is more than one way of representing a hierarchy

when you suggest parentOfficeId or childName, parentName, these are examples of the adjacency list data model for hierarchies

there are other ways, including nested sets and materialized paths

the "some reluctance" that you may have detected was merely me suggesting that a hierarchy was over-complicating matters in a particular situation where no hierarchy was needed at all

As you say, there are as many ways to represent just about anything but I'm genuinly curious why a hierarchical method isn't the optimal method of storing what appears to be hierarchical data. I did google nested sets and materialized paths and could see that they may work but find it very difficult to believe they're a simpler solution.

Could you explain what I'm missing?

Mike

that's the whole point, mike

just because something appears (emphasis: to you) to be hierarchical data, this does not imply that one should use a hierarchical model to store it

I accept your point but what would be a better answer than the hierarchy? To me the original problem is screaming out "hierarchy". Even the nested sets and materialized paths you propose appear to be just different ways of representing hierarchical data. I'm confused - how should the data be represented?

yep, that's what they are

why use a hierarchy when you don't really need one?

as i said in that thread...

in the real world, every different variation has its own "stock keeping unit" and barcode (do a search for GTIN and GS1)

there's no product hierarchy in the GS1 database, and i should know, i've worked on it

Must admit I haven't produced any product databases so I'll have to bow out to your experience. We certainly use a lot of hierarchies in financial reporting systems though and they seem to work well. If you cache the hierarchy data in a "flat" table then the queries are no more complex than a standard query and obviously faster than calculating the hierarchy each time.

What are the basic criteria for deciding when to use the nested sets and materialized paths over standard hierarchies?

Mike

sorry, can't answer your last question

Here are some good rules of thumb on which model to implement:

Use multiple tables when you want to ensure that the company cannot replace you with a DBA making under $40,000 per year.

Use the Adjency Model when you want to ensure that the company cannot replace you with a DBA making under $70,000 per year.

Use Nested Sets when you want to ensure that the company cannot replace you with a DBA making under $100,000 per year.

Very good!

The funny thing is I found some SQL code yesterday that I just couldn't work out (and the current team couldn't explain what it was doing either). Having read up on this stuff I now realise it's a nested set hierarchy - how about that for a coincidence! This forum is very educational

Mike

I had heard, but do not know, that nested sets have an a degree of exposure that is disproportionate to their use in the real world.
In other words (English this time) - they get discussed a lot but rarely make it into production. Anyone any experience to the contrary?

I've used both models extensively,so here is quick summary:

Nested Sets:
- space efficient (2 ints per node)
- unlimited tree depth
- very fast access to direct/all ancestors
- very fast access to direct/all descendants
- *VERY* slow inserts / updates / deletes

Materialized path:
- lots of space wasted
- limited tree depth
- fast access to all ancestors
- moderately fast access to direct ancestors
- fast access to all descendants
- moderately fast access to direct descendants
- fast inserts / updates / deletes

I prefer Nested Sets for mostly static hierarchies with lots of nodes, space/speed advantage over Materialized Path is noticable.

For everything else I recommend using Materialized Path.

Pavel Urbancik

Thanks for the response!

How do these methods compare with:

• the rather bog standard hierarchic table with parent and child fields
• the addition of a cached hierarchic table where accessing a parent in the cache table will result in all the child records without looping etc.

Are there issues with the readability of the code - the SQL code doesn't look at all obvious to me - perhaps senility is finally setting in.

Mike

I think the decision is between Nested Set and Adjacency models. I've never used Materialized Path, and doubt that I ever will.

Have you tried coding binary searches with SQLSVR 2005's new Common Table Expressions? That will determine whether you are still a young enough dog to learn new tricks...it took me several tries to get the hang of it.