ManyToMany, minimum set of keys from KeyTable1 that match selected items from KeyTable2? (I need classes...
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
add a comment |
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
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
add a comment |
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
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
sql sql-server many-to-many
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
add a comment |
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
add a comment |
1 Answer
1
active
oldest
votes
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
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
add a comment |
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
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
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
add a comment |
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
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
add a comment |
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
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
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
add a comment |
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
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
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