Re: parent/child relationship in the same table.

In article <sHbK7.30462$xS6.49680_at_www.newsranger.com>, "D" <D_at_b.a> wrote:

>>> 3. Incremental evaluation of transitive closure.
>>
>>It certainly is a hierarchy problem so probably is a FAQ.
>
> Every 3 mo or so a question on hierarchy surfaces in this group, but
> AFAIK there is no FAQ:-(
>

I'm thinking of putting together an FAQ. Somebody encourage me! I would need to get contributions from some of the regular posters on this topic.  It would follow the outline above, with a few more subdivisions.

>>I'm using SQL Server so solutions 1 and 2 are automatically ruled out.
>>Do you have any pointers on number 3?
>
> Here is incomplete classification:
> 1. Incremental evaluation systems for general graphs. The idea behind is
> that whenever you add a link <a,b> into a path like this:
>
> x---->a b---->y
>
> you also need to add links <x,b>, <a,y>, <x,y> into the adjucency
> relation. Obxiously this must be done for every couple (x,y) of nodes in
> the graph. Almost any paper on incremental evaluation mentiones that
> method -- just pull out Google.

Just to focus on this problem, the poster wants an easy way to order the results. Transitive closure doesn't do much in that department, although it does make it easier to do just about everything else. An alternative is incremental maintenance of the path to each node, and sorting by that field to get the order desired. It's not much different from maintaining the transitive closure.

Regards,

Kendall Received on Tue Nov 20 2001 - 07:16:09 CET