袋鼠知识

主题

第二章 关系数据库基础与关系代数 ​

📖 ⏱️ 预计阅读时长

1. 关系模型的数学基础 ​

关系数据库理论是当今数据库技术的核心基石。自 1970 年 E.F. Codd 在论文 A Relational Model of Data for Large Shared Data Banks 中首次提出关系模型以来，建立在集合论和谓词逻辑上的关系理论体系，已经成为包括 Oracle、MySQL、PostgreSQL 和 SQL Server 在内的几乎所有主流 DBMS 的理论根基。对关系模型数学基础的深入理解，是掌握 SQL 查询优化和数据库设计的必要前提。

1.1 域与笛卡尔积 ​

域 (Domain) 是一组具有相同数据类型的值的集合。例如，整数集合、长度不超过 20 个字符的字符串集合、以及枚举型集合如 {男 女} 都是域。域的作用在于规定某一类属性的合法取值范围。在数据库实现中，域的概念对应于列的数据类型定义，例如 INT、VARCHAR(20) 或 ENUM。

给定一组域 D1,D2,…,Dn，它们的笛卡尔积 (Cartesian Product) 定义为所有可能的有序组合的集合：

D1×D2×⋯×Dn={(d1,d2,…,dn)∣di∈Di, 1≤i≤n}

其中每一个有序组合 (d1,d2,…,dn) 称为一个 n 元组 (n-tuple)。若各域的基数（即元素个数）分别为 m1,m2,…,mn，则笛卡尔积中元组的总数为 m1×m2×⋯×mn。笛卡尔积列出了所有理论上可能的组合，而实际的数据库关系只是笛卡尔积的一个有语义意义的子集。

域这一概念看似抽象，实际上是在提醒我们：数据库中每一列都不只是“能装某种格式的值”，还承担着限定语义边界的作用。年龄列之所以不能随便写成任意字符串，成绩列之所以应落在合理范围内，本质上都是因为属性值必须来自恰当的域。只要把域理解成“某类属性允许出现的合法值空间”，后续关于类型、约束和完整性的很多要求就会更容易接受。

1.2 关系的形式化定义与基本术语 ​

关系 (Relation) 在数学上是一组域的笛卡尔积的子集。在数据库的物理表现上，一个关系对应一张二维表。由于关系本质上是集合，因此满足集合的基本性质：元组不允许完全重复（由主键保证），元组之间的排列顺序不影响关系的语义，属性列的排列顺序也不影响语义。

与关系相关的基本术语包括：

元组 (Tuple)：关系中的一行，代表一个具体的实体实例。例如在学生表中，一名特定学生的所有信息构成一个元组。

属性 (Attribute)：关系中的一列。每个属性具有一个名称（在同一个关系内不能重名）和一个取值范围（即域）。在数据库实际操作中，属性通常被称为字段或列。

度数 (Degree)：关系中属性的个数。一个包含 5 个属性的关系的度数为 5。

基数 (Cardinality)：关系中元组的个数。基数是动态变化的，会随着数据的插入和删除而改变。

关系模式 (Relation Schema)：是对关系结构的形式化描述，通常记作 R(U,D,DOM,F)，其中 R 为关系名，U 为属性名集合，D 为属性所对应的域集合，DOM 为属性到域的映射，F 为属性间的函数依赖集合。在简化表示中常省略为 R(A1,A2,…,An)。

关系可以分为三类：基本关系（也称基本表，是实际存储在数据库中的表）、查询结果表（由查询操作产生的临时表）和视图表（由基本表导出的虚拟表，数据库中只存储其定义而不存储实际数据）。

基本关系需要满足以下性质：第一，每一列中的分量来自同一个域，是同一类型的数据。第二，不同列可以来自同一个域，但必须有不同的属性名以示区别。第三，行的顺序无关紧要。第四，列的顺序无关紧要。第五，不允许出现完全相同的两行（由关系的集合性质保证）。第六，每个分量必须是不可再分的原子值（这是第一范式的基本要求）。

这里最容易被忽视的一点，是“关系”虽然在界面上表现为二维表，但它在理论上并不是电子表格。电子表格强调单元格位置、填写顺序和视觉呈现，关系则强调集合语义。集合语义意味着行无序、列无序、同一元组不能重复。只要真正接受这一点，很多后续知识就会自然连起来。例如，为什么没有显式 ORDER BY 时不能依赖结果顺序；为什么投影操作在理论上要去重；为什么集合运算要求两个关系满足并相容条件。这些并不是数据库厂商的人为规定，而是关系模型数学基础的自然结果。

同时还要看到，理论中的关系与工程中的 SQL 结果并不完全重合。关系理论默认结果是集合，而现实 SQL 为了效率和表达便利，经常采用可保留重复行的多重集语义；理论上属性值来自明确域，而 SQL 中还允许 NULL 参与运算。学习关系模型不是为了忽略这些差异，而是为了在面对这些工程折中时，依然知道什么是底层原则，什么是产品层的扩展。

