复合课程先决条件(a，b，c和x或y以及z风格中的一个或多个) [英] Compound course prerequisites (One or more of a,b,c and either x or y as well as z style)
问题描述
感谢大家的投入，特别是在赏金关闭期间，这是非常有用的.
Thanks everyone for the input, especially during the closing hours of the bounty, it's been incredible helpful.
This is a followup question to Select courses that are completely satisfied by a given list of prerequisites, and further explains the situation. It is definitely recommended to read to help understand this question further. (Courses and subjects are distinct entities, subjects are only prerequisites for courses and need not be prerequisites for other subjects - think high school subjects leading to possible university courses)
我的数据库如此布置.
Prerequisite:
+---------------+---------------+
| Id | Name | (Junction table)
|---------------|---------------| CoursePrerequisites:
| 1 | Maths | +---------------+---------------+
| 2 | English | | Course_FK | Prerequisite_FK
| 3 | Art | |---------------|---------------|
| 4 | Physics | | 1 | 1 |
| 5 | Psychology | | 1 | 2 |
+-------------------------------+ | 2 | 3 |
| 2 | 5 |
Course: | 5 | 4 |
+---------------+---------------+ +---------------v---------------+
| Id | Name |
|---------------|---------------|
| 1 | Course1 |
| 2 | Course2 |
| 3 | Course3 |
| 4 | Course4 |
| 5 | Course5 |
+---------------v---------------+
我一直在使用以下查询:
and I've been making use of the following query:
SELECT Course.id, course.Name, GROUP_CONCAT(DISTINCT Prerequisite.Name) AS 'Prerequisite Name(s)'
FROM Course
LEFT JOIN CoursePrerequisites ON Course.id = CoursePrerequisites.Course_FK
LEFT JOIN Prerequisite ON Prerequisite.id = CoursePrerequisites.Prerequisite_FK
WHERE NOT EXISTS
(SELECT 1
FROM CoursePrerequisites
WHERE Course.id = CoursePrerequisites.Course_FK
AND CoursePrerequisites.Prerequisite_FK NOT IN (SELECT Prerequisite.id FROM Prerequisite Where Name = 'Art' OR Name = 'English' OR Name = 'Psychology''))
GROUP BY Course.id;
选择适合其先决条件的课程的效果很好.
Which works well to select courses that are exactly filled by their prerequisites.
但是，我遇到了一个障碍，试图以一种能够代表具有复合先决条件的课程的方式来组织数据库.例如，一门课程可能需要英语，数学以及艺术或心理学.另一个示例可能是先决条件英语，以及物理，心理学，艺术等专业中的两种.
However, I've come to a roadblock trying to organise the database in such a way that is is able to represent courses with compound prerequisites. For example, a course may require English, Maths and either Art or Psychology. Another example may be prerequisites English and two of either Physics, Psychology, Art, etc.
构造数据库以处理这些类型的先决条件的合适方法是什么(我尝试进行一些搜索，但找不到任何内容(找到了，但没有帮助:
What would be an appropriate way to structure the database to handle these types of prerequisites (I tried doing some searches, but I couldn't find anything (edit: found this, but not helpful: Modeling courses and pre-requisites in the database) and how would I modify the above query to again return only courses that have at least their prerequisites filled?
为澄清起见: 给定一个科目列表(来自前提条件"表)，我希望返回一个给定的课程列表.在当前的数据库模式中，给定数学，英语，艺术和物理，返回的课程应为课程1和课程5(而不是课程2-它具有美术和心理学的先决条件，给定输入不满足后者的先决条件)，如连接表. 我希望将课程先决条件的复杂性从简单的与"(课程1需要数学和英语)扩展到可以处理或"/一组y中的x的东西(例如，课程1现在需要英语，数学和一个或更多的艺术或心理学).
For clarification: Given a list of subjects (from Prerequisite table), I wish to return a list of Courses that would be eligible given those subjects. In the current database schema, given Maths, English, Art and Physics, returned courses should be Course1 and Course5 (and NOT Course2 - it has prerequisites Art and Psychology, the later of which is not satisfied by the given input) as stipulated by the junction table. I wish to extend the complexity of a Course's prerequisites from a simple 'AND' (Course1 requires Maths AND English) to something that can handle 'OR'/One of x from a set of y (e.g. Course1 now requires English, Maths AND One or more of Art or Psychology).
进度
我一直在考虑用一些额外的列来扩展联结表，这些列用于以下至少一个"和至少两个以下"等，另外一个列用于全部"并放置前提条件变成那样的结构.这是解决问题的明智方法吗?在MySQL中，如果找到一个给定的主题列表，可以有效地查询以找到符合条件的课程呢?
I've been thinking of extending the junction table with a few extra columns for 'at least one of the following' and 'at least two of', etc as well as another column for 'all of' and placing the prerequisites into a structure that way. Is this a sane way to go about this and what would be an efficient query in MySQL to query to find eligible courses given a list of subjects?
进度:
Kuba Wyrostek在下面建议将每个课程的所有先决条件组合列举为不同的集合.尽管这行得通，但我需要对大约6000个行进行此操作，每个行都有许多枚举.有没有更有效的方法来做到这一点?
Kuba Wyrostek has suggested below to enumerate all prerequisite combinations for each course into distinct sets. While this would work, I need to do this for ~6k rows, each with many enumerations. Is there a more efficient way to accomplish this?
推荐答案
在我看来，在一个表中对合取和析取建模总是很不容易，并且会导致违反规范形式或无法预测需要多少个自我联接.据我了解，您的前提条件通常可以表达为连词的替代形式.因此，以下内容:
In my opinion modeling conjunction and disjunction in one table is always uneasy and leads to either violation of normal form or inability to predict how many self joins are necessary. What I understand is that your prerequisites can be generally always expressed as alternatives of conjunctions. So the following:
Math AND English AND (Physics1 OR Physics2)
可能表示为:
(Math AND English AND Physics1) OR (Math AND English AND Physics2)
得出一个结论，您可能需要一个描述先决条件集的中间表.当任何项设置成功时可以使用课程，而当所有项中的主题完成时则设置成功.
This lead to a conclusion, that you probably need an intermediate table describing sets of prerequisites. A course is available when any of sets is successful, while set is successful when all of subjects in the set are completed.
所以结构可能看起来像这样:
So the structure may look like this:
Prerequisite:
+---------------+---------------+
| Id | Name |
|---------------|---------------| PrerequisiteSets:
| 1 | Maths | +---------------+---------------+
| 2 | English | | SetNumber | Prerequisite_FK
| 3 | Art | |---------------|---------------|
| 4 | Physics | | 1 | 1 |
| 5 | Psychology | | 1 | 2 |
+-------------------------------+ | 1 | 4 |
| 2 | 1 |
| 2 | 2 |
Course: | 2 | 5 |
+---------------+---------------+ +---------------v---------------+
| Id | Name |
|---------------|---------------|
| 1 | Course1 |
| 2 | Course2 |
| 3 | Course3 |
| 4 | Course4 |
| 5 | Course5 |
+---------------v---------------+
CoursePrerequisite:
+---------------+---------------+
| Course_FK | SetNumber |
|---------------|---------------|
| 5 | 1 |
| 5 | 2 |
+---------------v---------------+
示例5可以通过SetNumber 1(数学，英语，物理学)或SetNumber2(数学，英语，心理学)来满足.
An example Course5 can be satisfied with either SetNumber 1 (Math, English, Physics) or SetNumber 2 (Math, English, Psychology).
不幸的是，现在为时已晚，无法为我提供确切的查询，但是如果您有需要，我可以在明天提供答复.祝你好运！ :-)
Unfortunately it's too late here for me to help you with exact queries now, but in case you need it I can extend my answer tomorrow. Good luck though! :-)
编辑
要生成查询，我将从观察开始，当集合中的所有先决条件是给定先决条件的子集时，将匹配该特定集合.这导致条件，集合中不同先决条件的数量必须与该集合中的给定集合中的前提条件的数量匹配.基本上(假设SetNumber-Prerequisite_FK是表中的唯一对):
To generate queries I'd start with observation, that particular set is matched, when all prerequisites in set are a subset of given prerequisites. This leads to condition, that number of distinct prerequisites in set must match number of prerequisites in this set that are also in given set. Basically (assumming SetNumber-Prerequisite_FK is unique pair in table):
select
SetNumber,
count(Prerequisite_FK) as NumberOfRequired,
sum(case when Prerequisite.Name in ('Math','English','Art') then 1 else 0 end)
as NumberOfMatching
from PrerequisiteSets
inner join Prerequisite on PrerequisiteSets.Prerequisite_FK = Prerequisite.ID
group by SetNumber
having
count(Prerequisite_FK)
=
sum(case when Prerequisite.Name in ('Math','English','Art') then 1 else 0 end)
现在获得最终课程归结为获得所有课程，在上面的查询结果中至少找到了一组数字.像这样开始(肯定可以更好地表达并通过连接进行优化，但总体思路是相同的):
Now getting final Courses boils down to getting all courses, which at least one set number is found in the results of query above. Starting like this (definitely can be expressed better and optimized with joins but general idea is the same):
select Id, Name
from Course
where Id in
(select Course_FK from CoursePrerequisite
where SetNumber in
(
-- insert query from above (but only first column: SetNumber, skip the two latter)
) as MatchingSets
) as MatchingCourses
这篇关于复合课程先决条件(a，b，c和x或y以及z风格中的一个或多个)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
