Re: query that Bob is descendant of Alice

... my reply CCied to David ...

David Wagner wrote:
> I don't understand. What's the matter with depth-first search?
> If SQL can't support depth-first search, then maybe it's not the
> best way to store the callgraph. After all, 30MB is not that large...

I have many (to O(n)) pairs of nice_guy()->bad_guy(). If depth-first for one is O(n) then all pairs go in O(n)xO(n)=O(n^2). In other words I have two tables: call graph & table of pairs. Calculation time has size of multiplication of both tables and this is no good if both tables are big.

I guess there is (in most cases) some way to reduce even group operations to O(n), but I cannot imagine any general way (call trees are just example, there are more complicated things around) to do this, nor I know about any software, that does this.

I can always ignore such problems, but if I could do this, it would give me a lot of power. Good partial solution maybe good also. Thanks in advance.

/Robert Received on Sun Apr 22 2001 - 08:01:40 CEST