关系代数中除法的SQL实现
[TOC]
引言
关系代数中的运算主要有选择、投影、连接（或者说乘法，即笛卡尔积）、除法，以及集合运算。其中，选择、投影、连接能直接用SQL表达，但除法和大部分集合运算不能。尤其是除法的缺失，使得涉及该操作的查询难以编写。本文将介绍用如何现有SQL实现除法，并分析困难产生的原因。
除法
笛卡尔积的逆
关系除法可以看作笛卡尔积的逆，即对于，其结果为所有满足
的
中最大的那个，有
可以将该结论表达为SQL以实现除法吗？在不支持
MINUS,EXCEPT的数据库中不能。由于R至少有两列，用NOT EXISTS实现MINUS并不简单。
SQL实现
应用场景举例
假设如下关系，
人与技能
| person | skill |
|---|---|
| 张大仙 | LOL |
| 殷子 | 笑 |
| 卫小妹 | CV |
| 成少 | LOL |
| 孙文涛 | Java |
| 张大仙 | 打剑 |
| 张大仙 | 机器学习 |
| 成少 | 机器学习 |
| 卫小妹 | 笑 |
需求的技能
| skill |
|---|
| LOL |
| 机器学习 |
要求：找出PersonSkill中会Skill中所有技能的人。
这是一个典型的关系除法问题，将问题翻译成关系代数语言，即
如何用SQL实现关系除法？
集合谓词的缺席
结合上述实际问题，一种自然的想法是：当一个人的所有技能包含需求的技能时，这个人被选中。试翻译为SQL，
SELECT person
FROM PersonSkill AS PS
GROUP BY person
HAVING PS.skill CONTAINS SKill
可惜这不是一段可以执行的SQL，因为目前SQL不支持集合层面的包含关系判定。
经过观察不难发现，当前SQL支持的所有真假判断（谓词）都定义在元组层面上，这迫使我们将PersonSkill中的person看作分散的个体，每个元组依次独立做出判断。然而，这作用在单个元组上的判断又必须考虑与其同名的其他元组，这让子查询的使用成为必然。最后，由于使某元组为真的谓词必定使其同名元组为真，需要加DISTINCT去重。
综合上述思考，调整SQL语句框架为
SELECT DISTINCT person
FROM PersonSkill AS PS
WHERE <某关于PS.person的谓词(子查询)>
实现减法
我们现在要实现这样一个子查询，根据某人的姓名判断其技能是否满足需求。还是按照最自然的思路，判断某人的技能集是否包含需求集。
取出某人技能集的SQL
SELECT skill
FROM PersonSkill
WHERE person = 某人
需求集
SELECT skill
FROM Skill
记技能集为A，需求集为B，等价于
又等价于
翻译为SQL
NOT EXISTS (
SELECT * FROM Skill AS S
WHERE S.skill NOT IN (
SELECT skill FROM PersonSkill AS PS
WHERE PS.person = 某人
)
)
也可以看作对等价式的判断，其中
NOT EXISTS判定空集，NOT IN实现集合差。
遗憾的是，
NOT IN实现集合差只对单列表有效
等价的双EXISTS版本
NOT EXISTS (
SELECT * FROM Skill AS S
WHERE NOT EXISTS (
SELECT * FROM PersonSkill AS PS -- 选A中对应S.skill的元组
WHERE PS.person = 某人 AND -- 某人的技能集A中的一个技能
PS.skill = S.skill -- 和需求集B中的一个技能相同
)
)
这段SQL可以理解为，“不存在B中有一行且A没有行与之对应的情况”，可以算是的直接SQL表述。
双EXISTS版本非常不好理解，原因还是在于我们只能用元组层面的谓词构造集合层面的结论。但如果做差的表不止一列，只能使用双EXISTS版本。
实现除法
综合上述讨论，
SELECT DISTINCT person
FROM PersonSkill AS PS1
WHERE NOT EXISTS (
SELECT * FROM Skill AS S -- WHERE
WHERE NOT EXISTS (
SELECT skill FROM PersonSkill AS PS2
WHERE PS2.person = PS1.person AND
PS2.skill = S.skill
)
);
有时，做“除数”的表（本例中的Skill）也是筛选得出的，这种情况可以在上述SQL的注释处添加选择条件。
附录
实验用SQL
CREATE TABLE PersonSkill (
person VARCHAR(10) NOT NULL,
skill VARCHAR(20) NOT NULL,
PRIMARY KEY (person, skill)
);
INSERT INTO PersonSkill
VALUES ('张大仙', 'LOL'), ('殷子', '笑'), ('卫小妹', 'CV'),
('成少', 'LOL'), ('孙文涛', 'Java'), ('张大仙', '打剑'),
('张大仙', '机器学习'), ('成少', '机器学习'), ('卫小妹', '笑');
CREATE TABLE Skill (
skill VARCHAR(20) NOT NULL,
PRIMARY KEY (skill)
);
INSERT INTO Skill
VALUES ('LOL'), ('机器学习');
SELECT DISTINCT person
FROM PersonSkill AS PS1
WHERE NOT EXISTS (
SELECT * FROM Skill AS S -- WHERE
WHERE NOT EXISTS (
SELECT skill FROM PersonSkill AS PS2
WHERE PS2.person = PS1.person AND
PS2.skill = S.skill
)
);
结果为张大仙、成少。
