MySQL 8.0

By using db<>fiddle, you agree to license everything you submit by Creative Commons CC0.
CREATE TABLE bag (
  `id` INTEGER,
  `name` VARCHAR(5)
);

INSERT INTO bag
  (`id`, `name`)
VALUES
  ('1', 'Bag A'),
  ('2', 'Bag B'),
  ('3', 'Bag C'),
  ('4', 'Bag D');

CREATE TABLE item (
  `id` INTEGER,
  `name` VARCHAR(6)
);

INSERT INTO item
  (`id`, `name`)
VALUES
  ('1', 'Pencil'),
  ('2', 'Pen'),
  ('3', 'Eraser'),
  ('4', 'Marker');

CREATE TABLE bag_item (
  `id` INTEGER,
  `bag_id` INTEGER,
  `item_id` INTEGER
);

INSERT INTO bag_item
  (`id`, `bag_id`, `item_id`)
VALUES
  ('1', '1', '1'),
  ('2', '1', '2'),
  ('3', '2', '1'),
  ('4', '2', '2'),
  ('5', '2', '3'),
  ('6', '2', '4'),
  ('7', '3', '1'),
  ('8', '3', '4'),
  ('9', '4', '1'),
  ('10', '4', '2'),
  ('11', '4', '3');

Records: 4  Duplicates: 0  Warnings: 0



Records: 4  Duplicates: 0  Warnings: 0



Records: 11  Duplicates: 0  Warnings: 0


SELECT
  base.id AS base_bag_id,
  s.id AS superset_bag_id
FROM bag base
JOIN bag s
   ON s.id <> base.id
  AND NOT EXiSTS (SELECT 1
    FROM bag_item bi
    WHERE bi.bag_id = base.id
      AND NOT EXISTS (SELECT 1
        FROM bag_item si
        WHERE si.item_id = bi.item_id
          AND si.bag_id = s.id
    )
);


base_bag_id
superset_bag_id


4
2

3
2

1
2

1
4


SELECT
  base.bag_id AS base_bag_id,
  s.id AS superset_bag_id
FROM bag_item base
JOIN bag s ON s.id <> base.bag_id
LEFT JOIN bag_item si
   ON si.bag_id = s.id
  AND si.item_id = base.item_id
GROUP BY
  base.bag_id,
  s.id
HAVING COUNT(si.item_id) = COUNT(*);


base_bag_id
superset_bag_id


1
4

1
2

3
2

4
2


SELECT
  base.bag_id AS base_bag_id,
  s.id AS superset_bag_id
FROM bag_item base
JOIN bag s
  ON s.id <> base.bag_id
  -- Limit the superset candidates we attempt to combine with to those
  -- that contain at least one of the items
  -- This improves performance significantly when there are a lot of
  -- bags and items
  AND s.id IN (
    SELECT DISTINCT overlap_bag_item.bag_id
    FROM bag_item AS base_bag_item_mirror
    JOIN bag_item AS overlap_bag_item
      ON overlap_bag_item.item_id = base_bag_item_mirror.item_id
    WHERE base_bag_item_mirror.bag_id = base.bag_id)
LEFT JOIN bag_item si
  ON si.bag_id = s.id
  AND si.item_id = base.item_id
GROUP BY
  base.bag_id,
  s.id
HAVING COUNT(si.item_id) = COUNT(*);


base_bag_id
superset_bag_id


1
2

1
4

3
2

4
2


SELECT
  base.bag_id AS base_bag_id,
  s.id AS superset_bag_id
FROM bag_item base
JOIN bag s
  ON s.id <> base.bag_id
  -- Limit the superset candidates we attempt to combine with to those
  -- that contain at least one of the items
  AND s.id IN (
    -- We're filtering out base bags using `IN`
    -- When combined with the `IN` statement, MySQL semijoin optimization
    -- attempts to create a temporary table with all the bag_items in it,
    -- defeating the purpose of this subquery and tanking performance
    -- We can turn that optimization off selectively with a hint tag
    SELECT /*+ NO_SEMIJOIN(MATERIALIZATION) */ DISTINCT overlap_bag_item.bag_id
    FROM bag_item AS base_bag_item_mirror
    JOIN bag_item AS overlap_bag_item
      ON overlap_bag_item.item_id = base_bag_item_mirror.item_id
    WHERE base_bag_item_mirror.bag_id = base.bag_id)
LEFT JOIN bag_item si
  ON si.bag_id = s.id
  AND si.item_id = base.item_id
WHERE base.bag_id IN (1, 4)
GROUP BY
  base.bag_id,
  s.id
HAVING COUNT(si.item_id) = COUNT(*);


base_bag_id
superset_bag_id


4
2

1
2

1
4


SELECT
  base.bag_id AS base_bag_id,
  si.bag_id AS superset_bag_id
FROM (
    SELECT *,
      COUNT(*) OVER (PARTITION BY base.bag_id) AS count
    FROM bag_item base
) base
LEFT JOIN bag_item si
   ON si.item_id = base.item_id
  AND si.bag_id <> base.bag_id
GROUP BY
  base.bag_id,
  si.bag_id
HAVING COUNT(*) = MIN(base.count);


base_bag_id
superset_bag_id


1
4

1
2

3
2

4
2