What's the best way to list groups of values that are contained in other groups

Question

For example, starting with a table like this:

create table t as 
select 'A' as x, level as y from dual connect by level<=5
union all 
select 'B' as x, level+2 as y from dual connect by level<=5
union all 
select 'C' as x, level as y from dual connect by level<=3
union all 
select 'D' as x, level+2 as y from dual connect by level<=3;

alter table t add primary key (x, y);

select * from t;

X Y                      
- -
A 1                      
A 2                      
A 3                      
A 4                      
A 5                      
B 3                      
B 4                      
B 5                      
B 6                      
B 7                      
C 1                      
C 2                      
C 3                      
D 3                      
D 4                      
D 5         

How do I get this:

SUBSET_X SUPERSET_X 
-------- ---------- 
D        A          
C        A          
D        B         

I'm posting my own effort as an answer but wondering if there is some other fancy way, perhaps with analytics or a set operator I don't know about

--edit

My test data unintentionally implies that the sets always consist of consecutive integers - unfortunately this is not true with my real data.

Answer 1

This is similar to your first approach, Jack, with a few differences.

• It does all the counting in batches as opposed to in the HAVING clause. HAVING is a post aggregation filter, which is why sticking the COUNT in there is slow.
• It is easier to read by grace of the CTEs which break up the work into smaller chunks.
• Like your approach, it works both on Oracle 9.2+ and SQL Server 2005+ (and any other RDBMS that supports CTEs).

Your indexing strategy shouldn't matter that much if you are querying the whole table at once, but if you are interested in specific sets I recommend you have indexes both on (x, y) and (y, x).

One way or the other, this query should run very quickly:

WITH set_sizes AS (
  SELECT x, COUNT(*) AS set_size  -- "size" is a reserved keyword in Oracle
  FROM t
  GROUP BY x
)
, intersection_sizes AS (
  SELECT 
      sub.x     sub_x
    , super.x   super_x
    , COUNT(*)  intersection_size
  FROM 
                t sub
    INNER JOIN  t super
      ON  sub.y = super.y
      AND sub.x <> super.x
  GROUP BY
      sub.x
    , super.x
)
SELECT xs.sub_x, xs.super_x
FROM 
              set_sizes           ss
  INNER JOIN  intersection_sizes  xs
    ON  ss.x = xs.sub_x
    AND ss.set_size = xs.intersection_size
;

Edit: Per your tests against a large data set, it looks like this query is the speediest.

Answer 2

This does the trick but is not terribly fast:

select t1.x as subset_x, t2.x as superset_x
from t t1 join t t2 on(t1.y=t2.y and t1.x<>t2.x)
group by t1.x, t2.x
having count(*)=(select count(*) from t where x=t1.x);

Answer 3

This also does the trick but 'not terribly fast' would be a huge understatement this time unfortunately - I'm posting it anyway in case it is of academic interest to anyone:

with w as (select x, cast(collect(y) as table_integer) as ys from t group by x)
select w1.x as subset_x, w2.x as superset_x
from w w1 join w w2 on (w1.x<>w2.x and w1.ys submultiset of w2.ys);

Answer 4

This won't be fast either, but it is an alternative. It requires 11.2, but could be done in an earlier version if you create a custom aggregate function that does the same thing listagg does.

SELECT aa.x, bb.x FROM
(SELECT x, listagg(y, ',%,') WITHIN GROUP (ORDER BY y) z FROM t GROUP BY x) aa
JOIN
(SELECT x, listagg(y, ',,') WITHIN GROUP (ORDER BY y) z FROM t GROUP BY x) bb
ON bb.z LIKE '%' || aa.z || '%' AND aa.x <> bb.x;