Page 1 of 2 12 LastLast
Results 1 to 15 of 23
  1. #1
    Join Date
    Jun 2007
    Location
    London
    Posts
    2,527

    Hierarchy structures in databases

    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

  2. #2
    Join Date
    Apr 2002
    Location
    Toronto, Canada
    Posts
    20,002
    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
    rudy.ca | @rudydotca
    Buy my SitePoint book: Simply SQL

  3. #3
    Join Date
    Jun 2007
    Location
    London
    Posts
    2,527
    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

  4. #4
    Join Date
    Apr 2002
    Location
    Toronto, Canada
    Posts
    20,002
    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
    rudy.ca | @rudydotca
    Buy my SitePoint book: Simply SQL

  5. #5
    Join Date
    Jun 2007
    Location
    London
    Posts
    2,527
    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?

  6. #6
    Join Date
    Apr 2002
    Location
    Toronto, Canada
    Posts
    20,002
    Quote Originally Posted by mike_bike_kite
    Even the nested sets and materialized paths you propose appear to be just different ways of representing hierarchical data.
    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
    rudy.ca | @rudydotca
    Buy my SitePoint book: Simply SQL

  7. #7
    Join Date
    Jun 2007
    Location
    London
    Posts
    2,527
    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

  8. #8
    Join Date
    Apr 2002
    Location
    Toronto, Canada
    Posts
    20,002
    sorry, can't answer your last question
    rudy.ca | @rudydotca
    Buy my SitePoint book: Simply SQL

  9. #9
    Join Date
    Jun 2003
    Location
    Ohio
    Posts
    12,592
    Quote Originally Posted by mike_bike_kite
    What are the basic criteria for deciding when to use the nested sets and materialized paths over standard hierarchies?
    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.
    If it's not practically useful, then it's practically useless.

    blindman
    www.chess.com: "sqlblindman"
    www.LobsterShot.blogspot.com

  10. #10
    Join Date
    Jun 2007
    Location
    London
    Posts
    2,527
    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

  11. #11
    Join Date
    Feb 2004
    Location
    One Flump in One Place
    Posts
    14,912
    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?

  12. #12
    Join Date
    Dec 2007
    Posts
    2
    Quote Originally Posted by mike_bike_kite
    What are the basic criteria for deciding when to use the nested sets and materialized paths over standard hierarchies?
    Mike
    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

  13. #13
    Join Date
    Jun 2007
    Location
    London
    Posts
    2,527
    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

  14. #14
    Join Date
    Jun 2003
    Location
    Ohio
    Posts
    12,592
    I think the decision is between Nested Set and Adjacency models. I've never used Materialized Path, and doubt that I ever will.
    If it's not practically useful, then it's practically useless.

    blindman
    www.chess.com: "sqlblindman"
    www.LobsterShot.blogspot.com

  15. #15
    Join Date
    Jun 2003
    Location
    Ohio
    Posts
    12,592
    Quote Originally Posted by mike_bike_kite
    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.
    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.
    If it's not practically useful, then it's practically useless.

    blindman
    www.chess.com: "sqlblindman"
    www.LobsterShot.blogspot.com

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •