形式陈述
给定关系数据模型理路关系数据模型Relational model · Relational database model用模式规定关系的列,用有限元组集合表示数据库状态,并区分实际出现的值与外部论域。中的有限实例 ,以及包含输入值和查询常量的非空论域 ,域关系演算查询写作
这里输出变量 互异,并包含公式的全部自由变量;公式只使用输入关系、等式、常量、逻辑联结词与对象量词,不使用函数符号。满足关系理路满足关系Satisfaction relation · Tarski semantics用对公式构造的递归定义刻画结构与赋值何时满足一阶公式。说明如何在结构中逐层解释它;尤其 遍历的是所声明的论域。各常量指固定且互异的值。
固定查询后,若对每个有限实例及每次论域扩张 ,保持输入关系和常量解释不变都有
则称查询域独立。这是语义条件,而不是公式的一种外观。本文与关系代数的等价关系只指这个域独立片段;代数一侧采用有限集合语义,允许查询常量组成的有限常量关系、空关系和零列单位。等价表示每个查询都能翻译成另一语言中在所有实例上同答案的查询。
另一种约定是活跃域求值:令 ,将所有自由变量取值及量词范围限制到 。它直接规定了一套有限求值规则;对任意公式这样求值,并不能证明该公式按原来的外部论域语义也是域独立的。
直觉
查询写出“什么条件算一个答案”,求值器寻找满足条件的元组。学生—教师查询是
是要交给用户的两个值; 是内部证据,只要存在一个即可。这个公式的每个成功取值都能追溯到输入行,加入无关对象不能增加证据。
否定本身不是问题。 从 已有成员中排除 的成员,等于有限差集。真正需要追问的是:候选对象来自哪里,量词会不会借助表外对象改变真值?
例子与边界
自由变量没有范围
令 ,公式 在 上没有答案,在 上返回 。表没有变化,答案却变化,所以它不是域独立查询。在无限外部论域上,答案还可能无限;把量词限制到活跃域得到空答案,只是换了语义。
只限制输出变量仍然不够
令 ,考虑
虽然 明确来自 ,但在 上不存在不属于 的 ,答案为空;扩张为 后可取 ,答案变成 。因此检查自由变量有无正关系原子,不能代替检查被量化变量的范围。
一种安全的改写是 :现在见证必须来自输入表 ,新增未使用的论域元素不起作用。不过这改变了问题,需要业务确实提供候选表 ,不能称为对原公式无条件等价的修补。
安全句法、语义安全与空活跃域
文献中的 safe-range 条件是一套可机械检查的充分句法规则;满足规则的查询域独立,但任意域独立公式未必已经写成该规则接受的形式。表达能力定理允许先翻译成安全形式,不能倒过来说只看“每个变量在某处出现”便得到完整判定。析取分支、否定内部与量词作用域都必须纳入规则。
空活跃域特别容易暴露约定差异。没有输入值或常量时,一阶句子 在每个非空外部论域上都为真,因而域独立;若机械地把量词范围改成空活跃域,它却为假。零列真答案必须用 保存,不能因“没有可枚举值”而丢掉。
推论与应用
等价翻译的两条方向
关系代数理路关系代数Relational algebra · Set relational algebra用选择、投影、积、重命名与集合运算组合有限关系查询,并在集合语义下解释连接和存在见证。到演算按表达式结构归纳:连接对应共享变量的合取,投影对应存在量词,并对应析取,差 对应 。左边 已给出有限候选,常量表则翻译为相应等式。每一步都保持列接口和答案。
反方向在 时,先把所有输入列投影、重命名并求并,再加入查询常量单列表,构造一元关系 。对含 个待赋值变量的子公式, 给出候选元组;原子式用选择和连接,否定用相对于 的差,存在量词用投影。只有当原查询域独立,才可把这一有限求值与原来的外部论域求值等同。
时,所有正元输入关系均为空,查询中也没有常量,但零元输入关系仍可能为真。保持这些零元事实不变,先取两个不同的值 。域独立性给出
若输出元数 ,两端分别包含于 与 ,而这两个元组集合不相交,因此三个答案都为空。对任意非空论域 ,再经共同扩张 比较,得到
这才说明任意论域上的正元输出都只能为空,包括候选元组含有多个不同坐标值的情形。零元输出则可能为真;可在一个辅助单元素论域上评价句子,按输入零元关系的真假生成相应的有限布尔组合,再用 表示。辅助元素只用于翻译证明,不会成为输出常量。以 判断非空分支、以 判断空分支,可以把两种情况合成一个代数表达式。
这说明等价定理需要的是明确的语义约定,不能把“遍历活跃域”当作适用于所有公式和边界的口号。合取查询理路合取查询Conjunctive query · CQ · Select-project-join query用关系事实的匹配定义集合答案,并以规范数据库与反向同态判定所有有限实例上的查询包含。提供一个更直接的安全片段:所有使用的变量都通过正关系事实获得见证。在这个片段中,还可以冻结查询变量构造规范数据库,用另一查询是否返回冻结头元组来判定全实例包含;成功赋值解冻后就是反向同态。这一判据依赖正关系原子的结构,不能由演算与代数等价直接推广到任意含否定的公式。
对涉及并发读的应用,还要由事务理路数据库事务Database transaction · Transaction以 begin 与 commit 或 abort 划定的一次逻辑状态变换,把多项读写作为共同成功或放弃的工作单位。与隔离语义确定本次公式究竟在哪个实例上求值。
参考资料