ManyToMany, минимальный набор ключей из KeyTable1, которые соответствуют выбранным элементам из KeyTable2? (Мне нужны классы w, x, y, z, что минимальные учителя удовлетворяют этому)?

Question

Во многих отношениях я пытаюсь решить проблему, в которой мне нужно найти наименьший набор элементов из первой таблицы, который обеспечивает покрытие для произвольного набора выбранных элементов из второй таблицы.

Например, представьте:
Учитель (TeacherID)
Класс (ClassID)
TeachClassXref (TeacherID, ClassID)

Если студенту необходимо учиться: 34,45,53,56,44,77,23,654,667

Как определить наименьший набор идентификаторов TeacherID, который будет преподавать в этих классах?

(Также подлежит определению: в случае, когда полное покрытие не может быть достигнуто, классы выброса не имеют общего учителя.)

---

Или используя терминологию из другого домена (но точно такую ​​же структуру таблицы):

Действия и роли: если мне нужно выполнить действия 1,3,6,7,9,33,45, к какой роли или набору ролей мне нужно принадлежать?

(я уверен, что для этой проблемы должно быть название, но мой гугл-фу меня подводит.)

Answer 1

Дайте этому попытку

SELECT
ClassID
into #RequiredClass
from CLass
where ClassID in (34,45,53,56,44,77,23,654,667)


create table #BestTeacher (TeacherID int)

while 1 = 1
begin

insert  #BestTeacher
SELECT top 1
  Teacher.TeacherID
FROM
  Teacher
  INNER JOIN TeacherClass
          ON Teacher.TeacherID = TeacherClass.TeacherID
  INNER JOIN #RequiredClass as Class
          ON TeacherClass.ClassID = Class.ClassID 
GROUP BY
  Teacher.TeacherID
  ,Teacher.TeacherName
order by count(Teacher.TeacherID) desc


delete #RequiredClass
where ClassID in (

 SELECT
#RequiredClass.ClassID
from #RequiredClass 
inner join 
  Teacher
  INNER JOIN TeacherClass
          ON Teacher.TeacherID = TeacherClass.TeacherID
  INNER JOIN Class
          ON TeacherClass.ClassID = Class.ClassID
on #RequiredClass.ClassID = Class.ClassID
inner join #BestTeacher
on #BestTeacher.TeacherID = Teacher.TeacherID)

   if @@rowcount = 0 break
end


select * from #BestTeacher
drop table #BestTeacher
drop table #RequiredClass