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: Chris F Clark <cfc_at_world.std.com>
Date: Mon, 23 Apr 2001 11:37:23 GMT
Message-ID: <sddoftnkft8.fsf@world.std.com>

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).

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.

You might get more clever and attempt to use Trajan's union-find algorithmic trick to get better amortorized cost, but I'd only do that if the brute force version was still too slow. If that's still too slow, you might try aborting the depth first search whenever a positive result was encountered. However, to memoize that, you'll probably need to somehow keep some representation of where the search has reached for each node and not just a single bit for closure taken or not. Hmmm, but it might be possible to amortorize that information so that it is stored through-out the graph.

Note, I would be surprised to find that an "incremental" or "online" transitive closure algorithm was not at least a partially solved problem. I would keep asking, someone must know of a paper that addresses exactly that problem.

Finally, unless you need external storage (e.g. saving the tree between runs), I would avoid databases. The size of data you are talking about should fit in memory (ram) for most implementations of most programming languages, and you are more likely to find a copy of the algorithm you are looking for in a language like C or Lisp than in SQL. If you had 30GB of code, I *might* think differently.

Hope this helps,
-Chris


Chris Clark                    Internet   :  compres_at_world.std.com
Compiler Resources, Inc.       Web Site   :  http://world.std.com/~compres  
3 Proctor Street               voice      :  (508) 435-5016
Hopkinton, MA  01748  USA      fax        :  (508) 435-4847  (24 hours)

------------------------------------------------------------------------------
Received on Mon Apr 23 2001 - 06:37:23 CDT

Original text of this message

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