知识卡片

FORALL和EXISTS可以互相定义,SQL缺FORALL导致双重否定困境

普通读书笔记卡

内容

EXISTS x(p(x))逻辑等价于NOT(FORALL x(NOT(p(x)))),反之 FORALL x(p(x))逻辑等价于NOT(EXISTS x(NOT(p(x))))——这说明一个形式化 语言理论上不需要同时显式支持EXISTS和FORALL,用其中一个加NOT就能表达另一个。 但实践中同时支持两者仍然很有价值,因为不同问题用不同量词表述往往”自然 程度”差异巨大:SQL只支持EXISTS、不支持FORALL,导致某些用FORALL天然表达的 查询在SQL里必须靠双重否定绕出来。经典例子是”获得供应所有零件型号的供应商” ——关系演算写法直接明了:{SX}WHERE FORALL PX(EXISTS SPX(SPX.SNO=SX.SNO AND SPX.PNO=PX.PNO));但对应的SQL必须先把FORALL改写成 NOT(EXISTS...NOT EXISTS...)的双重否定结构: WHERE NOT EXISTS(SELECT * FROM P AS PX WHERE NOT EXISTS(SELECT * FROM SP AS SPX WHERE SX.SNO=SPX.SNO AND SPX.PNO=PX.PNO))——书中直言”单重否定 已经够糟糕了,双重否定就更别提了”,这类嵌套双重NOT EXISTS结构公认是SQL里 最难正确写出、也最难正确读懂的查询模式之一,根源正是SQL在设计之初选择只 支持EXISTS而放弃了FORALL这个理论上完全可以互相替代、但在实际书写体验上 差异巨大的对偶量词。

参考来源

- 位置:《SQL与关系数据库理论——如何编写健壮的SQL代码》第10章"SQL与逻辑" 10.6.1节"不必同时使用两个量词"(源文件:OEBPS/text00114.html) - 结论依据:原文明确"谓词EXISTS x(p(x))实际逻辑等价于谓词NOT(FORALL x(NOT(p(x))))……我们都知道SQL支持EXISTS但不支持FORALL,因此,会 存在某些用SQL很难表达的查询……单重否定已经够糟糕了……双重否定就更别提了 (就像本例一样)"。 - 原始内容:谓词EXISTS x(p(x))实际逻辑等价于谓词NOT(FORALL x(NOT (p(x))))……SQL支持EXISTS但不支持FORALL,因此,会存在某些用SQL 很难表达的查询……单重否定已经够糟糕了……双重否定就更别提了。