Re: Other tree representations in SQL

"Greg Boland" <gregb_at_snet.net> wrote in message news:JPcI9.2772$Lq5.692739130_at_newssvr10.news.prodigy.com...
>
> "--CELKO--" <71062.1056_at_compuserve.com> wrote in message
> news:c0d87ec0.0212051125.526945fd_at_posting.google.com...
> > >> The tree model, no matter how you do it, is contrived under the sql
> > model. <<
> >
> > I find the nested sets model to be quite natural because I am a
> > programmer. I write algebra with parentheses, code with BEGIN-END
> > block, use HTML, XML, etc. All of which are nested structures. I now
> > find the adjacency list model -- "boxes and arrows" -- to be a little
> > harder to use.
> >
> > >>I do an app in which I need to know parents and siblings. Quite
> > simple. I found it much more natural to store children with a parent.
> > <<
> >
> > Yes, if that is all you do. But you still need constriants to assure
> > that nobody is his own great-grandfather, etc. -- that it is a tree.
> >
> > >> But to traverse the tree you still have to do some procedural
> > programming which sql is not up to the task. <<
> >
> > To me, a traversal sounds like it has to be procedural and SQL is a
> > non-procedural language. I want to get the SET of ancestors in one
> > operation, not the SEQUENCE of ancestors in a series of operations.
> >
> > >> The hierarchal model that Celko describes is much better up to the
> > task, but I wouldn't use it. <<
> >
> > The nested set model (and those similar model to it) are great for a
> > reporting hierarchy ("Give me expenses for the company, by department,
> > by sections within departments, by teams within sections!").
> >
> > The adjacency list is very fast for insertions - just put the (node,
> > parfent,child) tuple in the table, check the constraints and you are
> > done!
> >
> > However, there is no rule that says you cannot have a hybrid table.
> > And I have a section in my manuscript on that topic.
> >
> > CREATE TABLE HybirdTree
> > (node_id INTEGER NOT NULL
> > REFERENCES ...
> > lft INTEGER NOT NULL DEFAULT 0,
> > rgt INTEGER NOT NULL DEFAULT 0,
> > parent_node_id INTEGER NOT NULL
> > REFERENCES ...
> > CHECK(..), -- lots of work here!!
> > ...);
> >
> > The (0,0) for (lft,rgt) means I did not bother to compute their values
> > yet. Just before I need a report, I can run a stored proc (classic
> > stack or recursive algorithm for preorder traversal) and fill in the
> > real values, sorting the siblings.
>
> I liked the tone of your reply. I do indeed like your hierarchal model.
But
> you stated you are a programmer. So for your example, I would do a simple
> SELECT, and break the result set out. But not in SQL. And I would do
lft,rgt
> as a balanced b-tree, even though it's a little harder. Or did I miss
> something?
>
> Regards,
>
> Greg
>
After thinking about this, I would forget about balanced-btrees.

Too much wine, not enough time,

Greg Received on Sat Dec 07 2002 - 03:26:28 CET