形式陈述
固定一个非空的共同值论域 D 。一个关系模式 S 是有限组关系符号及其列名,例如 Enroll ( Student , Course ) 。每个符号的列名互异,并固定它们与各坐标的对应;列数称为元数。一个数据库实例 I 为每个 n 元符号 R 指定一个有限集合 理路 有限集 Finite set 与某个自然数初始段等势、因而能够在有限步内无遗漏编号的集合。 R I ⊆ D n ;D n 是由 n 个坐标构成的笛卡尔积 理路 笛卡尔积 Cartesian product · Direct product of sets 由各坐标分别取值形成的有序元组集合;二元情形记作 A×B。 。列名帮助识别坐标,展示时的行顺序不属于实例。
本文使用共同论域而不另设学生、课程等类型;业务类型可以由模式附加约束,但不由列名自动推出。实例采用集合语义:同一元组出现两次仍只是一条事实,不含 SQL 的 NULL、重复行或隐含排序。这里使用关系条目中的有类型有限元接口 理路 关系 Relation · Binary relation 带源集与目标集的二元关系,其底层关系图是 A×B 的子集。 ,把每个坐标的声明类型都取为共同论域 D ,再要求关系图为有限子集。元数为二时得到二元关系,其他有限元数与零元情形也属于同一接口;不能只靠两列表的例子替代一般的 R I ⊆ D n 。
实例的活跃域 adom ( I ) 是所有输入关系的所有元组中实际出现的值。对于查询 q ,还需要考虑其中常量的值:
A I , q = adom ( I ) ∪ Const ( q ) . 本系列将常量当作固定值,不同常量名表示不同值。允许扩大的外部论域必须包含输入值与查询常量;它可以含有大量从未出现在表中的值。活跃域有限,不意味着外部论域只能取它。扩大 D 时保留原值和常量的解释,不把旧值重新编号成别的对象。
查询把给定模式上的实例映成一个给定输出列集合上的关系。零列关系也有意义:D 0 = { ( ) } ,所以零列结果只有 ∅ 和 { ( ) } 两种,分别编码布尔查询的假和真。
直觉
模式回答“这一列代表什么位置”,实例回答“此刻哪些事实成立”,查询回答“从这些事实能找出哪些答案”。例如选课表中一行 甲 算 法 ( 甲 , 算法 ) 只表示甲选了算法,不表示甲只能选算法,更不表示表里已经列完所有可能的学生。
把关系当集合让查询的意义独立于存储方式。数据库可以扫描磁盘页、走索引或并行处理,只要给出相同的结果集合,就实现了同一个查询。计算速度、并发时看见哪个实例、崩溃后保留哪个实例,都是需要另外说明的问题。
例子与边界
两张表与六个实际值
沿用二元关系条目的选课例子:
Student
Course
甲
算法
甲
数据库
乙
数据库
上表是 Enroll ;授课表 Teach 为:
Course
Teacher
算法
林
数据库
林
数据库
周
每张表恰有三个元组,而活跃域有六个值:甲、乙、算法、数据库、林、周。问“每个学生能通过选修的课程联系到哪些教师”,输出模式只有 Student、Teacher 两列;课程仍参与判断,却不必出现在答案里。
向外部论域加入从未出现的“丙”,并不插入选课行,也不改变活跃域。一个仅根据现有选课与授课事实寻找见证的查询,答案因此不会改变。相反,“找出论域中未选课的所有值”会依赖论域范围;这正是关系演算需要处理的边界。
表的约束不能从外观猜测
甲出现两次不违反关系模型,也不违反尚未声明的“学生主键”。只有另行声明 Student 为键,才要求同一学生不能对应两个不同 Course 值。键约束是对允许实例的限制,不是每张表第一列的默认性质。
函数依赖与属性闭包 理路 函数依赖与属性闭包 Functional dependency · Attribute closure 从两行的一致性定义函数依赖,用固定点计算全部可决定属性,并以有限反模型证明闭包算法完备。 把这类约束写成两行的一致性条件:相同 Student 必须有相同 Course,就写作 Student → Course 。候选键则要求其属性决定整行,并且删掉任一属性后不再能保证这一点。依赖后承要求一条依赖在所有合法实例中成立,不能仅凭一张样本没有冲突便断言它成立。把本例放在包含这六个值的无限共同论域中,按该页约定核查:甲 算 法 ( 甲 , 算法 ) 与 甲 数 据 库 ( 甲 , 数据库 ) 在 Student 上相同、在 Course 上不同,故这张表不满足声明 Student → Course 。后续闭包与分解定理也固定无限共同论域,以便构造有限反例;本页一般模型的定义仍只要求 D 非空。
这种区别也决定查询包含的含义:无约束包含要遍历所有有限集合实例,带约束包含只遍历满足声明的实例。例如声明 ∀ x ( P ( x ) → Q ( x ) ) 后,只含 P ( a ) 而没有 Q ( a ) 的实例就不合法。合取查询的规范数据库判据 理路 合取查询 Conjunctive query · CQ · Select-project-join query 用关系事实的匹配定义集合答案,并以规范数据库与反向同态判定所有有限实例上的查询包含。 会直接使用由查询原子组成的实例,因此必须先说明是否有这些额外约束,才能判断它是不是可用的反例。
空表同样合法。所有正元关系都为空、且查询没有常量时,A I , q 可以为空;外部一阶论域仍保持非空。零列真关系 { ( ) } 中也没有任何值,因此它非空却不增加活跃域。必须分别判断“有没有元组”“有没有出现过的值”和“有没有允许量化的对象”。
自测:五个见证为何只给四个答案
请列出选课与授课通过同一 Course 值接通的全部三元组,再删去 Course 列。五个见证是
甲 算 法 林 甲 数 据 库 林 甲 数 据 库 周 乙 数 据 库 林 乙 数 据 库 周 W = { ( 甲 , 算法 , 林 ) , ( 甲 , 数据库 , 林 ) , ( 甲 , 数据库 , 周 ) , ( 乙 , 数据库 , 林 ) , ( 乙 , 数据库 , 周 ) } . 输出只有 甲 林 甲 周 乙 林 乙 周 ( 甲 , 林 ) , ( 甲 , 周 ) , ( 乙 , 林 ) , ( 乙 , 周 ) 四对。甲到林有两个课程见证,集合语义仍只保留同一个输出元组一次。这正是关系页二元复合的存在见证机制,不需先假设数据库如何存储或执行它。
先只把“丙”加入外部 D ,输出不变。再向 Enroll 插入 丙 算 法 ( 丙 , 算法 ) ,就新增一个见证和一个答案 丙 林 ( 丙 , 林 ) ,得到六个见证、五个答案。两步的区别在于是否真的改变了实例,而非新值是否已经允许作为坐标。
最后把所有正元输入表清空,另保留一个零元真关系 { ( ) } 。此时活跃域仍为空;若查询写入常量“甲”,则 甲 A I , q = { 甲 } ,外部 D 必须包含它且非空。零元真关系有一条元组,却没有任何坐标值。请分别数出行数、出现值数和允许量化的对象,不能把这三个集合混在一起。
推论与应用
关系代数 理路 关系代数 Relational algebra · Set relational algebra 用选择、投影、积、重命名与集合运算组合有限关系查询,并在集合语义下解释连接和存在见证。 把查询写成具有明确输入、输出列的运算组合;关系演算 理路 关系演算 Relational calculus · Domain relational calculus 用一阶公式的满足条件定义关系查询,并以域独立性区分仅依赖数据库事实的查询与依赖外部论域的公式。 把答案写成满足公式的元组。两者共用本页的有限集合实例,才能精确比较表达能力。
合取查询 理路 合取查询 Conjunctive query · CQ · Select-project-join query 用关系事实的匹配定义集合答案,并以规范数据库与反向同态判定所有有限实例上的查询包含。 进一步提取“存在一组相互匹配的事实”这一常用片段,选课例子就属于它。数据库事务 理路 数据库事务 Database transaction · Transaction 以 begin 与 commit 或 abort 划定的一次逻辑状态变换,把多项读写作为共同成功或放弃的工作单位。 则划定一组读写共同提交或中止的边界:查询语义确定在一个实例上应返回什么,事务与隔离规则确定执行时应观察哪个状态。
最坏情形最优连接 理路 最坏情形最优连接 Worst-case optimal joins · WCOJ 从AGM熵界到一般NPRR锚关系递归,完整核算三角形和四三元表实例的枚举与索引成本。 把这些有限集合实现为切片与前缀索引,展开一般NPRR锚关系递归。四张三元表的完整执行区分最终答案、枚举候选与二元中间结果;这些成本结论均使用集合语义。
参考资料
Serge Abiteboul、Richard Hull、Victor Vianu,Foundations of Databases ,作者官方第 3 章 ,Addison-Wesley,1995,§§3.1–3.3,印刷页 30–33:模式、列名/坐标、有限关系实例与空元组。该书固定可数无限共同值域;本页只在相应后续定理中采用这一更强约定,一般模型允许任意非空共同值域。
E. F. Codd,Relational Completeness of Data Base Sublanguages ,IBM Research Report RJ987,1972 年 3 月 6 日,§2.2–2.3 的一般关系及查询框架;其中 §2.3.2 对空投影列表另有约定,不能用它支持本页现代的零列空元组语义。后收入 Randall Rustin 编 Data Base Systems ,Prentice-Hall,1972,pp. 65–98。