Performance problem in a "Connect-By" query over a DAG-edges table

We're using an "Edges" table with records consisting of two fields: ParentID ChildID (actually, the table has some more columns, which are not important to the problem).

This table describes a DAG-type graph, with each record being an edge between two vertices with IDs given in these two fields. Each vertex may have many parents and many childs.

We want to get all the ancestors of a given vertex, using the following
query:
select ParentID from Edges
start with ChildID = #####
connect by prior ParentID = ChildID.

When the table size is about 1000 records, this query doesn't stop. We know, that we don't have cycles in the our described graph. We think that the problem comes from the fact that, since the graph is a DAG, there are many ways to get to a certain ancestor of our vertex with the amount of ways increasing exponentially. We followed the execution of the query, by examining the output of ParentIDs and indeed, it seems that the query got to the same record many times.

Is there a way to avoid this, or maybe there's a better way to get all the ancestors of our vertex.

Thanks,
Oren. Received on Mon May 12 2003 - 02:34:30 CDT