Re: Other tree representations in SQL

>> 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. Received on Thu Dec 05 2002 - 20:25:07 CET