Re: Re^5: Efficiently Walking Large Data Structures Stored in Multiple Tables

I can see how selection isn't very difficult. Nested set trees look to be optimized for retrieval. My issue is modification. Updates to where you stand in the hierarchy (promotion, for example) aren't incredibly hard, unless your entire department moves with you to someone that never had a department under them before. Deletion doesn't look to be a big deal - you simply have to deal with the same problem you have in CONNECT BY, which is what to do with the entities under you.

I guess my biggest problem with the whole notion is the fact that I affect record A. In Oracle's tree representation (and I'm assuming PG's, as well), that's the end of it. With nested set trees, I might have to re-number the entire hierarchy's intervals. Granted, that's the pathological case, but it's still something you have to code for. And, that has to be checked in every modification. (Maybe not DELETE, but definitely for INSERT and UPDATE.)

Another thing that concerns me is how this might potentially affect triggers written against that table. Most developers work with tables that aren't nested sets. (I understand that's how RDBMS's think about things, but most developers of my acquaintance aren't as ... flexible.) The data structure, as a whole, looks very fragile to me. There's a lot of bookkeeping involved (unless I'm missing something obvious).

------
We are the carpenters and bricklayers of the Information Age.

Please remember that I'm crufty and crochety. All opinions are purely mine and all code is untested, unless otherwise specified.

Comment on Re: Re^5: Efficiently Walking Large Data Structures Stored in Multiple Tables

Replies are listed 'Best First'.
Re^7: Efficiently Walking Large Data Structures Stored in Multiple Tables by adrianh (Chancellor) on Mar 01, 2004 at 09:29 UTC
I guess my biggest problem with the whole notion is the fact that I affect record A. In Oracle's tree representation (and I'm assuming PG's, as well), that's the end of it. Just in case this wasn't clear before. If you're RDBMS supports tree structures natively use them. Using nested sets in this case is obviously a pointless reinvention of the wheel when you already have a native mechanism for querying/updating trees. However, if your DB doesn't support tree structures well or if you need to consider the possibility of migration to a DB that doesn't support them then nested sets are pretty darn good in my experience. With nested set trees, I might have to re-number the entire hierarchy's intervals. Yup. As I mentioned before insertion is O(N). You can make the average case a lot better by sneaky work with the intervals. However since the vast majority of applications read a lot more than they change the hierarchy the more efficient queries more than make up for the less efficient inserts. Another thing that concerns me is how this might potentially affect triggers written against that table. I fail to see how this is any more/less of an issue than any other representation? Most developers work with tables that aren't nested sets. (I understand that's how RDBMS's think about things, but most developers of my acquaintance aren't as ... flexible.) The data structure, as a whole, looks very fragile to me. There's a lot of bookkeeping involved (unless I'm missing something obvious). You wrap the bookkeeping in a client side API or stored procedures on the database side - just like you would with any other bits of repetitive SQL.	[reply]

Replies are listed 'Best First'.

Re^7: Efficiently Walking Large Data Structures Stored in Multiple Tables
by adrianh (Chancellor) on Mar 01, 2004 at 09:29 UTC

I guess my biggest problem with the whole notion is the fact that I affect record A. In Oracle's tree representation (and I'm assuming PG's, as well), that's the end of it.

Just in case this wasn't clear before. If you're RDBMS supports tree structures natively use them. Using nested sets in this case is obviously a pointless reinvention of the wheel when you already have a native mechanism for querying/updating trees.

However, if your DB doesn't support tree structures well or if you need to consider the possibility of migration to a DB that doesn't support them then nested sets are pretty darn good in my experience.

With nested set trees, I might have to re-number the entire hierarchy's intervals.

Yup. As I mentioned before insertion is O(N). You can make the average case a lot better by sneaky work with the intervals.

However since the vast majority of applications read a lot more than they change the hierarchy the more efficient queries more than make up for the less efficient inserts.

Another thing that concerns me is how this might potentially affect triggers written against that table.

I fail to see how this is any more/less of an issue than any other representation?

Most developers work with tables that aren't nested sets. (I understand that's how RDBMS's think about things, but most developers of my acquaintance aren't as ... flexible.) The data structure, as a whole, looks very fragile to me. There's a lot of bookkeeping involved (unless I'm missing something obvious).

You wrap the bookkeeping in a client side API or stored procedures on the database side - just like you would with any other bits of repetitive SQL.

[reply]