CODEWITHSUNDEEP
sqlsql-servergroup-bymany-to-manycommon-table-expression
Ravi Dhanwani
Ravi Dhanwani

Reputation: 11

CTE to Group Employees that are in different departments Many to Many

Can anyone help please! I just cant seem to solve this puzzle?

Input Table 

DepartmentID    EmpID
-----------------------
   1             100
   1             101 
   1             103 
   1             200
   2             300
   2             350
   3             350
   3             100
   4             50
   4             30
   4             45
   5             50
   5             51
   5             52
   5             53
   6             53
   6             54
   7             54
   7             55
   8             55
   8             56
  10             800
  11             900

Output Table

Please note that GroupID is created by us to group departments that have common employees, with the condition that 1 employee cannot be in two departments. 

GroupID      Department
-----------------------
1000            1
1000            2
1000            3
1001            4
1001            5
1001            6
1001            7
1001            8
1002            10
1003            11

Example to show how and why Department 1, 2 & 3 are grouped:

EmpID 100 is common between Department 1 & 3, but wait! EmpID 350 is common between 2 & 3 as well. So group them as well. Now the Group created by departments 1, 2 and 3 do not any product that is in any other department, then we can stop.

Note: This is not a 'normal' group by because we dont want any 2 groups that we create to have same employee.

LOGIC:

Step1: EmpID 50 is common between department 4 & 5. So Group 4 & 5 together

Step2: So this means Group of 4 & 5 have 50,30,45,51,52,53 unique employees

Step3: But wait! the Department 6 has EmpID 53 common with the Group of 4 & 5, formed in step2

Step4: Group department 4, 5, and 6. This new group has unique employees of 50,30,45,51,52,53,54

Step5: But wait! the department 7 has EmpID of 54, which is common with the Group formed in step4. So Group them together

This goes on.... Till we don`t have any employee that is not in 2 groups. So in this case Group 7, Group 8 will also need to be 'merged' into the Group that is mentioned in Step 4.

Upvotes: 1

Views: 73

Answers (1)

Gordon Linoff
Gordon Linoff

Reputation: 1269753

This is a graph traversal problem that requires recursive CTEs. I think this is one approach:

with cte as (
      select department, empid
      from inputs
      union all
      select cte.department, i.empid
      from inputs i join
           cte
           on i.empid = cte.empid and i.department <> cte.department
    )
select department,
       row_number() over (order by min(empid)) as groupid
from cte
group by deparment;

Upvotes: 1

Related Questions