Re: Other tree representations in SQL

From: --CELKO-- <71062.1056_at_compuserve.com>
Date: 7 Dec 2002 20:37:41 -0800
Message-ID: <c0d87ec0.0212072037.1a5bfd0b_at_posting.google.com>


>> Oooops, I guess I must have mistaken you for this man:
 http://www.byte.com/art/9710/sec6/art6.htm <<

That's an article, not a book. And I did it with my wife.

>> (1) Object database vendors should work on supporting SQL, to allow
their products to be run with common reporting tools. <<

We did some of that with the SQL3 and OQL specs, but frankly I am not really happy about the results. I also like the idea of a standard SQL interface to legacy systems.

>> (2) All object databases products with noticeable market share
between 1980 and 2000 ... are still not ready for prime-time today. <<

I think it is not the technology, but the commercial data model, which is still "record oriented" rather than "Object Oriented" ; separation of data from procedures is a rather powerful concept.

>> (3) Object queries are not difficult. <<

I keep saying that about SQL ...

>> I think this statement is too generalised. Fly doing what? How much
work is it, to get the system to fly nice loopings? <<

Any routine, batch process on large amounts of data will be fastger in IMS. Things like doing the payroll for a Fortune 500 company. The trade off is that it is not flexible -- "The animal best adapted to one environment is a failure in all other environments."

>> Come on, I guess you do know at least one object-oriented language
like C++ ? <<

Nope. I started with FORTRAN and Algol, then stopped with 'C' and Pascal. When I got to be the "Great SQL Guru", I never worked with any procedural or OO languages after that. Sad, but true.

>> At least I would hope so, if you write articles on object
databases? (Your 1997 article is an excellent read anyway.) <<

That was the only one and my wife did the edits and most of the research.

>> As you have shown, it's difficult to traverse trees in SQL. If you
need to do that, you would usually load a complete representation of the tree into another language. <<

Actually, in the nested set model, I would write:

 SELECT T2.node, (rgt-lft) AS height
   FROM Tree AS T1, Tree AS T2
  WHERE T1.lft BETWEEN T2.rgt AND T2.lft     AND T1.node = :my_node;

The spread of (lft, rgt) values gets greater as you go up the path from the node to the root of the tree, so I can order my traversal in the host program.

>> Balancing takes place by comparing the number of subnodes of every
branch. This has proved to construct trees, balanced "well enough" and overall performance empirically turned out to be just as good as with red-black-trees and nearly as good as with AVL trees. <<

Okay, we are still talking about binary trees in this algorithm.

I have to play with this, but a wild first guess would be to put the binary tree into a table as a heap, then re-order the heap numbers with a single UPDATE statement. An ugly, slow running UPDATE statement. Received on Sun Dec 08 2002 - 05:37:41 CET

Original text of this message