ManyToMany, minimum set of keys from KeyTable1 that match selected items from KeyTable2? (I need classes...












1















In a many to many relationship, I'm trying to solve a problem where I need to find the smallest set of items from the first table that provide coverage for an arbitrary set of selected items from the second table.



For example, imagine:

Teacher (TeacherID)

Class (ClassID)

TeachClassXref (TeacherID, ClassID)



If a student needs to study classes: 34,45,53,56,44,77,23,654,667



How would one determine the smallest set of TeacherID's that would teach those classes?



(Also to be determined: in the case where complete coverage cannot be achieved, the outlier classes with no common teacher.)





Or using terminology from a different domain (but exact same table structure):



Activities & Roles: if I need to perform Activities 1,3,6,7,9,33,45, what Role or set of Roles do I need to belong to?



(I'm sure there has to be a name for this problem but my google-fu is failing me.)










share|improve this question

























  • do we need to consider the teachers already commited

    – Sanal Sunny
    Nov 14 '18 at 6:10













  • Basically, these 3 tables describe which teachers teach which classes; each class has multiple teachers, each teacher teaches multiple classes). Then, a student needs some set of <n> classes, and needs to know which single teacher, or which smallest set of teachers, teach ALL of those classes.

    – tbone
    Nov 14 '18 at 6:20











  • Consider a scenario A teacher is already occupied with a set of class. In which table is used to keep this info

    – Sanal Sunny
    Nov 14 '18 at 6:23













  • Actual class schedules are outside the scope - teachers & classes is just an example application of this problem, my actual scenario is Activities & Roles: if I need to perform Activities 1,3,6,7,9,33,45, what role or set of roles do I need to be assigned?

    – tbone
    Nov 14 '18 at 6:28











  • Can you provide some test data with expected output?

    – Dohsan
    Nov 14 '18 at 8:46
















1















In a many to many relationship, I'm trying to solve a problem where I need to find the smallest set of items from the first table that provide coverage for an arbitrary set of selected items from the second table.



For example, imagine:

Teacher (TeacherID)

Class (ClassID)

TeachClassXref (TeacherID, ClassID)



If a student needs to study classes: 34,45,53,56,44,77,23,654,667



How would one determine the smallest set of TeacherID's that would teach those classes?



(Also to be determined: in the case where complete coverage cannot be achieved, the outlier classes with no common teacher.)





Or using terminology from a different domain (but exact same table structure):



Activities & Roles: if I need to perform Activities 1,3,6,7,9,33,45, what Role or set of Roles do I need to belong to?



(I'm sure there has to be a name for this problem but my google-fu is failing me.)










share|improve this question

























  • do we need to consider the teachers already commited

    – Sanal Sunny
    Nov 14 '18 at 6:10













  • Basically, these 3 tables describe which teachers teach which classes; each class has multiple teachers, each teacher teaches multiple classes). Then, a student needs some set of <n> classes, and needs to know which single teacher, or which smallest set of teachers, teach ALL of those classes.

    – tbone
    Nov 14 '18 at 6:20











  • Consider a scenario A teacher is already occupied with a set of class. In which table is used to keep this info

    – Sanal Sunny
    Nov 14 '18 at 6:23













  • Actual class schedules are outside the scope - teachers & classes is just an example application of this problem, my actual scenario is Activities & Roles: if I need to perform Activities 1,3,6,7,9,33,45, what role or set of roles do I need to be assigned?

    – tbone
    Nov 14 '18 at 6:28











  • Can you provide some test data with expected output?

    – Dohsan
    Nov 14 '18 at 8:46














1












1








1








In a many to many relationship, I'm trying to solve a problem where I need to find the smallest set of items from the first table that provide coverage for an arbitrary set of selected items from the second table.



For example, imagine:

Teacher (TeacherID)

Class (ClassID)

TeachClassXref (TeacherID, ClassID)



If a student needs to study classes: 34,45,53,56,44,77,23,654,667



How would one determine the smallest set of TeacherID's that would teach those classes?



(Also to be determined: in the case where complete coverage cannot be achieved, the outlier classes with no common teacher.)





Or using terminology from a different domain (but exact same table structure):



Activities & Roles: if I need to perform Activities 1,3,6,7,9,33,45, what Role or set of Roles do I need to belong to?



(I'm sure there has to be a name for this problem but my google-fu is failing me.)










share|improve this question
















In a many to many relationship, I'm trying to solve a problem where I need to find the smallest set of items from the first table that provide coverage for an arbitrary set of selected items from the second table.



For example, imagine:

Teacher (TeacherID)

Class (ClassID)

TeachClassXref (TeacherID, ClassID)



If a student needs to study classes: 34,45,53,56,44,77,23,654,667



How would one determine the smallest set of TeacherID's that would teach those classes?



(Also to be determined: in the case where complete coverage cannot be achieved, the outlier classes with no common teacher.)





Or using terminology from a different domain (but exact same table structure):



Activities & Roles: if I need to perform Activities 1,3,6,7,9,33,45, what Role or set of Roles do I need to belong to?



(I'm sure there has to be a name for this problem but my google-fu is failing me.)







sql sql-server many-to-many






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Nov 14 '18 at 6:34







tbone

















asked Nov 14 '18 at 6:05









tbonetbone

2,9921570116




2,9921570116













  • do we need to consider the teachers already commited

    – Sanal Sunny
    Nov 14 '18 at 6:10













  • Basically, these 3 tables describe which teachers teach which classes; each class has multiple teachers, each teacher teaches multiple classes). Then, a student needs some set of <n> classes, and needs to know which single teacher, or which smallest set of teachers, teach ALL of those classes.

    – tbone
    Nov 14 '18 at 6:20











  • Consider a scenario A teacher is already occupied with a set of class. In which table is used to keep this info

    – Sanal Sunny
    Nov 14 '18 at 6:23













  • Actual class schedules are outside the scope - teachers & classes is just an example application of this problem, my actual scenario is Activities & Roles: if I need to perform Activities 1,3,6,7,9,33,45, what role or set of roles do I need to be assigned?

    – tbone
    Nov 14 '18 at 6:28











  • Can you provide some test data with expected output?

    – Dohsan
    Nov 14 '18 at 8:46



















  • do we need to consider the teachers already commited

    – Sanal Sunny
    Nov 14 '18 at 6:10













  • Basically, these 3 tables describe which teachers teach which classes; each class has multiple teachers, each teacher teaches multiple classes). Then, a student needs some set of <n> classes, and needs to know which single teacher, or which smallest set of teachers, teach ALL of those classes.

    – tbone
    Nov 14 '18 at 6:20











  • Consider a scenario A teacher is already occupied with a set of class. In which table is used to keep this info

    – Sanal Sunny
    Nov 14 '18 at 6:23













  • Actual class schedules are outside the scope - teachers & classes is just an example application of this problem, my actual scenario is Activities & Roles: if I need to perform Activities 1,3,6,7,9,33,45, what role or set of roles do I need to be assigned?

    – tbone
    Nov 14 '18 at 6:28











  • Can you provide some test data with expected output?

    – Dohsan
    Nov 14 '18 at 8:46

















do we need to consider the teachers already commited

– Sanal Sunny
Nov 14 '18 at 6:10







do we need to consider the teachers already commited

– Sanal Sunny
Nov 14 '18 at 6:10















Basically, these 3 tables describe which teachers teach which classes; each class has multiple teachers, each teacher teaches multiple classes). Then, a student needs some set of <n> classes, and needs to know which single teacher, or which smallest set of teachers, teach ALL of those classes.

