Re: CONNECT BY / START WITH query to count "families"

Vadim Tropashko wrote:

> trippknightly_at_hotmail.com wrote:

With the hint by Leonid Libkin:

<quote>Your equivalence relation is simply reachability (transitive closure) - you make the graph undirected to make this an equivalence relation. Once you have an equivalence relation you can define the set

{s | every element s' equivalent to s is greater than s in the ordering}

This is is clearly first order (rel. calc) and gives you unique representatives of equivalence classes.</quote>

The solution is reduced to the following:

create table input as (
select 1 x, 2 y from dual
union
select 2, 3 from dual
union
select 2, 4 from dual
union
select 6, 7 from dual
union
select 8, 9 from dual);

with STC as ( -- Symmetric transitive closure

   select connect_by_root(x) x, y from (     select x,y from input
    union
    select y,x from input
   ) connect by nocycle x = prior y
) select distinct x from STC s
where not exists (

   select * from STC ss where ss.y<s.x and s.x=ss.x );

X
---
 1
 6
 8 Received on Tue Oct 04 2005 - 11:31:11 CDT