Re: Recursive use

On Tue, Oct 10, 2006 at 04:33:46PM -0500, Jay A. Kreibich wrote:
> On Tue, Oct 10, 2006 at 10:15:42AM -0500, Jim C. Nasby scratched on the wall:
> > On Fri, Oct 06, 2006 at 10:37:26AM -0500, Jay A. Kreibich wrote:
> > >   These are generally referred to as "Hierarchical Queries" and center
> > >   around the idea of a self-referencing table (such as an employee
> > >   table with a "manager" field that is a FK to another row in the same
> > >   table).  This essentially makes a tree-like structure.
> > <snip>
> > >   As pointed out by others, the most general way to deal with this in
> > >   PostgreSQL is to write PL/PgSQL (or some other language) functions
> > >   that can generate the specific queries you need.  It isn't always
> > >   pretty, but it can be made to work for a specific set of queries.
> >
> > There are also other ways to represent this type of information without
> > using hierarchical queries. Joe Celko presents two methods in SQL For
> > Smarties.
>
>   If you're referring to Joe's March 1996 DBMS article,
>   (http://www.dbmsmag.com/9603d06.html) he does demonstrate two models,

Nope... I'm talking about his book SQL For Smarties

>   For one, the table requires an extreme amount of maintenance-- something
>   as simple as inserting a single leaf node may require updating every
>   row in the whole table.  On average, more than half the nodes/rows will
>   require updating for each record insertion and removal, but it isn't clear
>   how this update process would work (since the sequences require a
>   traversal to update, but a proper traversal requires the correct
>   sequences).  There are tricks for the simple cases, but I'm not sure
>   you could do an update in-place in the general case.

The book goes into great detail about how to handle inserts and deletes.

Something he doesn't talk about that I think would be of use is putting
intentional gaps in the nested set. That would greatly reduce the
overhead of many operations (at the cost of added code complexity). For
example, if instead of incrementing each sequence by one, you
incremented by 10, you could insert 9 new values into one location in
the tree before you'd have to worry about moving other numbers around.

>   I also noticed that Joe has a book out titled "Joe Celko's Trees and
>   Hierarchies in SQL for Smarties".  I have not yet had a chance to
>   review this book (other than the on-line table of contents) but it
>   looks interesting.  While much of this is on graphs and more general
>   edge/node structures, a fair bit of the book appears to be about this
>   type of tree structure.  He goes into more detail on some of these
>   issues, such as insertion and deletion times, and tricks to play for
>   inserting whole sub-trees, and that kind of thing.  Maybe the book
>   would sell the so-called "nested-set" implementation a bit better,
>   but it still strikes me as a solution for warehouses, not OLTP style
>   stuff.  I might have to find this book and have a closer read.

I'd be curious to know if that book is just an out-take of SQL For
Smarties, or if he adds new information. I can tell you that Smarties is
a book every serious database architect should have.
--
Jim Nasby                                            jim@nasby.net
EnterpriseDB      http://enterprisedb.com      512.569.9461 (cell)