Skip to Main Content
  • Questions
  • cycle detected in recursive query where it seems to be no cycle

Breadcrumb

Question and Answer

Chris Saxon

Thanks for the question, Tomáš.

Asked: September 16, 2020 - 12:29 pm UTC

Answered by: Chris Saxon - Last updated: September 16, 2020 - 1:47 pm UTC

Category: SQL - Version: Oracle 11

Viewed 100+ times

You Asked

I have recursive query on Oracle 11g table with undirected graph data. Each row represents one edge. The recursive query traverses all edges starting from given input edge. The idea of query is:

- input edge is at the 0th level
- for n>0, edge is on n-th level if it incides with node of some edge on (n-1)-th level.

Query:

with edges (id, a, b) as (
  select 1, 'X', 'Y' from dual union
  select 2, 'X', 'Y' from dual
), r (l, id, parent_a, parent_b, child_a, child_b, edge_seen) as (
  select 0, id, null, null, a, b, cast(collect(id) over () as sys.ku$_objnumset)
  from edges
  where id = 1 
  union all
  select r.l + 1, e.id, r.child_a, r.child_b, e.a, e.b
       , r.edge_seen multiset union distinct (cast(collect(e.id) over () as sys.ku$_objnumset))
  from r
  join edges e on (r.child_a in (e.a, e.b) or r.child_b in (e.a, e.b))
    and e.id not member of (select r.edge_seen from dual)
)
select * from r;


The query worked well with other inputs until two parallel edges between same node pair occured. In this case, there is edge 1 on 0th level of recursion (initial row). I expected edge 2 would be added to result on 1st level of recursion since join condition holds. Instead I get "ORA-32044: cycle detected while executing recursive with query".

I know this error is reported when the row newly joined to recursive query result would be same as some existing row. What I don't understand is why Oracle treats row with same node ids but different edge id as duplicate. Adding

cycle child_a, child_b set iscycle to 1 default 0


clause gives iscycle=1 for new row, adding

cycle id, child_a, child_b set iscycle to 1 default 0


gives iscycle=0, which is both correct.


Is it some known Oracle 11g bug and what's the best way to handle it?

I cannot fill LiveSQL link form since LiveSQL supports only Oracle 19 and the problem is reproducible only in Oracle 11g which I can't migrate from. The dbfiddle equivalent is https://dbfiddle.uk/?rdbms=oracle_11.2&fiddle=43af3cfae920e31f9a2748c1c31b54ad .

Thanks.

and we said...

From the docs:

A row is considered to form a cycle if one of its ancestor rows has the same values for the cycle columns.

i.e. the database doesn't consider the whole row, only the values of the columns you use in the cycle clause.

So when you have only:

cycle child_a, child_b


The database does consider this a cycle because edge 2 has exactly the same A, B values as edge 1, which is its ancestor.

By adding edge_seen and the multiset union nonsense, what you've done is implement your own cycle clause!

You could remove this and cycle on ID alone:

with edges (id, a, b) as (
  select 1, 'X', 'Y' from dual union
  select 2, 'X', 'Y' from dual
), r (l, id, parent_a, parent_b, child_a, child_b) as (
  select 0, id, null, null, a, b
  from edges
  where id = 1 
  union all
  select r.l + 1, e.id, r.child_a, r.child_b, e.a, e.b
  from r
  join edges e on (r.child_a in (e.a, e.b) or r.child_b in (e.a, e.b))
) 
  cycle id set iscycle to 1 default 0
select * from r
where  iscycle = 0;

L    ID    PARENT_A    PARENT_B    CHILD_A    CHILD_B    ISCYCLE   
   0     1 <null>      <null>      X          Y          0          
   1     2 X           Y           X          Y          0    

More to Explore

SQL

The Oracle documentation contains a complete SQL reference.