Re: Nested sets in SQL - inventor?

Mikito Harakiri wrote:
> Appeo Allkam wrote:
> > http://www.dbpd.com/vault/9811/kamfn.shtml
>
> I don't quite understand the following passage in Kamfonas article

<quote>
The "prestored transitive closure" approach involves an intermediate table that contains X's descendents, and a join to the org table. The intermediate table is either temporary, generated every time you issue a query, or permanent, containing the transitive closure of the "reports to" relationship.

There are disadvantages to each of these solutions. The first actually "walks the structure," requiring multiple requests that let you extract children sets for each node you retrieve. The advantage of this approach is that it doesn't introduce any update anomalies because you don't maintain redundant data. The second solution uses set processing, but it requires that you maintain a very large redundant table and deal with the associated update anomalies. For example, a tree five layers deep with a fan-out of 10 children per node has a total of 11,111 nodes and 11,110 parent-child relationships. But there are more than 11,000,000 ancestor-descendent relationships in the transitive closure. A single maintenance operation may affect more than one million of these ancestor-descendent relationships. The cost of this approach grows geometrically as the fanout and depth grow. This option is undesirable only because of maintenance complications and the lack of scalability.>
</quote>

Where this 11,000,000 number came from? Each of 11,111 nodes has no more than 5 ancestors so that the size of transitive closure is certainly less than 5*11,111.

Just for the record, the size of Materialized path/Nested Intervals.Nested Sets encoding is about the same. It is true, there are only 11,111 records, but each encoding grows in size with the number of nodes in the tree increasing.

I guess I'll stop reading, unless convinced that there is a single not entirelly wrong idea in this article. Received on Wed Jul 27 2005 - 21:09:32 CEST