Re: Other tree representations in SQL

>> Excuse me for jumping on the train, Joe. m<<

That's what newsgroups are for ..

>> Since hardly anyone here seems to understand that there are usecases where object databases work better than relational databases, I would like to provide some sample code, to prove it. <<

Two things:

1. I only write SQL books. A dirty job, but someone has to do it <g> ...
2. IMS will fly thru huge amounts of heirarchical data faster than either SQL or an OODBMS.

>> Since the code is straight-forward OO without the need for rocket science SQL, it took me just a little more than an hour to write. It contains all the tasks outlined in your posting and the class model directly defines the scheme to be used by the database engine. <<

I don't know Java, so I am at a bit of a loss to evaluate the code. I did look up some old Pascal binary tree traversals and that code was quite clear even after all these years.

>> I challenge any relational system for a performance race on any kind of tree search or tree traversal. <<

In SQL, the tree structures are not used for searching or traditional traversals. The nodes have a key, and if you want to find a node, you just do a "SELECT .. FROM Tree WHERE node_key = :my_guy;". We don't ask for the path (i.e. traditional ordered traversal), we ask for the set of descendents or ancestors of a node.

The major function of the tree is aggregation for reports -- "give me expenses for the company as a whole, broken down by departments, broken down by teams within departments." I have not seen anyone really use a pure binary tree in SQL; they are almost all multi-way trees.

>> The attached code uses S.O.D.A. for querying. <<

Did you count all of that code as part of the solution?

>> ... SQL trees: I wonder how you would balance them? <<

I honestly don't know. In fact, the best way I found to sort a tree in the nested zsets model was to convert it to the adjacency list model, and then use that working table to build a new nested sets model with a cursor.

I can swap sibling subtrees, but that much updating and committing of work was more than a brute force approach.

My guess would be to find the middle value (any median query would do it) in the table and make him the root of the new tree. Then apply the same algorithm to the left and right subtree sets. For example:

(1, NULL, NULL)
(2, NULL, NULL)
(3, NULL, NULL)
(4, NULL, NULL)
(5, NULL, NULL)
(6, NULL, NULL)
(7, NULL, NULL)
becomes:

(1, NULL, NULL)
(2, NULL, NULL)
(3, NULL, NULL)
(4, 1, 14) -- root has known (lft,rgt) values
(5, NULL, NULL)
(6, NULL, NULL)
(7, NULL, NULL)
becomes:

(1, NULL, NULL)
(2, 2, 7) --leftmost child has (lft=2, rgt = 2*size of subtree +1)
(3, NULL, NULL)
(4, 1, 14)
(5, NULL, NULL)
(6, NULL, NULL)
(7, NULL, NULL)
becomes:

(1, 3, 4)
(2, 2, 7)
(3, 5, 8)
(4, 1, 14)
(5, NULL, NULL)
(6, NULL, NULL)
(7, NULL, NULL)
It would be a bit of algebra to get the numbers right.

>> With an object database the task is dead simple:

• load the tree into memory from the root
• balance the tree
• store the root <<

Come on, you know that is not an answer! Remember the famous cartoon of two sciencists in front of a blackboard and in the middle of the equation there is a block of text that reads "then a miracle occurs"? The caption is "You need to be more explicit about step #2." Received on Wed Dec 04 2002 - 23:41:09 CET