形式陈述
查询及其集合语义
在关系演算理路关系演算Relational calculus · Domain relational calculus用一阶公式的满足条件定义关系查询,并以域独立性区分仅依赖数据库事实的查询与依赖外部论域的公式。中,本页的合取查询取如下形式:
每个项是变量或常量,没有函数项; 列出互异的输出变量, 列出其余变量。每个使用的变量都出现在至少一个正关系原子中,特别是每个输出变量必须如此。正文先讨论这个不另加等式原子的片段:没有析取、否定、全称量词或不等式;同一变量重复出现本身已经要求相应位置取相同值。
答案 属于 ,当且仅当存在给 的赋值,使每个关系原子同时成为输入表中的一条事实。见证可以有多个,结果仍按集合计一次。若 为空,得到布尔查询,其答案是真关系 或假关系 。允许空合取时,它仅给出无变量的恒真查询。
所有变量都由关系事实约束,因此成功匹配不依赖未使用的外部论域值。这给出合取查询域独立性的直接证明,不需要为每次求值另行枚举无限宇宙。
查询包含、同态与规范数据库
以下固定同一有限关系模式,实例中的每张表都是有限元组集合,且不另加键或其他依赖约束。比较的两个查询具有相同输出元数,输出坐标按同一次序比较;常量表示固定且互异的值。写 ,表示对每个这样的有限实例 ,都有 。这里允许所有包含输入值和两查询常量的非空外部论域,包括加入足够多新值后的论域;不能把量化范围限制在一个预先锁死的小有限论域上。
记 为查询的关系原子集合, 为有序输出变量元组。一个同态 把 的变量映到 的变量或常量,并在常量上扩展为恒等映射。它必须满足两个条件:每个 原子经 替换后都是 的原子; 逐坐标成立。不同变量可以映到同一个项,不同原子也可以映到同一个原子;没有单射或满射要求。
构造 的规范数据库 时,为每个变量 取一个新数据值 。这些新值两两不同,并避开两查询的所有常量。把每个原子中的变量替换成对应新值,常量保持原值,所得事实组成 ;没有出现的关系取空表。冻结后的输出元组记为 。外部论域还应包含 的常量,即使这些值没有出现在 的事实中。若冻结值与两查询常量构成的集合为空,则另取一个值保持论域非空;布尔头冻结后仍是 。
合取查询包含定理。 对上述纯合取查询,以下三件事等价:
所以,包含方向是从 到 ,验证它的同态却从 到 。查询等价要求两个包含方向都成立,因而需要两个方向的同态。这个有限判据及其证明见 Koutris 的 CS838 Spring 2016 Lecture 2,Theorem 2.7。
例子与边界
从问题到规则、连接与答案
问题是“找出学生及其所选课程的授课教师”。取三行选课表与三行授课表:
其公式和规则分别写为
箭头表示右侧事实成立便产生左侧答案,不是给表增加一条约束。关系代数理路关系代数Relational algebra · Set relational algebra用选择、投影、积、重命名与集合运算组合有限关系查询,并在集合语义下解释连接和存在见证。实现为 。连接的五个见证元组依次是甲—算法—林、甲—数据库—林、甲—数据库—周、乙—数据库—林、乙—数据库—周。投影后四个答案为甲—林、甲—周、乙—林、乙—周。
甲—林既可用算法作见证,也可用数据库作见证。若只问周的学生,得到甲、乙;从 Teach 删除数据库—周后,这个答案变为空。反之,只扩大未使用的外部论域,答案不变。
非递归查询中删除一条见证后,可以重新检查其他输入见证;若派生关系递归引用自身,局部“仍有支持”却可能只剩循环引用。删除与重推理路删除与重推Delete and rederive · DRed · 删除与重新推导在固定正 Datalog 程序下先沿旧推导过删,再从幸存证据重推,正确维护含递归与替代证明的最小模型,并排除循环自我支持。给出准确的集合维护接口:删除 EDB 事实,先过删所有受影响结论,再从幸存事实重建;同一可达性例子既恢复替代路径,也排除没有输入起点的循环支持。它不把删除一个证明等同于删除仍有其他证明的答案。
这条规则只读取给定的输入表。Datalog 与有限最小不动点理路Datalog 与有限最小不动点Datalog · Positive Datalog · Datalog least model在固定有限活跃域上反复应用正规则,证明所得关系是最小模型,并用有环可达性逐轮推导半朴素求值。进一步允许规则体使用规则自己定义的关系:反复加入新答案,直到关系闭合。正体匹配的含义不变,但递归答案必须由最小模型确定,不能只执行一轮查询。
为什么代数实现对所有实例成立
若 在投影结果中,就存在一个连接元组 ;连接的定义给出 和 ,因此 满足公式。反过来,公式的任何见证 都提供两条可连接的输入事实,组成 ,投影产生 。两个方向都不依赖示例中的具体名字或行数,所以证明适用于该模式的所有实例。
不同变量不表示不同对象
对单自环关系 ,布尔查询 为真,见证就是 。若业务要求两个不同节点,需要写出 ,但这已扩展了本页的纯合取查询语言。重复变量 则直接要求自环,无需额外等式原子。
加入显式等式原子时,可以合并被等式识别的变量、把与常量相等的变量替换掉,但还必须保持输出有范围;两个不同常量被要求相等时,查询恒空。这类扩展不能悄悄混入不含等式的定义。析取得到合取查询的并,否定引入差集式条件,也都超出了本页片段。
同一查询对:合并中点证明包含
在同一个二元关系 上,比较下面两个二元输出查询。 要求中点具有自环, 要求一条普通的三步游走;“游走”允许重复节点。
先判定 。所需方向为 ,取
三个原子的像依次是 、、,头 的像为 。所有条件都满足,因此包含成立。两边都有三个原子,不能靠比较条件数量得到这个结论;关键是允许把 合并为 。
再用规范测试核对:冻结 为互异的新值 ,得到
取 就返回 。进一步算出全部答案: 的中点只能为 ,起点可以是 ,终点可以是 ; 的两个中点也都只能为 。因此
这四对答案相同只核验了一份实例;全实例包含仍由同态及后面的证明保证。
反向失败:用同一查询对构造反例
若要证明 ,就需要 的同态。但 的像必然仍为自环原子,而 的原子中没有自环,故这种同态不存在。这里的理由排除了所有候选映射,而不只是某次尝试失败。
冻结 的 为四个互异新值 :
这条链唯一的三步游走从 到 ,所以 。链上没有自环,。于是 和 给出了反向包含的具体有限反例,也说明前一份实例上答案相同不足以推出查询等价。
迁移题:中点成为常量以后
把中点的一部分位置改成固定常量 :
仍有 :取 ,并保持 ,即可逐原子、逐头坐标验证。反向仍失败:取 ,其中 互异; 恰返回 , 因缺少 而为空。不能移动常量 来修复失败,因为两个查询中的 始终指同一个固定值。
集合见证不能代替重复次数
取 和 。将 合并给出一个方向的同态,选择其中一个原子给出另一方向,所以它们在集合语义下等价。但令 ,每条输入事实只出现一次,不去重的投影为 输出两次 ,为 输出四次 :后者的 有 四种选择。包含定理保存“存在见证”,没有保存见证的数量,不能据此直接证明 bag 语义下的等价改写。
查询来源与半环标注理路查询来源与半环标注Query provenance · Provenance semiring · K-relation · 查询溯源用有限支撑的半环标注关系记录查询见证,证明来源多项式的通用求值性质,并计算重数、事实删除与最小见证击中集。进一步给每条输入事实一个符号,用乘法记录同一见证使用的事实,用加法保留替代见证。它复用本页的六条选课与授课事实,为甲—林得到 ,并计算删除授课事实后哪些答案仍有支持。多项式保留重复原子的出现次数、同一事实的复用幂次与推导重数,所以本页把查询体视为原子集合的约定只直接适用于集合语义。
依赖约束改变了允许实例
若只比较满足约束集合 的实例,就应写 。例如 与 在约束 下等价;然而 的原规范实例只有 ,没有 ,它本身违反约束,不能充当合法反例。
本例补上 就满足约束。依赖追赶与通用模型理路依赖追赶与通用模型Dependency chase · Restricted chase · TGD and EGD chase · Universal model用活跃触发补入存在见证并全局合并等式,证明有限成功追赶的通用同态性质及合取查询的常量确定答案判据。进一步处理需要新存在见证的 TGD 和强制等式的 EGD:它用四步例子完成见证生成、全局合并与结论补入,并证明有限成功结果可通过同态映到每个合法补全,从而决定纯合取查询的常量确定答案。一般 chase 仍可能不终止;这并未把无约束包含定理扩写成保证返回的一般约束判定程序。有限实例语义的边界可对照 Pieris 的 ATFD 2018/19 Lecture 3,PDF 第 10–11、18 页。
只含函数依赖时,可以采用一个更受限且保证终止的等式过程。函数依赖的追赶检验理路函数依赖的追赶检验FD chase · Lossless join chase test在固定符号表中全局合并被函数依赖强制相等的值,以全标记行证明无损,以终止表构造合法有损反例。不生成新事实,而在固定表中合并被依赖强制相同的符号;每次有效合并减少符号类数。针对投影分解,它用全标记行证明无损,用无成功行的终止表构造满足约束的反例。这保留了规范数据库“把符号冻结成证据”的思想,却先修复了原符号表可能违反约束的问题;其终止证明不覆盖上面的事实生成依赖。
推论与应用
为什么反向同态恰好刻画包含
先证明有同态就有包含。取任意允许实例 、任意 ,并取产生它的成功赋值 ;把 在常量上也看成恒等映射。给 使用函数复合理路函数复合Function composition · Composition of maps按先 f 后 g 的次序把映射串联为 g∘f。 。对其任意原子 ,同态条件保证 是 原子,成功赋值又保证 是 的事实。因此 满足 的全部原子,并且
所以 。这也解释方向为什么不能颠倒:已知的是 的见证,需要先把 的项送入 ,才能复用这份见证。
再证明包含蕴含规范测试。冻结赋值本身满足 的所有原子,所以 。 是一份允许的有限实例,由包含立即得到 。
最后证明规范测试产生同态。设 是 在 上返回 的赋值。每个变量都出现在正关系原子中,因此它的成功取值一定出现在某条 事实里,只可能是一个冻结值或 的常量值。定义解冻映射 :把 还原为 的变量 ,保持所有常量不变。新值互异且避开常量,保证解冻不会混淆这两类项。
令 。对 的每个原子,它经 得到的事实属于 ,而 的事实恰由 原子冻结得到,解冻后便是 原子。常量保持不变,且 给出 。故 满足全部要求。若 没有变量,变量映射为空,同样逐原子检查;空合取的布尔恒真查询也包含在这一步内。
改写与单调性
合取查询具有单调性:只向输入关系增加元组时,已有见证不会消失,所以旧答案仍成立。带否定的查询一般没有这一性质,例如增加 会让 丢掉答案 。这既是表达能力边界,也是检查业务问题是否需要否定的线索。
匹配可以用连接次序与投影位置来组织;改写时必须保留后续匹配需要的共享变量,不能先丢掉课程再做任意配对。包含定理提供了集合语义下的改写证书:两个方向各给一个同态,就证明改写对所有有限实例保持答案;失败时,相应的规范数据库给出反例。
求值和包含是不同的判定问题
联合求值复杂度把查询 与数据库 都作为输入,问布尔查询是否为真,或给定元组是否属于答案。它是 NP 完全的:猜出所有变量的取值,再逐原子检查,是多项式证书。Chandra 与 Merlin 原文 §4 Theorem 7 讨论的就是这种求值问题。
固定查询的数据复杂度只让 及待测答案增长。此时变量数是常数,枚举赋值的数量是数据规模的固定次幂,因此有多项式时间算法。标准有限关系特征位编码下,判定甚至在 :每个候选赋值对应一组输入事实位的 AND,再把这些结果 OR 起来,得到常数深度、多项式规模电路。这里说的是布尔或成员判定,不是恒定时间输出整张结果表;参见 CS784 Spring 2021 Lecture 3,§3.2、Theorem 3.9。
查询包含的输入只有 ,没有待求值数据库。它也是 NP 完全的:证书是 ,每个变量的像、原子的像与头坐标都能在多项式时间内检查。NP 难性可由无向图三着色看出:令固定布尔查询 使用三个变量 ,包含全部六个 原子,其中 ;对输入图 ,令布尔查询 为每条无向边写两个方向的原子,孤立点可略去。则 当且仅当存在 的同态,恰当于给图的节点分配三种颜色并要求邻点异色。目标是含六条有向弧、没有自环的完全图;三个单向环边不能代替它。
若固定查询并要求枚举全部完整见证,问题还包括输出规模与中间结果成本。最坏情形最优连接理路最坏情形最优连接Worst-case optimal joins · WCOJ从AGM熵界到一般NPRR锚关系递归,完整核算三角形和四三元表实例的枚举与索引成本。用属性超图的分数边覆盖证明最大输出规模,并通过三角形的重轻分解避免先物化巨大的二元连接。这是枚举算法的保证,与上面的成员判定、查询包含不是同一个复杂度问题。