关系代数中除法的SQL实现

文章目录

• 关系代数中除法的SQL实现
• 引言
• 除法
• 笛卡尔积的逆
• SQL实现
• 应用场景举例
• 集合谓词的缺席
• 实现减法
• 实现除法
• 附录
• 实验用SQL

引言

关系代数中的运算主要有选择、投影、连接（或者说乘法，即笛卡尔积）、除法，以及集合运算。其中，选择、投影、连接能直接用SQL表达，但除法和大部分集合运算不能。尤其是除法的缺失，使得涉及该操作的查询难以编写。本文将介绍用如何现有SQL实现除法，并分析困难产生的原因。

除法

笛卡尔积的逆

关系除法可以看作笛卡尔积的逆，即对于$R\div S$R÷S，其结果为所有满足$T\times S\subseteq R$T×S⊆R的$T$T中最大的那个，有
$T=\pi(R)-\pi((\pi(R)\times S)-R)$T=π(R)−π((π(R)×S)−R)

可以将该结论表达为SQL以实现除法吗？在不支持MINUS, EXCEPT的数据库中不能。由于R至少有两列，用NOT EXISTS实现MINUS并不简单。

SQL实现

应用场景举例

假设如下关系，

人与技能

person	skill
张大仙	LOL
殷子	笑
卫小妹	CV
成少	LOL
孙文涛	Java
张大仙	打剑
张大仙	机器学习
成少	机器学习
卫小妹	笑

需求的技能

skill
LOL
机器学习

要求：找出PersonSkill中会Skill中所有技能的人。

这是一个典型的关系除法问题，将问题翻译成关系代数语言，即
$PersionSkill\div Skill$PersionSkill÷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，$B\subseteq A$B⊆A等价于
$\forall x\in B\rightarrow x\in A$∀x∈B→x∈A
又等价于
KaTeX parse error: Undefined control sequence: \and at position 17: …!\exists x\in B\̲a̲n̲d̲ ̲x\notin A
翻译为SQL

NOT EXISTS (
    SELECT * FROM Skill AS S
    WHERE S.skill NOT IN (
        SELECT skill FROM PersonSkill AS PS
        WHERE PS.person = 某人
    )
)

也可以看作对等价式$B-A=\empty$B−A=∅的判断，其中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没有行与之对应的情况”，可以算是KaTeX parse error: Undefined control sequence: \and at position 16: !\exists x\in B\̲a̲n̲d̲ ̲x\notin 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
    )
);

结果为张大仙、成少。