SQL query to resolve transitive dependencies in a database

Question

SQLFIddle reference for this data.

Suppose I have a table with the following structure:

create table rd(r1 number,r2 number, primary key (r1,r2)); 

Sample data:

 | R1 | R2 | ----------- | 1 | 2 | | 1 | 4 | | 2 | 3 | | 3 | 1 | | 4 | 5 | 

This means that R1 is connected to R2, bidirectionally. Therefore, if there is an entry for 1.3 in the database, there will be no such entry as 3.1.

According to the above data: 1 is directly related to 2,4,3. And 4 also refers to 1. Thus, through the transitive dependence, 1 and 5 are also considered as related.

Expected Result:

 | R1 | R2 | ----------- | 1 | 2 | | 1 | 4 | | 1 | 3 | | 1 | 5 | 

Can someone write an SQL query for this?

Answer 1

When you use Oracle 11g (and if Release 2 happens), you can use a recursive generic table expression (also known as factoring a recursive subquery) as one of the methods to get the result you want .

 SQL> with rcte(r1, r2, lv, root) as( 2 select r1 3 , r2 4 , 0 lv 5 , r1 6 from rd 7 where r1 = 1 8 9 union all 10 11 select t.r1 12 , t.r2 13 , lv + 1 14 , q.root 15 from rd t 16 join rcte q 17 on (t.r1 = q.r2) 18 ) 19 search depth first by r1 set s 20 cycle r1 set is_cycle to 'y' default 'n' 21 22 select root 23 , r2 24 from rcte 25 where is_cycle = 'n' 26 and r2 <> root 27 ; ROOT R2 ---------- ---------- 1 2 1 3 1 4 1 5 

Answer 2

The following query will work until there is only one level of intermediate values ​​in the table.

It works by expanding the table into unidirectional, and then combining this table with the results of joining it to itself.

 WITH expanded AS (SELECT r1, r2 FROM rd UNION ALL SELECT r2 AS r1, r1 AS r2 FROM rd) SELECT * FROM (SELECT r1, r2 FROM expanded -- direct relations UNION SELECT e1.r1 AS r1, e2.r2 AS r2 -- indirect relations FROM expanded e1 INNER JOIN expanded e2 ON e1.r2 = e2.r1 -- via transitive dependency AND e2.r2 <> e1.r1) WHERE r1 = 1 ORDER BY r1, r2