关系代数中除法的SQL实现

关系代数中除法的SQL实现

文章目录

引言

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

除法

笛卡尔积的逆

关系除法可以看作笛卡尔积的逆,即对于R÷SR\div SR÷S,其结果为所有满足T×SRT\times S\subseteq RT×S⊆R的TTT中最大的那个,有
T=π(R)π((π(R)×S)R) 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÷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,BAB\subseteq AB⊆A等价于
xBxA \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 = 某人
    )
)

也可以看作对等价式BA=B-A=\emptyB−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
    )
);

结果为张大仙、成少。

上一篇:shell for 循环演示


下一篇:C#文本解析