Double Not Exists——SQL语言的一个经典问题

关系型数据库中，有一个经常出现的模式，就是集合A和集合B，通过一个关系集R，组成多对多的关系。

举个例子，我们有学生表

create table student(
    id serial primary key,
    name text
)

课程表

create table course(
    id serial primary key,
    name text
);

可以建立一个选课表

create table take_course (
    id serial primary key,
    std_id int reference student(id),
    course_id int reference course(id)
)

这里我省掉了几乎所有与问题无关的字段，并且关系表采用了比较平凡的形式，这仅仅是为了叙述方便。语法遵循了 PostgreSQL 的习惯，不过放到其它数据库平台也无需大的改动，核心的东西并不依赖任何具体的关系型数据库。

这个形式下，学生可以选0到多门课，每个课程也可以有0到多名学生。大部分相关的查询写起来不一定简单，但是都比较平凡，通过耐心的拼装Join操作都可以解决。

但是其中有一个经典问题，是比较不直观的。

简单的说，现在有集合 A 和B ，及其关系集 R 通过 R，我们可以找到 A 到 B 和 B到 A 的一对多关系，从而A B双方建立了多对多的关系（懒得写代数式了，抱歉啊各位(´･_･`)）。

那么，现在如果我们想要找到A集合中，映射到所有B元素的那些项，这个查询写起来远比看起来复杂。

举个具体的例子会更好理解，以{学生-选课-课程}这个关系来说，如果我们要查询选了所有课程的学生，该如何做？

子查询操作符 All？不，ALL不是这样用的，我们不能写一个 id = all(query) 来映射"A中映射到所有B"的项。

我们可以很容易构造出“存在映射关系”的元素，但是构造“映射到全集”的查询并不容易。

这个在《SQL-3参考指南》（二十多年前出自SQL标准委员会的一本书，现在已经找不到了）里，称为 Double Not Exists 问题。是通过逆向思维解决全匹配的。

也就是说，正面构造全集匹配很难，但是我们可以反过来，对任给的 a ∈ A，我们可以通过R查询 B 中是否有不关联 a 的元素，假设这个集合我们称为 E(a) ，那么 E(a) 为空集的元素a，就是我们需要找的。而这个关系，可以用两层嵌套的 Not Exists 相关子查询表示。例如选了所有课程的学生，就是满足“课程表中不存在该学生没有选的课程”这个条件的学生

select * 
from student
where not exists (
    select * 
    from course
    where not exists (
        select * 
        from take_course
        where student.id = std_id and course.id=course_id
    )
)

这是一个非常奇妙的“看起来很简单，解决起来很不直观”的问题，我跟范博士开玩笑说这可以算是 SQL 语言的水果方程问题

虽然它没有真的难到这个程度，仍然是一个相对比较简单（较真的话可以写出非常朴素的逻辑推导过程）的问题，但是程序员在工作中遇到这个问题，比数学家遇到伪装成香蕉菠萝的椭圆方程的可能性，要高很多。

多对多关系中的全匹配，其实有很多实用背景，例如我的一位经济学家朋友，就遇到过“寻找投标了所有项目的企业”这类风控问题——当然实际问题比这个复杂，不能直接基于这个查询处理。类似的还有我们刚才提到的，“选了所有课程的学生”，“购买过所有商品的顾客”，等等等等。

今天处理这个问题的时候，想起来在差不多十年前，我和《算法》的译者谢路云老师，在金山的同一个团队工作，当时我们在工作中就遇到了这样的一个查询问题，在办公楼下讨论过如何用 Double Not Exists 查询解决。有些感慨，记录一下。