Oracle FAQ Your Portal to the Oracle Knowledge Grid
HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US
 

Home -> Community -> Usenet -> c.d.o.server -> Re: Can this be done in SQL? Find the transitive relation

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:57:11 -0400
Message-ID: <f9frio$7lq$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 is not *exacly* the solution being sought, but it may be of some value.

Note the use of the trim function. Somewhere along the line, spaces where being appended to either the id1 or id2 values, resulting in a "connect by" statement that would not work. This could be a bug or user error, I haven't taken the time to investigate.

First, map the transitive data so that the data may be expressed as a parent-child hierarchy.

create or replace view mapper as
with
right_missing_link as -- tuples where both id1 and id2 exist as transitive values in the id2 column of other 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 id1 column of other 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) -- all other tuples 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 that the transitive data exists in a hierarchical structure, extract it using the following query:

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 allows the data to be grouped for further processing.

hth Received on Thu Aug 09 2007 - 14:57:11 CDT

Original text of this message

HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US