Skip to content

模型Model

关系数据模型

施工中 · 内容逐步修订

Relational model · Relational database model

用模式规定关系的列,用有限元组集合表示数据库状态,并区分实际出现的值与外部论域。

形式陈述 ​

固定一个非空的共同值论域 D。一个关系模式 S 是有限组关系符号及其列名,例如 Enroll(Student,Course)。每个符号的列名互异,并固定它们与各坐标的对应;列数称为元数。一个数据库实例 I 为每个 n 元符号 R 指定一个有限集合 RI⊆Dn;Dn 是由 n 个坐标构成的笛卡尔积。列名帮助识别坐标,展示时的行顺序不属于实例。

本文使用共同论域而不另设学生、课程等类型;业务类型可以由模式附加约束,但不由列名自动推出。实例采用集合语义:同一元组出现两次仍只是一条事实,不含 SQL 的 NULL、重复行或隐含排序。这里使用关系条目中的有类型有限元接口,把每个坐标的声明类型都取为共同论域 D,再要求关系图为有限子集。元数为二时得到二元关系,其他有限元数与零元情形也属于同一接口;不能只靠两列表的例子替代一般的 RI⊆Dn。

实例的活跃域 adom(I) 是所有输入关系的所有元组中实际出现的值。对于查询 q,还需要考虑其中常量的值:

AI,q=adom(I)∪Const(q).

本系列将常量当作固定值,不同常量名表示不同值。允许扩大的外部论域必须包含输入值与查询常量;它可以含有大量从未出现在表中的值。活跃域有限,不意味着外部论域只能取它。扩大 D 时保留原值和常量的解释,不把旧值重新编号成别的对象。

查询把给定模式上的实例映成一个给定输出列集合上的关系。零列关系也有意义:D0={()},所以零列结果只有 ∅ 和 {()} 两种,分别编码布尔查询的假和真。

直觉

模式回答“这一列代表什么位置”,实例回答“此刻哪些事实成立”,查询回答“从这些事实能找出哪些答案”。例如选课表中一行 (甲,算法) 只表示甲选了算法,不表示甲只能选算法,更不表示表里已经列完所有可能的学生。

把关系当集合让查询的意义独立于存储方式。数据库可以扫描磁盘页、走索引或并行处理,只要给出相同的结果集合,就实现了同一个查询。计算速度、并发时看见哪个实例、崩溃后保留哪个实例,都是需要另外说明的问题。

例子与边界

两张表与六个实际值 ​

沿用二元关系条目的选课例子:

Student Course
甲 算法
甲 数据库
乙 数据库

上表是 Enroll;授课表 Teach 为:

Course Teacher
算法 林
数据库 林
数据库 周

每张表恰有三个元组,而活跃域有六个值:甲、乙、算法、数据库、林、周。问“每个学生能通过选修的课程联系到哪些教师”,输出模式只有 Student、Teacher 两列;课程仍参与判断,却不必出现在答案里。

向外部论域加入从未出现的“丙”,并不插入选课行,也不改变活跃域。一个仅根据现有选课与授课事实寻找见证的查询,答案因此不会改变。相反,“找出论域中未选课的所有值”会依赖论域范围;这正是关系演算需要处理的边界。

表的约束不能从外观猜测 ​

甲出现两次不违反关系模型,也不违反尚未声明的“学生主键”。只有另行声明 Student 为键,才要求同一学生不能对应两个不同 Course 值。键约束是对允许实例的限制,不是每张表第一列的默认性质。

函数依赖与属性闭包把这类约束写成两行的一致性条件:相同 Student 必须有相同 Course,就写作 Student→Course。候选键则要求其属性决定整行,并且删掉任一属性后不再能保证这一点。依赖后承要求一条依赖在所有合法实例中成立,不能仅凭一张样本没有冲突便断言它成立。把本例放在包含这六个值的无限共同论域中,按该页约定核查:(甲,算法) 与 (甲,数据库) 在 Student 上相同、在 Course 上不同,故这张表不满足声明 Student→Course。后续闭包与分解定理也固定无限共同论域,以便构造有限反例;本页一般模型的定义仍只要求 D 非空。

这种区别也决定查询包含的含义:无约束包含要遍历所有有限集合实例,带约束包含只遍历满足声明的实例。例如声明 ∀x(P(x)→Q(x)) 后,只含 P(a) 而没有 Q(a) 的实例就不合法。合取查询的规范数据库判据会直接使用由查询原子组成的实例,因此必须先说明是否有这些额外约束,才能判断它是不是可用的反例。

空表同样合法。所有正元关系都为空、且查询没有常量时,AI,q 可以为空;外部一阶论域仍保持非空。零列真关系 {()} 中也没有任何值,因此它非空却不增加活跃域。必须分别判断“有没有元组”“有没有出现过的值”和“有没有允许量化的对象”。

自测:五个见证为何只给四个答案 ​

请列出选课与授课通过同一 Course 值接通的全部三元组,再删去 Course 列。五个见证是

W={(甲,算法,林),(甲,数据库,林),(甲,数据库,周),(乙,数据库,林),(乙,数据库,周)}.

输出只有 (甲,林),(甲,周),(乙,林),(乙,周) 四对。甲到林有两个课程见证,集合语义仍只保留同一个输出元组一次。这正是关系页二元复合的存在见证机制,不需先假设数据库如何存储或执行它。

先只把“丙”加入外部 D,输出不变。再向 Enroll 插入 (丙,算法),就新增一个见证和一个答案 (丙,林),得到六个见证、五个答案。两步的区别在于是否真的改变了实例,而非新值是否已经允许作为坐标。

最后把所有正元输入表清空,另保留一个零元真关系 {()}。此时活跃域仍为空;若查询写入常量“甲”,则 AI,q={甲},外部 D 必须包含它且非空。零元真关系有一条元组,却没有任何坐标值。请分别数出行数、出现值数和允许量化的对象,不能把这三个集合混在一起。

推论与应用

关系代数把查询写成具有明确输入、输出列的运算组合;关系演算把答案写成满足公式的元组。两者共用本页的有限集合实例,才能精确比较表达能力。

合取查询进一步提取“存在一组相互匹配的事实”这一常用片段,选课例子就属于它。数据库事务则划定一组读写共同提交或中止的边界:查询语义确定在一个实例上应返回什么,事务与隔离规则确定执行时应观察哪个状态。

最坏情形最优连接把这些有限集合实现为切片与前缀索引,展开一般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。
关系图谱29 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
类型化关系