CODEWITHSUNDEEP
sqlsql-server
reykjavi
reykjavi

Reputation: 43

Find all possible pairs based on transitivity via T-SQL

I have a concern that doesn't let me go for already several days. The collective mind is the last resort I may rely on.

Assume we have a table with two columns. Actually, the values are GUIDs, but for the sake of simplicity let's take them as letters.

| a | b |
|---|---|
| x | y |
| y | x |
| y | z |
| z | y |
| m | n |
| m | z |

I need to create a T-SQL query that will present all the possible pairs out of trasitivity, i.e. if x=y, y=z, then x=z. Also, simmetry has to be there, i.e. if there is x=y, then there should be y=x as well. In this particular case, I believe there is "full house", meaning that every letter is connected to all others through the intermediates. But I need a query that will show that. All I did is here (SQLFiddle fails to run it):

    WITH
    t AS
      (SELECT 'x' AS a, 'y' AS b
       UNION ALL
       SELECT 'y' AS a, 'x' AS b
       UNION ALL 
       SELECT 'y' AS a, 'z' AS b
       UNION ALL 
       SELECT 'z' AS a, 'y' AS b
       UNION ALL 
       SELECT 'm' AS a, 'n' AS b
       UNION ALL 
       SELECT 'm' AS a, 'z' AS b),

    coupled_reflective AS --for reflective couples we take either of them

      (SELECT t2.a, t2.b
       FROM t t1
       JOIN t t2 ON t1.a=t2.b
       AND t1.b!=t2.a),

    reversive_coupled_reflective AS --that's another half of the above couples (reversed)

      (SELECT t2.b, t2.a
       FROM t t1
       JOIN t t2 ON t1.a=t2.b
       AND t1.b!=t2.a),

    rs AS -- reduce the initial set (t)

      (SELECT *
       FROM coupled_reflective
       UNION
       SELECT *
       FROM t
       EXCEPT
       SELECT *
       FROM reversive_coupled_reflective),

     cte AS -- recursively iterate through the set to find transitive values (get linked by the left field)

      (SELECT a, b
       FROM rs
       UNION ALL
       SELECT rs.b, cte.b
       FROM rs
       JOIN cte ON rs.a=cte.a
       AND rs.b!=cte.b),

     cte2 AS -- recursively iterate through the set to find transitive values (get linked by the right field)

      (SELECT a, b
       FROM rs
       UNION ALL
       SELECT rs.a, cte.a
       FROM rs
       JOIN cte ON rs.b=cte.b
       AND rs.a!=cte.a)



    SELECT a, b FROM cte2
    UNION
    SELECT a, b FROM cte
    UNION
    SELECT a, b FROM t
    UNION
    SELECT b, a FROM t

But that doesn't do the trick, unfortunately.

The desired result should be

 | a | b |
 |---|---|
 | x | y |
 | y | x |
 | y | z |
 | z | y |
 | m | n |
 | m | z |
 | n | m |
 | z | m |
 | x | z |
 | z | x |
 | x | m |
 | m | x |
 | x | n |
 | n | x |
 | y | m |
 | m | y |
 | y | n |
 | n | y |

Is there a SQL-gifted buddy out there who can help me here, please? Thanks.

Upvotes: 4

Views: 376

Answers (1)

Gordon Linoff
Gordon Linoff

Reputation: 1269953

You can use recursive CTEs, but you need a list of already visited nodes. You can implement that using a string:

with cte as (
      select a, b, cast('{' + a + '}{' + b + '}' as varchar(max)) as visited
      from t
      union all
      select cte.a, t.b,
             (visited + '{' + t.b + '}')
      from cte join
           t
           on cte.b = t.a
      where cte.visited not like '%{' + t.b + '}%'
     )
select distinct a, b
from cte;

Note:

The above follows the directed links in the graph. If you want undirected links, then include both:

with t as (
      select a, b from yourtable
      union
      select b, a from yourtable
     ),

The rest of the logic follows using t.

Upvotes: 3

Related Questions