SQL Solution to Grab Largest Group with Overlap

Question

I have an input of a names and associated groups. I desire an output of a de-duplicated version of the input, except for when groups overlap, I want the summation of the overlapping groups.

Name    Group
Jeff    1
John    1
Frank   1
Jeff    2
John    2
Frank   2
Fred    2
Steve   3
Sam     3
Jim     3

So for this example there are three groups, group 1, 2, and 3. There is overlap between group 1 and 2, (Jeff, John, and Frank all belong to both 1 and 2, and Fred is only in group 2). Given that there's overlap in group 1 and 2, I want to combine them into one single group, with all of the names in either group. I also want to keep groups without overlap separate. This is my desired output:

Name    Group
Jeff    1
John    1
Frank   1
Fred    1
Steve   2
Sam     2
Jim     2

Is this possible in SQL?

Dems_53341 · Answer

I have a solution, though it's probably really costly for large data sets.

It's also hard to explain, but I'll try...

First, look at how we can combine groups base on "person" alone:

PersonA is a member of Groups {1, 2, 3}
   Group2 can therefore be combined in to Group1
   AND
   Group3 can therefore be combined in to Group1

PersonB is a member of Groups    {2, 3, 4}
   Group3 can therefore be combined in to Group2
   AND
   Group4 can therefore be combined in to Group2

PersonC is a member of Groups       {3, 4, 5}
   Group4 can therefore be combined in to Group3
   AND
   Group5 can therefore be combined in to Group3

This gives us...
   From PersonA : (G2 → G1) and (G3 → G1)
   From PersonB :               (G3 → G2) and (G4 → G2)
   From PersonC :                             (G4 → G3) and (G5 → G3)

Then look at it "vertically", such that if a group can be combined in to more than one other group, take the lowest option.

        Overall : (G2 → G1) and (G3 → G1) and (G4 → G2) and (G5 → G3)

If we apply those "combining of groups" to the original data we get this...

| person | original groups | revised groups               |
+--------+-----------------+------------------------------+
|   A    | {1, 2, 3}       | {1, 1, 1}       => {1}       |
|   B    |    {2, 3, 4}    |    {1, 1, 2}    => {1, 2}    |
|   C    |       {3, 4, 5} |       {1, 2, 3} => {1, 2, 3} |

So, we've gone from 5 distinct groups, to three distinct groups.

If we repeat that process again, starting from the revised groups, all three people end up as members of just Group1.

The number of times you need to repeat this depends on how many groups overlap each other and in what way.

The following code should be able to apply that process as many times as is necessary. It keeps going until each person is a member of just one group. There may still be more than one group at the end, they're the groups which don't overlap with each other.

That may take many iterations, dealing with every person every time, which may be slow, especially on larger datasets.

But, I think, it works for all cases. (Even though you probably shouldn't do this in SQL, at least now you can.)

Demo including test data : dbfiddle.uk demo

WITH
  RECURSIVE "membership"
AS
(
  SELECT
    "name",
    "group_id",
    (SELECT COUNT(DISTINCT "name") FROM "name_group_links")   AS unique_names,
    0                                                         AS current_depth,
    COUNT(*) OVER ()                                          AS current_links
  FROM
    "name_group_links"

  UNION ALL

  SELECT
    *,
    COUNT(*) OVER ()   AS "current_links"
  FROM
  (
    SELECT DISTINCT
      "name",
      MIN("min_group_by_name") OVER (PARTITION BY "group_id")   AS "group",
      "unique_names",
      "current_depth" + 1                                       AS "current_depth"
    FROM
    (
      SELECT
        *,
        MIN("group_id") OVER (PARTITION BY "name")  AS "min_group_by_name"
      FROM
        "membership"
      WHERE
        "current_links" > "unique_names"
    )
      AS "collapse_groups_by_name"
  )
    AS "collapse_groups_by_group"
)
SELECT
  "current_depth",
  "name",
  "group_id"
FROM
  "membership"
WHERE
  "current_links" = "unique_names"
ORDER BY
  "current_depth",
  "name",
  "group_id"
;

SQL Solution to Grab Largest Group with Overlap

1 Answers