2. 键与完整性约束 ​

关系数据库能够保证数据正确性和一致性的关键在于它定义了一套严密的完整性规则体系。这些规则通过键和约束来具体实施。

2.1 键的分类与层次 ​

超键 (Superkey)：能够唯一标识关系中每个元组的属性集合。超键的定义比较宽泛，它可以包含多余属性。例如在学生表中，（学号）是超键，（学号 姓名）也是超键，因为加入姓名后仍然能唯一标识每个学生。

候选键 (Candidate Key)：不包含多余属性的超键。也就是说，候选键中的任何一个属性被去掉后，剩余的属性集合就不再具有唯一标识元组的能力。候选键是最小的超键。一个关系中可能存在多个候选键。例如在身份证信息表中，身份证号和护照号都可以唯一标识一个人，因此两者都是候选键。

主键 (Primary Key)：从候选键中选定的一个，用于在实际操作中唯一标识元组。每个关系只能指定一个主键。主键的选择通常考虑简洁性和稳定性，例如优先选择单一整数列而非组合列。

替代键 (Alternate Key)：候选键中除主键之外的其他候选键。

外键 (Foreign Key)：关系 R 中的某个属性或属性组合，它不是 R 的主键，但其取值要么为空值，要么等于另一个关系 S 中某个主键的值。外键是实现表与表之间关联的核心机制。外键所在的关系 R 称为参照关系，外键指向的关系 S 称为被参照关系。

主属性：包含在任何一个候选键中的属性称为主属性。非主属性：不包含在任何候选键中的属性称为非主属性。这一对概念在规范化理论中非常重要，是判定关系处于第几范式的关键依据。

2.2 三类完整性约束 ​

实体完整性 (Entity Integrity)：要求主键的每个属性列都不能取空值 NULL。因为主键的作用是唯一标识每个元组，如果允许主键为空，就无法有效区分不同的实体实例。在联合主键的情况下，组成主键的每一个属性列都必须非空。

参照完整性 (Referential Integrity)：要求外键的值必须满足以下条件之一：取空值（前提是该外键列允许空值），或者等于被参照关系中某个实际存在的主键值。当对被参照关系中的主键进行删除或修改操作时，系统通常提供三种处理策略：RESTRICT 策略拒绝执行可能破坏参照完整性的操作；CASCADE 策略级联地删除或修改所有引用该主键的外键行；SET NULL 策略将引用方对应的外键值设置为空值。

用户定义完整性：由具体业务规则所决定的约束条件，反映特定应用领域中数据应满足的语义要求。例如，学生年龄必须大于 0 且小于 150 的 CHECK 约束，或者成绩必须在 0 到 100 之间的范围限制。用户定义完整性既可以通过 CHECK 约束在表定义时声明，也可以通过触发器 (Trigger) 在运行时进行更复杂的校验。

从更深一层看，键和约束并不是“为了写建表语句而设置的语法元素”，而是在回答两个根本问题：系统靠什么认出一个对象，系统靠什么阻止错误事实进入数据库。键负责前者，约束负责后者。若一个实体没有清晰稳定的键，数据库就很难可靠去重、建立引用和追踪责任；若约束缺位，错误虽然暂时能写入，代价却会在查询、统计、审计和人工纠错阶段成倍放大。因此，完整性约束越早下沉到数据库层，越能减少后续由应用层和人工流程兜底的成本。

3. 关系代数 ​

关系代数 (Relational Algebra) 是一种过程化的形式查询语言，它以关系（即表）作为运算的对象和结果，通过一组运算符来表达查询请求。SQL 语句在 DBMS 内部经过解析后，最终会被转化为等价的关系代数表达式来执行。因此理解关系代数不仅有助于理解 SQL 的语义，更有助于理解查询优化的原理。

3.1 传统的集合运算 ​

以下运算要求参与运算的两个关系具有相同的度数（列数相同），并且对应属性的域相容（类型兼容）。这一前提条件称为并相容性。

并 (Union)：R∪S 的结果包含所有属于 R 或属于 S 或同时属于两者的元组，并自动去除重复。例如将本科生表和研究生表取并集，可以得到全体学生的名单。

差 (Difference)：R−S 的结果包含那些属于 R 但不属于 S 的元组。例如从全体学生中去掉已注册选课的学生，可以得到尚未选课的学生列表。

交 (Intersection)：R∩S 的结果包含同时属于 R 和 S 的元组。交集实际上可以通过差运算来定义：R∩S=R−(R−S)。

