Re: Can this be done in SQL? Find the transitive relation

From: Chris Colclough <chris.colclough_at_nospam.jhuapl.edu>
Date: Thu, 9 Aug 2007 15:47:03 -0400
Message-ID: <f9fqvo$774$2@aplnetnews.jhuapl.edu>

"da. Ram" <dba2adm_at_yahoo.com> wrote in message news:1186254415.754555.284800_at_e16g2000pri.googlegroups.com...
> Dear Group,
>
> I am strugling get the following done in SQL. Could anyone help me to
> figure out a way?
>
> Oracle version 8i .
>
> create table t_grp (id1 char(1), id2 char(2)) ;
>
> insert into t_grp values ('A','C'); --> A:C are related
> insert into t_grp values ('B','D'); --> B:D are related
> insert into t_grp values ('F','H');
> insert into t_grp values ('G','H');
> insert into t_grp values ('B','G');
> insert into t_grp values ('X','Y');
> insert into t_grp values ('W','Y');
>
> I want to group the values based on the following rules,
>
> 1, if any of the value from id1 or id2 can be linked to any other
> values,
> they all will be treated as one group
>
> Ex, in the above case
> A has relationship to C, neither of them has any other relationship to
> any
> other values in the table
> B has relationship to D, B has relationship to G, G has relationship
> to H, H
> has relationship to F
> F has relationship to H, H has relationship to G ...
>
> A:C - Group 1 (A,C) - new elements
> B:D -> B:G -> G:H -> H:F - Group 2 (B, D, G, H, F)
> F:H -> H:G -> G:B -> B:D - Group 2 (F, H, G, B, D) - same elements as
> above
> G:H -> G:B -> H:F -> B:D - Group 2 (G, H, B, F, D) - do -
> G:B -> G:H -> H:F -> B:D - Group 2 (G, B, H, F, D) - do -
> X:Y -> Y:W - Group 3 (X, Y, W) - new set of elements
>
> My objective is to get the final result in the below form.
>
> grp id1 id2
> ----- ------ ------
> 1 A C
> 2 B D
> 2 F H
> 2 G H
> 2 B G
> 3 X Y
> 3 W Y
>
> The following output is also fine [This would be the final output, but
> I can covert from the above to this one]
>
> grp id
> ---- -------
> 1 A
> 1 C
> 2 B
> 2 D
> 2 F
> 2 H
> 2 G
> ...
> 3 X
> 3 Y
> 3 W
> 3 Y
>
> Thank you.
>

This solution does not yield *exactly* what's being requested, but it may be of some value. The trim function is used because spaces where being appended to the id1 and id2 columns. It may be a bug or a user error :-)

First, create a view of the data which allows the transitive relations to be viewed in a hierarchical manner:

create or replace view mapper as
with
right_missing_link as -- tuples where both id1 and id2 exist as transitive values in the right hand column of other t_grp tuples (
select rowid, id1, id2
from t_grp t1
where t1.id1 in
(select id2
from t_grp t2
where t1.id1 = t2.id2)
and t1.id2 in
(select id2
from t_grp t3
where t1.id2 = t3.id2)
),
left_missing_link as -- tuples where both id1 and id2 exist as transitive values in the left hand column of other t_grp tuples (
select rowid, id1, id2
from t_grp t1
where t1.id1 in
(select id1
from t_grp t2
where t1.id1 = t2.id1)
and t1.id2 in
(select id1
from t_grp t3
where t1.id2 = t3.id1)
),
right_multi_map as -- tuples where id1 maps to multiple id2 values in t_grp (
select rowid, id1, id2
from t_grp t1
where id1 =
(select id1
from t_grp t2
where t2.id1 = t1.id1
group by id1
having count(*) > 1)
),
left_multi_map as -- tuples where id2 maps to multiple id1 values in t_grp (
select rowid, id2, id1
from t_grp t3
where id2 =
(select id2
from t_grp t4
where t4.id2 = t3.id2
group by id2
having count(*) > 1)
)
select trim(id1) as id1, trim(id2) as id2 from right_missing_link union
select trim(id1), trim(id2) from left_missing_link union
select trim(id1), trim(id2) from right_multi_map WHERE ROWID NOT IN
(SELECT ROWID FROM RIGHT_MISSING_LINK
UNION
SELECT ROWID FROM LEFT_MISSING_LINK)
union
select trim(ID2), trim(ID1) from left_multi_map WHERE ROWID NOT IN
(SELECT ROWID FROM RIGHT_MISSING_LINK
UNION
SELECT ROWID FROM LEFT_MISSING_LINK)
UNION
select trim(id1), trim(id2) -- any other tuple not yet mapped from t_grp
where rowid not in
(select rowid from left_missing_link union select rowid from right_missing_link union select rowid from left_multi_map union
select rowid from right_multi_map)
Now, extract the data

with fred as
(
select lpad(' ', 2*level) || id1 as indented, id1, id2, level

, sys_connect_by_path(id1, ':')||':'||id2 as entire_path
, connect_by_isleaf as isleaf
,connect_by_root id1 as current_tuple_root

from mapper
connect by prior id2 = id1
)
select *
from fred
where current_tuple_root not in
(select id2
from fred)

Results follow:

INDENTED ID1 ID2 LEVEL ENTIRE_PATH ISLEAF CURRENT_TUPLE_ROOT

---------- --- --- ---------- -------------------- ---------- ------------------
  A        A   C            1 :A:C                          1 A
  B        B   D            1 :B:D                          1 B
  B        B   G            1 :B:G                          0 B
    G      G   H            2 :B:G:H                        0 B
      H    H   F            3 :B:G:H:F                      1 B
  Y        Y   W            1 :Y:W                          1 Y
  Y        Y   X            1 :Y:X                          1 Y

The current_tuple_root column allows the data to be broken into distinct groups for further processing. Again, not exactly what was requested, but it may be of value.

hth Received on Thu Aug 09 2007 - 14:47:03 CDT