– tbone
Nov 14 '18 at 6:20





Basically, these 3 tables describe which teachers teach which classes; each class has multiple teachers, each teacher teaches multiple classes). Then, a student needs some set of <n> classes, and needs to know which single teacher, or which smallest set of teachers, teach ALL of those classes.

– tbone
Nov 14 '18 at 6:20













Consider a scenario A teacher is already occupied with a set of class. In which table is used to keep this info

– Sanal Sunny
Nov 14 '18 at 6:23







Consider a scenario A teacher is already occupied with a set of class. In which table is used to keep this info

– Sanal Sunny
Nov 14 '18 at 6:23















Actual class schedules are outside the scope - teachers & classes is just an example application of this problem, my actual scenario is Activities & Roles: if I need to perform Activities 1,3,6,7,9,33,45, what role or set of roles do I need to be assigned?

– tbone
Nov 14 '18 at 6:28





Actual class schedules are outside the scope - teachers & classes is just an example application of this problem, my actual scenario is Activities & Roles: if I need to perform Activities 1,3,6,7,9,33,45, what role or set of roles do I need to be assigned?

– tbone
Nov 14 '18 at 6:28













Can you provide some test data with expected output?

– Dohsan
Nov 14 '18 at 8:46





Can you provide some test data with expected output?

– Dohsan
Nov 14 '18 at 8:46












1 Answer
1






active

oldest

votes


















1














Give this a try



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





share|improve this answer
























  • Interesting....I will have to think about this a bit more but it looks workable at first glance.

    – tbone
    Nov 14 '18 at 19:15











Your Answer






StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53294069%2fmanytomany-minimum-set-of-keys-from-keytable1-that-match-selected-items-from-ke%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes









1














Give this a try



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





share|improve this answer
























  • Interesting....I will have to think about this a bit more but it looks workable at first glance.

    – tbone
    Nov 14 '18 at 19:15
















1














Give this a try



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





share|improve this answer
























  • Interesting....I will have to think about this a bit more but it looks workable at first glance.

    – tbone
    Nov 14 '18 at 19:15














1












1








1







Give this a try



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





share|improve this answer













Give this a try



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






share|improve this answer












share|improve this answer



share|improve this answer










answered Nov 14 '18 at 8:48









RegBesRegBes

46929




46929













  • Interesting....I will have to think about this a bit more but it looks workable at first glance.

    – tbone
    Nov 14 '18 at 19:15



















  • Interesting....I will have to think about this a bit more but it looks workable at first glance.

    – tbone
    Nov 14 '18 at 19:15

















Interesting....I will have to think about this a bit more but it looks workable at first glance.

– tbone
Nov 14 '18 at 19:15





Interesting....I will have to think about this a bit more but it looks workable at first glance.

– tbone
Nov 14 '18 at 19:15




















draft saved

draft discarded




















































Thanks for contributing an answer to Stack Overflow!


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53294069%2fmanytomany-minimum-set-of-keys-from-keytable1-that-match-selected-items-from-ke%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

Florida Star v. B. J. F.

Danny Elfman

Retrieve a Users Dashboard in Tumblr with R and TumblR. Oauth Issues