笛卡尔积 (Cartesian Product)：R×S 将 R 中的每个元组与 S 中的每个元组进行拼接。若 R 有 p 个元组和 m 个属性，S 有 q 个元组和 n 个属性，则结果有 p×q 个元组和 m+n 个属性。笛卡尔积本身在实际应用中很少直接使用，因为它产生的数据量通常非常大且包含大量无意义的组合。它的主要价值在于作为连接运算的理论基础。

3.2 专门的关系运算 ​

专门的关系运算是关系数据库中最为核心和常用的操作，它们直接对应于 SQL 查询中的各种子句。

选择 (Selection，记作 σF(R))：从关系 R 中选出满足给定条件 F 的元组。选择操作相当于对行进行过滤，在 SQL 中对应 WHERE 子句。条件 F 由属性名、比较运算符和常量或属性名组成，多个条件之间可以用 AND、OR 和 NOT 连接。选择操作不改变关系的属性结构，只改变元组的数量。

投影 (Projection，记作 πA(R))：从关系 R 中选取若干指定的属性列组成新的关系。投影操作相当于对列进行选取，在 SQL 中对应 SELECT 子句中指定的列名。需要注意的是，投影操作可能会产生重复行，因此结果需要消除重复（对应 SQL 中的 DISTINCT 关键字）。

连接 (Join)：连接运算是从两个关系的笛卡尔积中选取满足一定条件的元组，是关系数据库中实现多表关联查询的基本手段。连接按条件类型可分为以下几种：

Theta 连接是最一般的连接形式，条件 theta 可以是任意的比较运算（大于、小于、等于等）。等值连接是 theta 连接的特例，要求连接条件为等于关系。自然连接 (Natural Join) 是等值连接的进一步特例。自然连接自动在两个关系的所有同名属性上执行等值比较，并在结果中消除重复的同名属性列。自然连接是最常用的连接方式。

在自然连接中，只有在两个关系中都有匹配的元组才会出现在结果中。那些找不到匹配的元组（称为悬浮元组）会被丢弃。如果需要保留某一侧或两侧的全部元组，则需要使用外连接。左外连接保留左关系的全部元组，右侧无匹配时用 NULL 填充；右外连接保留右关系的全部元组；全外连接保留两侧全部元组。

除法 (Division，记作 R÷S)：除法运算用于处理包含"全部"或"至少"语义的查询。设关系 R 的属性集可以分为两部分 X 和 Y，其中 Y 与关系 S 的属性集相同。R÷S 的结果包含这样的 X 值：在 R 中，与该 X 值关联的所有 Y 值的集合完全包含了 S 中的全部元组。

典型的应用场景是查找选修了所有课程的学生。设 SC(Sno, Cno) 为选课表，Course(Cno) 为课程表。SC÷πCno(Course) 的结果就是选修了全部课程的学生学号集合。除法运算是关系代数中理解难度最大的运算，在考试中经常以具体计算题的形式出现。

关系代数之所以值得认真学习，核心原因在于它与 SQL 并不是两套毫不相干的知识。很多常见 SQL 写法都可以映射到代数运算：SELECT 对应投影，WHERE 对应选择，JOIN 对应连接，UNION、INTERSECT、EXCEPT 对应集合运算。把 SQL 语句翻译回代数表达式后，原本容易靠经验猜的性能问题，就能被更稳定地推理出来。例如，多表查询过慢时，可以先问自己能否先过滤再连接，这就是选择下推；能否先裁剪掉无关列再连接，这就是投影下推。代数视角的价值，正在于把“语法技巧”提升为“结构推理”。

除法运算虽然抽象，却很适合训练“全称查询”的思维。面对“修完全部必修课的学生”“覆盖全部目标区域的网点”这类问题时，最好按三步理解：先找出全集 S，再找出候选关系 R 中的主体与条件组合，最后验证某个主体是否覆盖了全集。只要“全集是什么”“覆盖到什么程度算满足条件”这两个问题答清楚，除法类查询就不容易写错。

4. 关系演算 ​

与关系代数的过程化思路不同，关系演算是一种非过程化的形式查询语言。用户只需描述所需数据应满足的逻辑条件，而无需指定获取数据的具体操作步骤。在理论上，关系代数与关系演算的表达能力是等价的，这一等价性已由 Codd 证明。

4.1 元组关系演算 ​

元组关系演算以元组变量作为基本操作单元。其一般形式为 {t∣P(t)}，表示所有使谓词公式 P(t) 为真的元组 t 构成的集合。谓词公式 P 可以包含属性引用、常量比较、逻辑连接词 (AND OR NOT) 以及量词。

存在量词 ∃ 表示只要存在一个满足条件的值即可。全称量词 ∀ 表示对于所有值都必须满足条件。通过组合使用量词和逻辑连接词，可以表达复杂的查询条件。

4.2 域关系演算 ​

域关系演算以域变量（即属性值变量）作为基本操作单元，其形式为 {⟨x1,x2,…,xk⟩∣P(x1,x2,…,xk)}。域关系演算是 QBE (Query By Example) 查询工具的理论基础。

