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

"Chris Colclough" <chris.colclough_at_nospam.jhuapl.edu> wrote in message news:f9fqvo$774$2_at_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
>

btw -

  I'm working in 10g, not 8i, so the query aliasing would have to be handled differently. Alternatively, move from 8i to 10g ;-> Received on Fri Aug 10 2007 - 06:48:39 CDT