Re: transitive closure

From: Marshall Spight <marshall.spight_at_gmail.com>
Date: 18 Jul 2005 07:58:37 -0700
Message-ID: <1121698717.883563.221800@g44g2000cwa.googlegroups.com>

-CELKO- wrote:
> Have you seen a copy of TREES & HIERARCHIES? There are serealk ways of
> modeling trees to get a transitive closure in one statement. General
> graphs can be done with recursive CTEs.

Yeah, after you mentioned it in a previous thread, it occurred to me in a "duh" moment that if trees are what I'm thinking about right now, I ought to read it.

I have played a little with what I believe you call the adjacency list model, and the materialized path model. I found materialized path to be quite speedy for my purposes, even if I didn't find it particularly aesthetically pleasing.

While I was doing that work I noticed that in ordinary application code, one can tranverse a tree in O(n) time/O(logn) space, and reparent a tree in O(1) time. I would like to believe there's an approach in the RM (not necessarily in SQL) that would work with the same time/space performance.

Marshall Received on Mon Jul 18 2005 - 09:58:37 CDT