感谢大家的投入,尤其是在赏金的最后几个小时,这是非常有帮助的。
这是https://stackoverflow.com/questions/20671624/select-courses-that-are-completely-satisfied-by-a-given-list-of-prerequisites的后续问题,并进一步解释了情况。为了进一步理解这个问题,我们建议一定要阅读。(课程和科目是不同的实体,科目只是课程的先决条件,而不一定是其他科目的先决条件-想想高中科目导致可能的大学课程)
我把我的数据库布置成这样。
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---------------+
我一直在使用以下查询:
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;
它可以很好地选择课程,而这些课程正是由他们的先决条件来填补的。
然而,我遇到了一个障碍,试图以这样一种方式来组织数据库,即能够代表具有复合先决条件的课程。例如,一门课程可能需要英语、数学、艺术或心理学。另一个例子可能是英语基础和物理、心理学、艺术等两门专业。
如何构造数据库以处理这些类型的先决条件(我尝试了一些搜索,但找不到任何东西(编辑:找到这个,但没有帮助:Modeling courses and pre-requisites in the database),我将如何修改上面的查询以再次返回至少已经满足了它们的先决条件的课程?
澄清:给出一份科目清单(从先决条件表),我希望返回一份根据这些科目符合资格的课程清单。在目前的数据库模式中,给定数学、英语、艺术和物理,返回的课程应该是Course1和Course5 (而不是Course2 -它有艺术和心理学的先决条件,后者不能满足给定输入的要求)。我希望将课程先决条件的复杂性从简单的‘和’(Course1需要数学和英语)扩展到能够处理y集合中的‘or’/x中的一个(例如,Course1现在需要英语、数学和一个或多个艺术或心理学)。
进度编辑:
我一直在考虑用几个额外的列来扩展连接表,比如“至少一个”和“至少两个”等等,还有另一列表示“所有”,并以这种方式将先决条件放置到结构中。这是一种明智的方法吗?在MySQL中,怎样才能有效地查询到有资格的课程,给出一个科目列表?
进度:
Kuba建议在下面列举每个课程的所有先决条件组合为不同的集合。虽然这是可行的,但我需要对~6k行这样做,每个行都有许多枚举。是否有更有效的方法来完成这一任务?
发布于 2014-02-12 22:01:58
在我看来,在一个表中建模、连接和分离总是不容易的,并且会导致违反正常形态或无法预测需要多少自我连接。我所理解的是,你的先决条件通常可以用连词的替代词来表达。因此,以下情况:
Math AND English AND (Physics1 OR Physics2)
其表达方式可与以下几点相同:
(Math AND English AND Physics1) OR (Math AND English AND Physics2)
由此得出的结论是,您可能需要一个描述先决条件集的中间表。当任何一组都成功时,课程是可用的,当集合中的所有科目都完成时,set是成功的。
所以这个结构可能是这样的:
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---------------+
一个例子Course5可以满足于SetNumber 1(数学,英语,物理)或SetNumber 2(数学,英语,心理学)。
不幸的是,现在对我来说已经太晚了,无法帮助您进行准确的查询,但如果您需要,我明天可以扩展我的答案。祝你好运!-)
编辑
为了生成查询,我从观察开始,当集合中的所有先决条件都是给定先决条件的子集时,特定的集合是匹配的。这导致条件,集合中的不同先决条件的数量必须匹配该集合中也在给定集合中的先决条件数。基本上(假设SetNumber- pair _FK是表中唯一的对):
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)
现在获得最后的课程可以归结为获得所有的课程,在上面的查询结果中至少可以找到一个集合数。像这样开始(当然可以用joins更好地表达和优化,但是一般的想法是一样的):
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
发布于 2014-02-17 17:29:01
Kuba建议在下面列举每个课程的所有先决条件组合为不同的集合。虽然这是可行的,但我需要对~6k行这样做,每个行都有许多枚举。是否有更有效的方法来完成这一任务?
存储设备是一个显而易见的选择,我同意Kuba的观点。但我建议采取一种不同的方法:
prereqs: courses:
+------+------------+ +------+------------+
| p_id | Name | | c_id | Name |
|------|------------| |------|------------|
| 1 | Math | | 1 | Course1 |
| 2 | English | | 2 | Course2 |
| 3 | Art | | 3 | Course3 |
| 4 | Physics | | 4 | Course4 |
| 5 | Psychology | | 5 | Course5 |
+------+------------+ +------+------------+
compound_sets: compound_sets_prereqs:
+-------+-------+-------+ +-------+-------+
| s_id | c_id | cnt | | s_id | p_id |
|-------|-------|-------| |-------|-------|
| 1 | 1 | 1 | | 1 | 1 |
| 2 | 1 | 2 | | 1 | 2 |
| 3 | 2 | 1 | | 2 | 3 |
| 4 | 2 | null | | 2 | 4 |
| 5 | 3 | null | | 2 | 5 |
+-------+-------+-------+ | 3 | 1 |
| 3 | 4 |
| 4 | 1 |
| 4 | 2 |
| 5 | 2 |
| 5 | 3 |
+-------+-------+
上面的"cnt“列存储所需的最小匹配数,NULL值意味着所有先决条件都必须匹配。因此,在我的示例中,我们有以下要求:
Course1:(数学或英语)和(至少有两门艺术、物理和心理学)
Course2:(数学或物理)和(数学和英语)
Course3:英语与艺术
下面是SQL:
select t.c_id
, c.name
from ( select c_id
, sets_cnt
-- flag the set if it meets the requirements
, case when matched >= min_cnt then 1 else 0 end flag
from ( select c.c_id
, cs.s_id
-- the number of matched prerequisites
, count(p.p_id) matched
-- if the cnt is null - we need
-- to match all prerequisites
, coalesce( cnt, count(csp.p_id) ) min_cnt
-- the total number of sets the course has
, ( select count(1)
from compound_sets t
where t.c_id = c.c_id
) sets_cnt
from courses c
join compound_sets cs
on cs.c_id = c.c_id
join compound_sets_prereqs csp
on cs.s_id = csp.s_id
left join ( select p_id
from prereqs p
-- this data comes from the outside
where p.name in ( 'Physics',
'English',
'Math',
'Psychology' )
) p
on csp.p_id = p.p_id
group by c.c_id, cs.s_id, cs.cnt
) t
) t
, courses c
where t.c_id = c.c_id
group by t.c_id, c.name, sets_cnt
-- check that all sets of this course meet the requirements
having count( case when flag = 1 then 1 else null end ) = sets_cnt
发布于 2014-02-17 19:52:41
这是我的一个培训实验室的剪贴,我希望它是正确的,我现在不能测试它,听起来像你的任务。
它只是使用比萨饼和配料,我通常在午餐前做:-)
CREATE TABLE Pizzas
(Pizza# INTEGER NOT NULL PRIMARY KEY,
PizzaName VARCHAR(30) NOT NULL UNIQUE
);
INSERT INTO Pizzas VALUES(1, 'Margherita')
;INSERT INTO Pizzas VALUES(2, 'Salami')
;INSERT INTO Pizzas VALUES(3, 'Prosciutto')
;INSERT INTO Pizzas VALUES(4, 'Funghi')
;INSERT INTO Pizzas VALUES(5, 'Hawaii')
;INSERT INTO Pizzas VALUES(6, 'Calzone')
;INSERT INTO Pizzas VALUES(7, 'Quattro Stagioni')
;INSERT INTO Pizzas VALUES(8, 'Marinara')
;INSERT INTO Pizzas VALUES(9, 'Vegetaria')
;INSERT INTO Pizzas VALUES(10, 'Diavola')
;INSERT INTO Pizzas VALUES(11, 'Tonno')
;INSERT INTO Pizzas VALUES(12, 'Primavera')
;INSERT INTO Pizzas VALUES(13, 'Gorgonzola')
;INSERT INTO Pizzas VALUES(14, 'Fantasia')
;INSERT INTO Pizzas VALUES(15, 'Quattro Formaggi')
;INSERT INTO Pizzas VALUES(16, 'Napolitane')
;INSERT INTO Pizzas VALUES(17, 'Duplicato')
;
CREATE TABLE Toppings
(Topping# INTEGER NOT NULL PRIMARY KEY,
Topping VARCHAR(30) NOT NULL UNIQUE
);
INSERT INTO Toppings VALUES(1, 'Tomatoes')
;INSERT INTO Toppings VALUES(2, 'Mozzarella')
;INSERT INTO Toppings VALUES(3, 'Salami')
;INSERT INTO Toppings VALUES(4, 'Mushrooms')
;INSERT INTO Toppings VALUES(5, 'Chillies')
;INSERT INTO Toppings VALUES(6, 'Pepper')
;INSERT INTO Toppings VALUES(7, 'Onions')
;INSERT INTO Toppings VALUES(8, 'Garlic')
;INSERT INTO Toppings VALUES(9, 'Olives')
;INSERT INTO Toppings VALUES(10, 'Capers')
;INSERT INTO Toppings VALUES(11, 'Tuna')
;INSERT INTO Toppings VALUES(12, 'Squid')
;INSERT INTO Toppings VALUES(13, 'Pineapple')
;INSERT INTO Toppings VALUES(14, 'Spinach')
;INSERT INTO Toppings VALUES(15, 'Scallop')
;INSERT INTO Toppings VALUES(16, 'Ham')
;INSERT INTO Toppings VALUES(17, 'Gorgonzola')
;INSERT INTO Toppings VALUES(18, 'Asparagus')
;INSERT INTO Toppings VALUES(19, 'Fried egg')
;INSERT INTO Toppings VALUES(20, 'Anchovies')
;INSERT INTO Toppings VALUES(21, 'Corn')
;INSERT INTO Toppings VALUES(22, 'Artichock')
;INSERT INTO Toppings VALUES(23, 'Seafood')
;INSERT INTO Toppings VALUES(24, 'Brokkoli')
;INSERT INTO Toppings VALUES(25, 'Anchovis')
;INSERT INTO Toppings VALUES(26, 'Parmesan')
;INSERT INTO Toppings VALUES(27, 'Goat cheese')
;
CREATE TABLE PizzaToppings
(Pizza# INTEGER NOT NULL,
Topping# INTEGER NOT NULL,
UNIQUE (Pizza#, Topping#)
) PRIMARY INDEX(Pizza#);
INSERT INTO PizzaToppings VALUES(1, 1)
;INSERT INTO PizzaToppings VALUES(1, 2)
;INSERT INTO PizzaToppings VALUES(2, 1)
;INSERT INTO PizzaToppings VALUES(2, 2)
;INSERT INTO PizzaToppings VALUES(2, 3)
;INSERT INTO PizzaToppings VALUES(3, 1)
;INSERT INTO PizzaToppings VALUES(3, 2)
;INSERT INTO PizzaToppings VALUES(3, 16)
;INSERT INTO PizzaToppings VALUES(4, 1)
;INSERT INTO PizzaToppings VALUES(4, 2)
;INSERT INTO PizzaToppings VALUES(4, 4)
;INSERT INTO PizzaToppings VALUES(5, 1)
;INSERT INTO PizzaToppings VALUES(5, 2)
;INSERT INTO PizzaToppings VALUES(5, 13)
;INSERT INTO PizzaToppings VALUES(5, 16)
;INSERT INTO PizzaToppings VALUES(6, 1)
;INSERT INTO PizzaToppings VALUES(6, 2)
;INSERT INTO PizzaToppings VALUES(6, 4)
;INSERT INTO PizzaToppings VALUES(6, 11)
;INSERT INTO PizzaToppings VALUES(6, 22)
;INSERT INTO PizzaToppings VALUES(7, 1)
;INSERT INTO PizzaToppings VALUES(7, 2)
;INSERT INTO PizzaToppings VALUES(7, 4)
;INSERT INTO PizzaToppings VALUES(7, 6)
;INSERT INTO PizzaToppings VALUES(7, 16)
;INSERT INTO PizzaToppings VALUES(8, 1)
;INSERT INTO PizzaToppings VALUES(8, 2)
;INSERT INTO PizzaToppings VALUES(8, 8)
;INSERT INTO PizzaToppings VALUES(8, 9)
;INSERT INTO PizzaToppings VALUES(8, 12)
;INSERT INTO PizzaToppings VALUES(8, 15)
;INSERT INTO PizzaToppings VALUES(8, 16)
;INSERT INTO PizzaToppings VALUES(8, 23)
;INSERT INTO PizzaToppings VALUES(9, 1)
;INSERT INTO PizzaToppings VALUES(9, 2)
;INSERT INTO PizzaToppings VALUES(9, 5)
;INSERT INTO PizzaToppings VALUES(9, 6)
;INSERT INTO PizzaToppings VALUES(9, 7)
;INSERT INTO PizzaToppings VALUES(9, 8)
;INSERT INTO PizzaToppings VALUES(9, 9)
;INSERT INTO PizzaToppings VALUES(9, 14)
;INSERT INTO PizzaToppings VALUES(9, 18)
;INSERT INTO PizzaToppings VALUES(10, 1)
;INSERT INTO PizzaToppings VALUES(10, 2)
;INSERT INTO PizzaToppings VALUES(10, 5)
;INSERT INTO PizzaToppings VALUES(10, 7)
;INSERT INTO PizzaToppings VALUES(10, 9)
;INSERT INTO PizzaToppings VALUES(10, 10)
;INSERT INTO PizzaToppings VALUES(11, 1)
;INSERT INTO PizzaToppings VALUES(11, 2)
;INSERT INTO PizzaToppings VALUES(11, 7)
;INSERT INTO PizzaToppings VALUES(11, 11)
;INSERT INTO PizzaToppings VALUES(12, 1)
;INSERT INTO PizzaToppings VALUES(12, 2)
;INSERT INTO PizzaToppings VALUES(12, 3)
;INSERT INTO PizzaToppings VALUES(12, 4)
;INSERT INTO PizzaToppings VALUES(13, 1)
;INSERT INTO PizzaToppings VALUES(13, 2)
;INSERT INTO PizzaToppings VALUES(13, 16)
;INSERT INTO PizzaToppings VALUES(13, 17)
;INSERT INTO PizzaToppings VALUES(13, 24)
;INSERT INTO PizzaToppings VALUES(14, 1)
;INSERT INTO PizzaToppings VALUES(14, 2)
;INSERT INTO PizzaToppings VALUES(14, 10)
;INSERT INTO PizzaToppings VALUES(14, 19)
;INSERT INTO PizzaToppings VALUES(14, 20)
;INSERT INTO PizzaToppings VALUES(14, 21)
;INSERT INTO PizzaToppings VALUES(15, 1)
;INSERT INTO PizzaToppings VALUES(15, 2)
;INSERT INTO PizzaToppings VALUES(15, 17)
;INSERT INTO PizzaToppings VALUES(15, 26)
;INSERT INTO PizzaToppings VALUES(15, 27)
;INSERT INTO PizzaToppings VALUES(16, 1)
;INSERT INTO PizzaToppings VALUES(16, 2)
;INSERT INTO PizzaToppings VALUES(16, 4)
;INSERT INTO PizzaToppings VALUES(16, 5)
;INSERT INTO PizzaToppings VALUES(16, 16)
;INSERT INTO PizzaToppings VALUES(17, 1)
;INSERT INTO PizzaToppings VALUES(17, 2)
;INSERT INTO PizzaToppings VALUES(17, 4)
;INSERT INTO PizzaToppings VALUES(17, 6)
;INSERT INTO PizzaToppings VALUES(17, 16)
;
REPLACE VIEW PizzaView AS
SELECT
P.Pizza#
,P.PizzaName
,T.Topping
FROM
Pizzas P
JOIN
PizzaToppings PT
ON P.Pizza# = PT.Pizza#
JOIN
Toppings Z ON PT.Topping# = T.Topping#
;
/***
1. Return all pizzas which are a superset of the searched toppings.
*At least* ('tomaten', 'mozzarella', 'salami') and maybe additional toppings:
Salami, Primavera
***/
/*** 1. ***/
SELECT
Pizza#
,PizzaName
,COUNT(*) AS #Toppings
FROM
PizzaView
WHERE
Topping IN ('tomatoes', 'mozzarella', 'salami')
GROUP BY 1,2
HAVING COUNT(*) = 3
;
/***
2. Return all pizzas which are a subset of the searched toppings.
*At most* toppings ('tomaten', 'mozzarella', 'salami'), but no other toppings:
Salami, Margherita
***/
/*** 2. ***/
SELECT
Pizza#
,PizzaName
,COUNT(*) AS #Toppings
FROM
PizzaView
GROUP BY 1,2
HAVING
SUM(CASE WHEN Topping IN ('tomatoes', 'mozzarella', 'salami') THEN 0 ELSE 1 END) = 0
ORDER BY #Toppings DESC
;
/***
3. Return all pizzas which are a exactly made of the searched toppings.
*All toppings* ('tomaten', 'mozzarella', 'salami'), but no other toppings
Salami
***/
/*** 3. ***/
SELECT
Pizza#
,PizzaName
,COUNT(*) AS #Toppings
FROM
PizzaView
GROUP BY 1,2
HAVING
SUM(CASE WHEN Topping IN ('tomatoes', 'mozzarella', 'salami') THEN 1 ELSE -1 END) = 3
ORDER BY #Toppings
;
/***
4. Return all pizzas which are a superset of the searched toppings.
*At least* toppings ('tomaten' and 'mozzarella') and ('olives' or 'capers')
Diavola, Fantasia, Marinara, Vegetaria
***/
/*** 4. ***/
SELECT
Pizza#
,PizzaName
,COUNT(*) AS #Toppings
,SUM(CASE WHEN Topping IN ('olives', 'capers') THEN 1 ELSE 0 END) AS #Optional
FROM PizzaView
GROUP BY 1,2
HAVING
SUM(CASE WHEN Topping IN ('tomatoes', 'mozzarella') THEN 1 ELSE 0 END) = 2
AND
#Optional >= 1
ORDER BY 4 DESC
;
/***
5. Return all pizzas which are a superset of the searched toppings.
*At least* toppings ('tomatoes' and 'olives') and maybe additional toppings, but no 'capers'
Marinara, Vegetaria
***/
/*** 5. ***/
SELECT
Pizza#
,PizzaName
,COUNT(*) AS #Toppings
FROM
PizzaView
GROUP BY 1,2
HAVING
SUM(CASE
WHEN Topping IN ('tomatoes', 'olives') THEN 1
WHEN Topping IN ('capers') THEN -1
ELSE 0
END) = 2
ORDER BY #Toppings DESC
;
/*** Instead of a list of toppings a table with searched toppings
***/
CREATE SET TABLE searched
(grp INTEGER NOT NULL,
topping VARCHAR(30) NOT NULL
);
DELETE FROM searched;
INSERT INTO searched VALUES(1,'tomatoes');
INSERT INTO searched VALUES(1,'mozzarella');
INSERT INTO searched VALUES(1,'salami');
/*** 1. ***/
SELECT
Pizza#
,PizzaName
,COUNT(*) AS #Toppings
FROM
PizzaView p
JOIN searched g
ON p.Topping = g.Topping
GROUP BY 1,2
HAVING
COUNT(*) = (SELECT COUNT(*) FROM searched)
;
/*** 2. ***/
SELECT
Pizza#
,PizzaName
,COUNT(*) AS #Toppings
FROM
PizzaView p
LEFT JOIN searched g
ON p.Topping = g.Topping
GROUP BY 1,2
HAVING
COUNT(*) = COUNT(g.Topping)
;
/*** 3. ***/
SELECT
Pizza#
,PizzaName
,COUNT(*) AS #Toppings
FROM
PizzaView p
LEFT JOIN searched g
ON p.Topping = g.Topping
GROUP BY 1,2
HAVING
SUM(CASE WHEN g.Topping IS NOT NULL THEN 1 ELSE -1 END)
= (SELECT COUNT(*) FROM searched)
;
我从来不需要对搜索的表做#4/#5,但是使用上面的逻辑应该是可能的。
https://stackoverflow.com/questions/21519140
复制相似问题