SQL query to resolve transitive dependencies in database

Question

Suppose I have a table with 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 |

What it means is that R1 is related to R2 , bi-directionally. So if there is an entry in database for 1,3 there won't be an entry like 3,1.

According to above data: 1 is related to 2,4,3 directly. And 4 is related to 1 also . So via transitive dependency, 1 and 5 are also considered as related.

Expected result:

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

Can anyone write a SQL query for this?

What is the version of Oracle? – Nick Krasnov Nov 25 '12 at 08:38 — Nick Krasnov, Nov 25 '12 at 08:38
Oracle 11g , but database is not a primary constraint. – Priyank Doshi Nov 25 '12 at 08:39 — Priyank Doshi, Nov 25 '12 at 08:39

score 3 · Answer 1 · answered Nov 25 '12 at 08:46

3

As you are running Oracle 11g (and If it happens to be Release 2), as one of the methods, you can use recursive common table expression (also known as recursive sub-query factoring) to get desired result.

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

answered Nov 25 '12 at 08:46

Nick Krasnov

26,886
6
61
78

Thanks for help. I tried on sqlfiddle , it works perfactly. But, Is there a easy way ? I am not a DB expert and this terms are quite harder to understand for me. – Priyank Doshi Nov 25 '12 at 10:15
This is **the** answer. Otherwise, choose a programming language and do the recursion on its side :) – Raffaele Nov 25 '12 at 11:35
1

@Raffaele: it can be written in a more compact way using `connect by`: http://sqlfiddle.com/#!4/842b8/1 but it is essentially the same solution. – Nov 25 '12 at 11:59
@a_horse_with_no_name nice one! – Raffaele Nov 25 '12 at 15:46

score 0 · Answer 2 · answered Nov 25 '12 at 11:31

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

It works by expanding the table into a monodirectional one, and then combining that 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

SQL query to resolve transitive dependencies in database

2 Answers2

Linked