Oracle FAQ Your Portal to the Oracle Knowledge Grid

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

Re: query that Bob is descendant of Alice

From: Mats Kindahl <>
Date: 25 Apr 2001 10:13:11 +0200
Message-ID: <> (Robert Vazan) writes:

> Mats Kindahl <> wrote:
> >The call tree you have form a DAG, but I believe the following can be
> >easily applied to DAGs and to "forests" as well [...]
> And there is the trick. In DAGs, you have multiple LCAs.
> Besides getting uncertain, algorithm would IMHO need
> modifications for DAGs, so I would need look in detail on
> that algo.

Yeah, that's correct.  

> <snipped adaptation of LCA to is_descendant question>
> >[2] D. Harel and R. E. Tarjan.
> > Fast algorithms for finding nearest common ancestors.
> > SIAM J. Comput., 13:338-355, 1984.
> >
> >[3] B. Schieber and U. Vishkin.
> > On finding lowest common ancestors: simplification and
> > parallelization. SIAM J. Comput., 17(6):1253-1262,
> > December 1988.
> It is sad, but for me, if it is not online, it doesn't
> exist. Is there a web site with LCA or author's homepage?
> Could you describe key steps of LCA? It's hard to guess.

I tried to find it on the net as well, but only found references to the papers. I have a book ("Algorithms on Strings, Trees, and Sequences" by Dan Gusfield) where the algorithm is described in detail, proofs and all, but that is too much for me to copy manually (the algorithms in the book are generally given in english and not using any form of pseudo-code).

I belive that SIAM have some kind of on-line service where you, for a fee, can get access to their articles. I don't know if that is an option for you.

I'm short of time right now, but next week or the week after that I might have time to condense the information to something more managable, e.g., some piece of code.

Best wishes,

Mats Kindahl, IAR Systems, Sweden

Any opinions expressed are my own, not my company's.
Received on Wed Apr 25 2001 - 03:13:11 CDT

Original text of this message