Oracle FAQ Your Portal to the Oracle Knowledge Grid
HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US
 

Home -> Community -> Usenet -> comp.databases.theory -> Re: query that Bob is descendant of Alice

Re: query that Bob is descendant of Alice

From: Robert Vazan <robova_at_nextra.sk>
Date: Mon, 23 Apr 2001 22:56:48 GMT
Message-ID: <3ae4affc.9811851@news.nextra.sk>

Chris F Clark <cfc_at_world.std.com> wrote:
>Unfortunately, most call trees are not-acyclic, recursion and indirect
>recursion are both common in many programs (and allowed in almost all
>programming languages that allow calls).

When depth of cyclic links doesn't matter, then they behave like equivalence (cycles form sort of autonomous objects). Now, we can divide graph into acyclic part and union of cyclic parts. And then maybe replace cycles with some more effective form of equivalence.

>If I were attacking this problem under the constraints you have, I
>might attempt something like incrementally forming the transitive
>closure. When ever asked for the decendent of Alice, form the closure
>with Alice as a root, marking each vertex (function name) that is
>closed in the process. Then you can avoid recomputing the closure on
>those nodes, if they are later queried.

OK, OK, I agree with you all, that transitive closure is good enough in 75-percent situations. If we have graph with <10,000 nodes or shallow graph with <1,000,000 nodes then transitive closure fits into disk. Deep narrow graph can be rounded to total ordering. But if I don't want it rounded or I have graph which is both deep and wide. Or if I want many queries per minute. Or if my graph only so-so fits into disk (and closure doesn't). Then what?

<snip>
>Note, I would be surprised to find that an "incremental" or "online"
>transitive closure algorithm was not at least a partially solved
>problem.

It surely is. Partially, however.

> [...] I would keep asking, someone must know of a paper that
>addresses exactly that problem.

Exactly. It seems to be too common problem to not be solved or worked around. Maybe everybody has only trees and shallow graphs, but that's hard to believe.

/Robert Received on Mon Apr 23 2001 - 17:56:48 CDT

Original text of this message

HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US