知识卡片
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
很难表达的查询……单重否定已经够糟糕了……双重否定就更别提了。