關(guān)系代數(shù)中除法的SQL實(shí)現(xiàn)

[TOC]

引言

關(guān)系代數(shù)中的運(yùn)算主要有選擇、投影、連接（或者說(shuō)乘法，即笛卡爾積）、除法，以及集合運(yùn)算。其中，選擇、投影、連接能直接用SQL表達(dá)，但除法和大部分集合運(yùn)算不能。尤其是除法的缺失，使得涉及該操作的查詢難以編寫(xiě)。本文將介紹用如何現(xiàn)有SQL實(shí)現(xiàn)除法，并分析困難產(chǎn)生的原因。

除法

笛卡爾積的逆

關(guān)系除法可以看作笛卡爾積的逆，即對(duì)于，其結(jié)果為所有滿足的中最大的那個(gè)，有

可以將該結(jié)論表達(dá)為SQL以實(shí)現(xiàn)除法嗎？在不支持MINUS, EXCEPT的數(shù)據(jù)庫(kù)中不能。由于R至少有兩列，用NOT EXISTS實(shí)現(xiàn)MINUS并不簡(jiǎn)單。

SQL實(shí)現(xiàn)

應(yīng)用場(chǎng)景舉例

假設(shè)如下關(guān)系，

人與技能

需求的技能

要求：找出PersonSkill中會(huì)Skill中所有技能的人。

這是一個(gè)典型的關(guān)系除法問(wèn)題，將問(wèn)題翻譯成關(guān)系代數(shù)語(yǔ)言，即

如何用SQL實(shí)現(xiàn)關(guān)系除法？

集合謂詞的缺席

結(jié)合上述實(shí)際問(wèn)題，一種自然的想法是：當(dāng)一個(gè)人的所有技能包含需求的技能時(shí)，這個(gè)人被選中。試翻譯為SQL，

SELECT person
FROM PersonSkill AS PS
GROUP BY person
HAVING PS.skill CONTAINS SKill

可惜這不是一段可以執(zhí)行的SQL，因?yàn)槟壳癝QL不支持集合層面的包含關(guān)系判定。

經(jīng)過(guò)觀察不難發(fā)現(xiàn)，當(dāng)前SQL支持的所有真假判斷（謂詞）都定義在元組層面上，這迫使我們將PersonSkill中的person看作分散的個(gè)體，每個(gè)元組依次獨(dú)立做出判斷。然而，這作用在單個(gè)元組上的判斷又必須考慮與其同名的其他元組，這讓子查詢的使用成為必然。最后，由于使某元組為真的謂詞必定使其同名元組為真，需要加DISTINCT去重。

綜合上述思考，調(diào)整SQL語(yǔ)句框架為

SELECT DISTINCT person
FROM PersonSkill AS PS
WHERE <某關(guān)于PS.person的謂詞(子查詢)>

實(shí)現(xiàn)減法

我們現(xiàn)在要實(shí)現(xiàn)這樣一個(gè)子查詢，根據(jù)某人的姓名判斷其技能是否滿足需求。還是按照最自然的思路，判斷某人的技能集是否包含需求集。

取出某人技能集的SQL

SELECT skill
FROM PersonSkill
WHERE person = 某人

需求集

SELECT skill
FROM Skill

記技能集為A，需求集為B，等價(jià)于

又等價(jià)于

翻譯為SQL

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

也可以看作對(duì)等價(jià)式的判斷，其中NOT EXISTS判定空集，NOT IN實(shí)現(xiàn)集合差。

遺憾的是，NOT IN實(shí)現(xiàn)集合差只對(duì)單列表有效

等價(jià)的雙EXISTS版本

NOT EXISTS (
    SELECT * FROM Skill AS S
    WHERE NOT EXISTS (
        SELECT * FROM PersonSkill AS PS -- 選A中對(duì)應(yīng)S.skill的元組
        WHERE PS.person = 某人 AND   -- 某人的技能集A中的一個(gè)技能
              PS.skill = S.skill    -- 和需求集B中的一個(gè)技能相同
    )
)

這段SQL可以理解為，“不存在B中有一行且A沒(méi)有行與之對(duì)應(yīng)的情況”，可以算是的直接SQL表述。

雙EXISTS版本非常不好理解，原因還是在于我們只能用元組層面的謂詞構(gòu)造集合層面的結(jié)論。但如果做差的表不止一列，只能使用雙EXISTS版本。

實(shí)現(xiàn)除法

綜合上述討論，

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
    )
);

有時(shí)，做“除數(shù)”的表（本例中的Skill）也是篩選得出的，這種情況可以在上述SQL的注釋處添加選擇條件。

附錄

實(shí)驗(yàn)用SQL

CREATE TABLE PersonSkill (
    person VARCHAR(10) NOT NULL,
    skill VARCHAR(20) NOT NULL,
    PRIMARY KEY (person, skill)
);

INSERT INTO PersonSkill
VALUES ('張大仙', 'LOL'), ('殷子', '笑'), ('衛(wèi)小妹', 'CV'), 
('成少', 'LOL'), ('孫文濤', 'Java'), ('張大仙', '打劍'), 
('張大仙', '機(jī)器學(xué)習(xí)'), ('成少', '機(jī)器學(xué)習(xí)'), ('衛(wèi)小妹', '笑');

CREATE TABLE Skill (
    skill VARCHAR(20) NOT NULL,
    PRIMARY KEY (skill)
);

INSERT INTO Skill
VALUES ('LOL'), ('機(jī)器學(xué)習(xí)');

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
    )
);

結(jié)果為張大仙、成少。