4.3 安全性限制 ​

不论是元组关系演算还是域关系演算，都需要对表达式施加安全性限制 (Safety Restriction)，以确保查询结果是有限的、可计算的。如果不加限制地使用否定和全称量词，可能会产生无限大的结果集，这在实际系统中是无法处理的。安全的关系演算表达式要求：结果中每个分量都来自于表达式中明确涉及的域中的值。

关系演算最值得把握的，不只是形式写法，而是它所代表的声明式思想。过程化思维强调一步一步怎样操作数据，声明式思维强调结果应当满足什么条件。SQL 之所以能够让优化器自由选择执行路径，正是因为用户描述的是结果集合而不是操作步骤。也因此，声明式语言并不意味着“更省事”，而是要求表达更精确。只要条件定义含糊、变量范围不清、边界值漏掉，再强的优化器也无法替用户修正语义错误。

5. 查询优化基础 ​

查询优化是数据库管理系统中极为重要的功能模块。一条 SQL 语句可能有多种等价的执行方式，不同的执行方式之间的性能差异可能达到几个数量级。查询优化器的任务就是从这些等价的执行方案中选择代价最低的一种。

5.1 代数优化的基本策略 ​

代数优化是指利用关系代数表达式的等价变换规则对查询进行重写，以减少中间结果的规模，从而降低查询执行的总代价。主要策略包括：

第一，尽早执行选择操作（选择下推）。将选择条件尽可能向查询树的叶子节点方向下推，使其在连接等代价较高的运算之前执行。这样可以尽早过滤掉不满足条件的元组，减少参与后续运算的数据量。这是最重要、最有效的优化策略之一。

第二，尽早执行投影操作（投影下推）。在查询过程的每一步中尽可能只保留后续运算所需要的属性列，去掉不必要的列。这可以减少中间结果的宽度，降低数据传输量和内存占用。

第三，将选择与笛卡尔积结合为连接操作。如果一个笛卡尔积之后紧跟一个涉及两个关系属性的等值选择条件，应将其合并为一个等值连接操作。等值连接可以利用索引等手段进行高效处理，而直接计算笛卡尔积通常会产生大量冗余的中间数据。

第四，合并相邻的选择操作和投影操作。多个连续作用的选择条件可以合并为一个复合条件的选择；同样，连续的投影操作也可以合并为一次投影以减少扫描次数。

教材中讲查询优化时，学生常把注意力直接放到“某种连接算法快不快”上，反而忽略了优化的层次。更清晰的理解方式是把优化分成三层：第一层是语义等价层，确认改写后结果不变；第二层是代数重写层，尽可能减少中间结果规模；第三层才是物理执行层，选择哈希连接、嵌套循环或归并连接等具体算法。若上层语义和代数结构已经失真，再好的底层算法也难以挽救性能。因此，优化首先是结构问题，其次才是算法问题。

5.2 物理优化简述 ​

在代数优化完成后，物理优化阶段需要为查询执行计划中的每个运算选择具体的实现算法。例如，对于连接操作，物理优化器需要在嵌套循环连接 (Nested Loop Join)、排序归并连接 (Sort-Merge Join) 和哈希连接 (Hash Join) 等算法之间进行选择。选择的依据主要包括参与运算的表的大小、可用的索引、内存缓冲区的大小以及数据的物理存储分布等因素。

现代查询优化器通常采用基于代价的优化方法 (Cost-Based Optimization)，通过估算每种执行方案的 I/O 代价、CPU 代价和网络代价等指标，选择总代价最低的执行方案。代价估算依赖于数据字典中维护的统计信息，如各表的行数、各列的值分布直方图和索引的选择性等。

关系模型的学习还承担着承前启后的作用。它不仅帮助我们解释查询为什么这样执行，也为后续数据库设计建立了共同语言。一个良好的关系模式，应当让每张表只表达一个相对单一且清晰的事实集合，让主键定义对象身份，让外键承担联系，让约束守住语义边界。若缺少这种结构意识，表就容易退化成字段的随意堆砌，随后在更新异常、删除异常和统计口径混乱中暴露问题。也就是说，关系模型不是孤立的理论章节，而是连接数学基础、SQL 语言和模式设计的桥梁。

因此，学习关系模型最重要的训练，并不是记住多少定义，而是形成“先结构、后操作”的思维习惯。看到一张表时，要能说清它记录的事实主体是什么、键是什么、约束是什么；看到一个查询时，要能判断它本质上对应哪种集合运算；看到一种设计缺陷时，要能解释它可能导致哪类异常。只要这种结构化训练真正建立起来，关系模型就不再只是抽象理论，而会成为理解整个数据库课程的共同语言。

🔒 会员专属内容

检查登录状态中...