Re: A new approach to storing ordered hierarchical data in RDBs.

From: Bob Badour <>
Date: Wed, 22 Nov 2006 16:40:21 GMT
Message-ID: <V3%8h.23524$>

goran wrote:

> I guess a better title for my post would have been »I've rediscovered
> the wheel«. I'm curious as to why 90% of articles I've read on the
> subject only consider adjacency list, materialized path and nested sets
> as a viable solution to storing hierarchical data in RDBs? I think
> maintaining transitive closure tables to be as complex (or less
> complex) than maintaining materialized paths while avoiding the
> limitation of the size of an indexed field.
> The "new" idea I had was to actually use a helper (width) table to
> store the information on the size of each branch of the tree. For my
> case it was important to preserve not only the hierarchical relations
> between nodes but also their relative order. TC table alone cannot tell
> me if Marie is the first or the last child node of Allen.
> Using this approach I get a model that is far less volatile then nested
> sets. I have a much faster read then using adjacency list (using CTE or
> temp stack tables). The way I'm storing and retrieving global order
> enables me to avoid the volatility of using global order information or
> the limitation of a fixed mapping scheme (as in nested intervals
> model).
> If this approach has been used before, I would appreciate a link or two
> as I don't wish to rediscover things I can educate myself on by
> reading. Anyways - sorry for causing such turbulence.
> Goran

We all rediscover wheels from time to time, and there is no harm in that. Sometimes there is great benefit in it.

Even if your representation of the hierarchy has no other useful properties, there is still value in sharing it. It might inspire someone else to come up with something useful.

If I recall correctly, Chris Date once observed that someone published a paper in the 1970's remarking on some cool properties of certain relations that inspired Ron Fagin to prove the necessity and sufficiency of 5NF. As I understand it, Dr. Codd remarked on those same properties in his seminal work.

If someone had not reinvented that wheel, we might never have had Fagin's proofs.

Materialized path already maintains a strict order. However, I don't see why hierarchies should have just a single order. One of the advantages of relations is the ability to order by any combination of derivable values.

Does your representation of the hierarchy have any other useful properties? In particular, could it yield any physical optimizations? Certain inserts will require renumbering large amounts of the tree, so one would want some significant benefit to pay for that cost.

> vc wrote:

>>The TC appoach to SQL queries has been rather well known since 1970s
>>but alas TC maintenance is costly.
>>More interestingly,  why bother ?  SQL server implements the SQL-99
Received on Wed Nov 22 2006 - 17:40:21 CET

Original text of this message