2.2 关系模型的完整性

关系模型的完整性规则 是指对关系的约束条件，是数据操作中应遵守的规则，保证其正确相容性。 主要有三类完整性约束 ：实体完整性约束、参照完整性约束和用户定义的完整性约束。前两个称为 关系的不变性 ，是关系模型必须满足的完整性约束条件，由系统自动实现。用户定义的完整性是业务应用时实际遵循的规则。

2.2.1 关系模型的实体完整性

实体完整性（Entity Integrity）规则： 如果属性 A （单一属性（组））是基本关系 R 的主属性，则属性 A 不能取空值。

主键是记录的唯一标识（调用的指定位置），如果主属性为空，则将导致记录不可区分，这与实体的定义矛盾。例如，学生数据表的“学号”不能为空，如果为空则表明学生不存在，后续的学生选课和学生选课成绩就无法查找与进行数据处理。

实体完整性要求 保证每个关系（二维表）有且仅有一个主键，而且每个主键的值必须唯一，不能为空值或重复，以确保数据操作的正确、完整、可靠。

2.2.2 关系模型的参照完整性

在实际应用中，关系模型中的实体及其之间的联系可用关系表示。例如，用户查询数据时经常需要通过主键和外键进行多表之间数据的关联或引用。

参照完整性（Referencial Integrity）形式化的定义 ：如果 F 是关系 R 的一个或一组属性，但不是 R 的键， K 是关系 S 的主键，若 F 与主键 K 相对应，则称 F 是关系 R 的外键，并称 关系 R 为参照关系，关系 S 为被参照关系 或 目标关系 。

参照完整性体现在两方面 ：实现多表之间的关联，外键的取值必须是另一表主键的有效值或是空值（暂时未定）。

注意： 在关系模式中，外键不一定与对应主键同名，外键常用下画曲线标出。外键的值是否允许为空，应视具体问题而定。

参照完整性规则 是外键和主键之间的引用规则。若属性（组） F 是关系 R 的外键， F 与关系 S 的主键 K 相对应（关系 R 和 S 不一定是不同关系），则 R 中每个元组在 F 上的值或为空，或等于 S 中某个元组的主键。

学生和专业关系存在属性的引用，即学生关系引用了专业关系的主键“专业编号”，此处学生关系中的“专业编号”的取值需要参照专业关系中的“专业编号”，即学生关系中“专业编号”的取值或为空值（表明学生还没确定专业），或取某个具体值。例如，在插入数据时，DBMS负责验证外键是否合法，并决定是否插入该记录。

2.2.3 用户定义完整性及域完整性

用户定义的完整性（User-defined Integrity） 是指对数据表中字段属性的约束（实际要求），包括属性的值域、类型、宽度和小数点位数等，是由确定关系结构时所定义的字段属性决定的。例如，在客户申请银行卡时，银行对身份证进行合法验证，要求其字段长度为18位。

域完整性（Domain Integrity） 是指属性（列）值域的完整性，如数据类型、格式、值域范围、是否允许空值等，是针对某一具体数据库的约束条件，保证表中的某些列不能输入无效的值。域完整性限制了某些属性中的值，将属性限制在一个有限集合。例如，通常，正式职工的年龄在18～60之间。

讨论思考：

1）在关系模型中具体有哪几类完整性约束？

2）关系中为何满足实体完整性和参照完整性？

3）试举例说明用户定义的完整性应用案例。

2.3 常用的关系运算

数据查询是实际应用中最常用的操作。关系代数是一种抽象的查询语言，是以集合代数为基础、以关系（表）为运算对象的高级运算。 关系运算具有三大要素： 运算对象、运算符和运算结果。关系代数的运算对象和运算结果都是关系。

2.3.1 关系运算种类和运算符

1．关系运算的种类

关系运算的种类 有 两种 ：传统关系运算和专门关系运算。 传统关系运算 将关系作为集合，并对“水平”方向（行）运算， 专门关系运算涉及 行和列。

（1）传统关系运算

传统关系运算主要使用传统的集合运算方法将关系（表）作为行（记录）的集合，从关系的行方向进行（集合）运算，常用的是两个关系的运算。

传统的集合运算可以实现的基本操作 如下。

1）并运算。在数据库中，用于实现对指定数据的插入和添加操作。

2）差运算。在数据库中，用于实现对指定数据记录的删除操作。

3）差并结合。修改数据的操作，要先删除（差）后插入（并）。

（2）专门关系运算

专门关系运算 是针对关系数据库专门设计的，涉及关系的行和列。利用比较运算符和逻辑运算符可以实现辅助专门的关系运算符操作。有时还需要对关系本身运算，如果需要显示表中某列的值，就需要利用关系的专门运算中的“投影”。

2．关系运算符

关系运算符有四种 ：集合运算符、专门的关系运算符、（算术）比较运算符和逻辑运算符。具体的使用方法将在后面结合应用案例介绍。

1）集合运算符：∪（并运算）、—（差运算）、∩（交运算）、×（笛卡儿积）。

2）专门的关系运算符：σ（选择）、π（投影）、 （连接）、÷（除）。

3）（算术）比较运算符：＞（大于）、≥（大于或等于）、＜、≤、=、≠。

4）逻辑运算符： （非）、∧（与）、∨（并）。

2.3.2 传统的关系运算

传统的关系运算可以归纳为集合运算，即对两个关系的集合运算， 主要包括四种 ：并、差、交和广义笛卡儿积。

1．并运算

设关系 R 和关系 S 具有相同的 n 目（属性/列），且相应的属性取自同一个域，则 关系 R 和关系 S 的并（Union） 由属于 R 或属于 S 的记录（元组）组成。其结果关系的目仍为 n ，记为 R ∪ S 。 形式化定义 为 R ∪ S ={ t|t ∈ R ∨ t ∈ S }。其中， t 表示关系 R 或 S 中的记录，即关系 R 或 S 中的行。

注意： R ∪ S 的结果集合是 R 中的记录和 S 中的记录合并一起构成的一个新关系。特别要指出的是，合并后的结果必须除去重复记录。

2．差运算

设关系 R 和关系 S 具有相同的 n 目（列/属性），且相应的属性取自同一个域，则 关系 R 和关系 S 的差（Difference） 由属于 R 且不属于 S 的记录组成。其结果关系的目仍为 n ，记为 R-S 。形式化定义为 R-S ={ t|t ∈ R ∧ t ∉ S }。其中， t 表示属于 R 且不属于（差掉） S 的所有记录。

3．交运算

设关系 R 和关系 S 具有相同的 n 目（列/属性），且相应的属性取自同一个域，则 关系 R 和关系 S 的交（Intersection） 由属于 R 且属于 S 的记录组成。其结果关系的属性数仍为 n ，记为 R ∩ S 。 形式化定义 为 R ∩ S ={ t|t ∈ R ∧ t ∈ S }。其中， t 为同时属于关系 R 和 S 中的所有记录，即关系 R 且 S 中行的公共部分。

4．广义笛卡儿积

设关系 R 和关系 S 的目（列/属性）分别为 r 及 s 。关系 R 和 S 的 广义笛卡儿积（Extended Cartesian） R × S 是一个（ r + s ）目的记录集合（新关系有 r + s 列），每个记录的前 r 个分量（属性值）来自关系 R 的一个记录，后 s 个分量是关系 S 的一个记录。关系 R 和关系 S 的笛卡儿积记为 R × S ，其 形式化定义 为 。

说明： t ^r 、 t ^s 中的 r 、 s 为上标，分别表示 r 个分量和 s 个分量。若关系 R 的基数（行数）为 k ₁ ，关系 S 的基数为 k ₂ ，则关系 R 和关系 S 的笛卡儿积的基数为 k ₁ × k ₂ 。

注意： 关系 R 和关系 S 中有相同的属性名“学号”，在计算结果中为了区分，需要在其属性名前标注上相应的关系名，如 R .学号和 S .学号。

在实际应用中，单独笛卡儿积本身并无具体实际意义和用途，只有在两表连接时需要限制条件，才能起到正确处理有效数据的作用。

2.3.3 专门的关系运算

专门的关系运算有四种 ：选择运算、投影运算、连接运算和除运算。其中，选择运算可以在多表中选取符合满足条件的记录并构成新关系（表），投影运算可选取记录中指定的属性（列）并构成新关系，连接运算可选取符合条件的记录串联（连接）成新关系，除运算可选取象集符合条件的记录的多个属性（列）构成新关系。

1．选择运算

选择（Selection） 运算也称 限制（Restriction） ，可对关系进行水平（行）分割（选取）。选择是在表中选取符合指定条件的记录， 记为 σ _F （ R ） 。其中， σ 为选择运算符； F 表示选择条件， F 通常是一个逻辑表达式，其取值为逻辑值“真”（成立）或“假”（不成立）。 σ _F （ R ）表示从 R 中选取满足条件 F 的记录（行）所构成的新关系， 形式化定义 为 σ _F （ R ）={ t|t ∈ R ∧ F （ t ）=true}。

逻辑表达式 F 的基本形式 为 X θ Y 。其中，θ表示比较运算，可以是＞、≥、＜、≤、=、≠； X 和 Y 为属性名、常量或简单函数，属性名可以用其序号替代。在基本的选择条件中可以进一步地进行逻辑运算，包括非（ ）、与（∧）、或（∨）运算。

2．投影运算

投影（Projection） 运算可对关系（表）进行垂直分割，即对关系的列方向的筛选。

投影运算是在一个关系中选取某些属性或列，并重新排列其顺序，再删掉重复记录后构成的新关系，是对二维表的垂直分割， 记为π _A （ R ） 。其中，π为投影运算符， A 为关系 R 中的属性列。 投影运算的形式化定义 为 （π _A （ R ）={ t 「 A ┐ t ）∈ R } 。

3．连接运算

连接（Join） 运算也称为 θ连接 ，是从两个关系的广义笛卡儿积中选取属性间满足一定条件的记录。 形式化定义为 ：

其中， A 和 B 分别为关系 R 和关系 S 上列数相同且可比的属性组。θ为比较运算符。连接运算从 R 和 S 的笛卡儿积 R × S 中选取 R 关系在 A 属性组上的值与 S 关系在 B 属性组上的值满足比较关系θ的记录。

连接运算中有两种常用的连接 ：等值连接（Equijoin）和自然连接（Natural Join）。

1） 等值连接 。等值连接指θ为“=”的连接运算。从关系 R 和关系 S 的广义笛卡儿积中选取 A 与 B 属性（列）相等的记录，即等值连接记为：

2） 自然连接 。自然连接是一种特殊的等值连接，要求两个关系中进行比较的分量（属性值/数据项）必须是相同的属性组，并且在结果中把重复的属性列去掉。如果关系 R 和 S 具有相同的属性组 B ，则自然连接可记为：

注意： 通常，连接操作是从行的角度进行运算的。而自然连接还需要取消重复列（常为后面的列），所以是同时从行和列的角度进行的运算。

自然连接与等值连接的主要区别 如下。

1）等值连接中相等的属性可以是相同的属性，也可以是不同的属性，而自然连接中相等的属性必须是相同的属性。

2）自然连接结果必须去除重复属性，而等值连接的结果不需要去除重复属性。

3）自然连接用于有公共属性的情况。若两个关系没有公共属性，则它们不能进行自然连接，而等值连接无此要求。自然连接在多表数据调用时常用。

4．除运算

给定关系 R （ X ， Y ）和 S （ Y ， Z ），其中 X ， Y ， Z 为属性组。 R 中的 Y 与 S 中的 Y 可以有不同的属性名，但必须出自相同的域集。

R 与 S 的 除运算（Division） 得到一个新的关系 P （ X ）， P 是 R 中满足下列条件的记录在 X 属性列上的投影：记录在 X 上的分量值 x 的象集 Y _X 包含 S 在 Y 上投影的集合。 记作：

其中， Y _X 为 x 在 R 中的象集， x = t _r [ X ]。除运算通常是对关系的行和列角度进行操作。

除运算的计算过程 如下。

1）将被除关系的属性分为象集属性和结果属性两部分，与除关系相同的属性归于象集，不相同的属性归于结果集。

2）在除关系中，在与被除关系相同的属性（象集属性）上投影，得到除目标数据集。

3）将被除关系分组，将结果属性值相同的记录分为一组。

4）观察每个组，若它的象集属性值中包括除目标数据集，则对应的结果属性值应该属于除法运算结果集，并去掉与原被除关系相同的分组。

具体除运算的计算过程 ：

1）关系 R 中属性组（ A ， B ）的取值为{（2，1），（2，2），（3，2）}。其中，（2，1）的象集为{（a，c），（b，d）}，（2，2）的象集为{（a，d）}，（3，2）的象集为{（b，d），（b，c）}。

2）关系 S 在属性组（ C ， D ）上的投影为{（a，c），（b，d）}。

3）找出全部属性组（ A ， B ）象集包含关系 S 属性组（ C ， D ）上的投影的取值，即为新关系 R ÷ S ，此处通过比较1）和2）可以发现，只有记录（2，1）的象集包含关系 S 在属性组（ C ， D ）上的投影，所以 R ÷ S 只有一个记录（2，1），即 R ÷ S 运算结果如表2-22所示。

除的基本运算可以表示为等价关系表达式：

π _A （ R ） -π _A （ π _A （ R ）× S-R ）

下面举例说明关系代数 综合运算应用 。

设商品销售数据库有三个关系：商品、售货员和售货。

商品（商品编号，商品名，产地，价格，等级）

售货员（售货号编号，姓名，性别，年龄）

售货（商品编号，售货员编号，数量）

讨论思考：

1）交、并、差运算的两个关系必须满足什么条件？

2）除运算的结果主要表示什么具体的含义？

3）等值连接和自然连接之间的区别是什么？ 10r4we/x92t0ZKDb9humbUmOv6POE1u1KiNYLrKsO4ncc0yQz+NGU6A9WpxjmBf4

*2.4 关系演算与查询优化

关系演算与关系运算不同，是以数理逻辑中的谓词演算为基础的一种运算。与关系代数相比较，关系演算是非过程化的。关系演算只需描述结果的信息，而不需给出获得信息的具体过程。按谓词变元的不同，关系演算可分为记录关系演算和域关系演算。记录关系演算以记录为变量，域关系演算以域为变量。

*2.4.1 关系演算概述

1．记录关系演算

记录关系演算（Tuple Relational Calculus）的形式化表达 为{ t|φ （ t ）}。其中， t 为记录变量，表示一个元数固定的记录； φ （ t ）是以记录变量 t 为基础的公式。该表达式的含义是使 φ （ t ）为真的记录 t 的组合。关系演算由原子公式和运算符组成。

原子公式有以下三类 。

1） R （ t ）。 R 是关系名， t 是记录变量， R （ t ）表示 t 是关系 R 的一个记录。

2） t [ i ]θ s [ j ]。其中， t 和 s 是记录变量，θ是算术比较运算符（如＞、＜、=、≥等）。 t [ i ]θ s [ j ]表示记录 t 的第 i 个分量与记录 s 的第 j 个分量满足θ关系。例如， t [3]≥ s [5]表示 t 的第3个分量大于或等于 s 的第5个分量。

3） t [ i ]θ C 或 C θ t [ i ]。其中， C 表示一个常量， t 是记录变量，θ是算术比较运算符。 t [ i ]θ C 表示 t 的第 i 个分量与常量 C 满足关系θ。例如， t [2]>5表示 t 的第2个分量大于5。

公式可递归定义如下 。

1）每个原子公式都是公式。

2）如果 ϕ ₁ 和 ϕ ₂ 是公式，则 ϕ ₁ ∧ ϕ ₂ 、 ϕ ₁ ∨ ϕ ₂ ， ϕ ₁ 也是公式。其中， ϕ ₁ ∧ ϕ ₂ 表示只有 ϕ ₁ 和 ϕ ₂ 同时为真时 ϕ ₁ ∧ ϕ ₂ 为真，否则 ϕ ₁ ∧ ϕ ₂ 为假； ϕ ₁ ∨ ϕ ₂ 表示只有 ϕ ₁ 和 ϕ ₂ 同时为假时 ϕ ₁ ∨ ϕ ₂ 为假，否则 ϕ ₁ ∨ ϕ ₂ 为真； ϕ ₁ 表示如果 ϕ ₁ 为真，则 ϕ ₁ 为假。3）如果 ϕ 为公式，则∃ t （ ϕ ）也是公式。其中，符号∃是存量词符号。∃ t （ ϕ ）表示若有一个 t 使 ϕ 为真，则∃ t （ ϕ ）为真，否则∃ t （ ϕ ）为假。

4）如果 ϕ 为公式，则∀ t （ ϕ ）也是公式。其中，∀是全称量词符号。∀ t （ ϕ ）表示如果对于所有 t ，都使 ϕ 为真，则∀ t （ ϕ ）为真，否则∀ t （ ϕ ）为假。

5）在记录演算公式中， 各种运算符的优先级 如下。

①算术比较运算符的优先级最高。

②量词次之，且∃的优先级高于∀的优先级。

③逻辑运算符最低，且 的优先级高于∧的优先级，∧的优先级高于∨的优先级。

④加括号时，括号中的运算符优先，同一括号内的运算符的优先级遵循①、②、③三项。

6）有限次地使用上述五条规则得到的公式是记录关系演算公式，其他公式不是记录关系演算公式。

关系代数的运算均可以用关系演算表达式来表示（反之亦然）。下面用关系演算表示 关系代数的五种运算 。

（1） 并运算

（2） 差运算

（3） 笛卡儿积

（4） 投影运算

（5） 选择运算

其中，关系 F′ 是 F 的等价条件。

下面给出一个关系演算的应用案例，供读者参考。

2．域关系演算

域关系演算与记录关系演算相似，记录关系演算中表达式使用的是记录变量，记录变量的变化范围是一个关系，域关系演算表达式中则以属性列为变量，即域变量。域变量的变化范围是上述的某值域。

域关系演算的原子公式 有两种形式。

1） R （ x ₁ ， x ₂ ，…， x _k ）。其中， R 是一个元数为 k 的关系， x _i 是一个常量或域变量。如果（ x ₁ ， x ₂ ，…， x _k ）是 R 的一个记录，则 R （ x ₁ ， x ₂ ，…， x _k ）为真。

2） x θ y 。其中， x 和 y 是常量或域常量，但至少有一个是域变量。θ是算术比较运算符。如果 x 和 y 满足关系θ，则 x θ y 为真。

域关系演算表达式 的 一般形式 为{ x ₁ ， x ₂ ，…， x _k |ϕ （ x ₁ ， x ₂ ，…， x _k ）}。

其中， x ₁ ， x ₂ ，…， x _k 都是域变量， ϕ 是公式。该表达式的含义是使 ϕ 为真的域变量 x ₁ ， x ₂ ，…， x _k 组成的记录集合。

下面是应用域关系演算对商品销售数据库进行查询的实例。

*2.4.2 查询优化常用规则与算法

查询是应用最广泛的操作，查询策略和方法至关重要。为了提高效率，可以先将查询语句转换为执行时间少的关系运算，并选取较优的存取路径，即查询优化。

1．关系代数等价变换规则

关系代数是各种数据库查询语言的基础，各种查询语言都能转换成关系代数表达式，所以关系代数表达式的优化是查询优化的基本方法。两个关系代数表达式等价是指用同样的关系实例代替两个表达式中相应的关系时，所得到的结果相同。

两个关系表达式 E ₁ 和 E ₂ 等价可表示为 E ₁ ≡ E ₂ 。

等价变换规则指出两种不同形式的表达式是等价的，可利用第二种形式的表达式代替第一种，或者用第一种形式的表达式代替第二种，主要原因是这两种表达式在任何有效的数据库中运行后将得到同样的结果。

常用的等价变换规则 如下。

（1）笛卡儿积和连接表达式的等价交换律

设 E ₁ 和 E ₂ 是两个关系代数表达式， F 是连接运算的条件，则：

（2）笛卡儿积和连接的结合律

设 E ₁ 、 E ₂ 和 E ₃ 是三个关系代数表达式， F ₁ 和 F ₂ 是两个连接运算的限制条件， F ₁ 只涉及 E ₁ 和 E ₂ 的属性， F ₂ 只涉及 E ₂ 和 E ₃ 的属性，则：

（3）投影的串联

设 E 是一个关系表达式， L ₁ ， L ₂ ，…， L _n 是属性名，则：

说明： 投影运算序列中，只有最后一个运算是需要的，其余可以省略。

（4）选择的串联

设 E 是一个关系表达式， F ₁ 和 F ₂ 是两个选择条件，则：

（5）选择和投影的交换

设 E 为一个关系代数表达式，选择条件 F 只涉及 L 中的属性，则：

π _L （ σ _F （ E ））≡ σ _F （ π _L （ E ））

若上式中的 F 还涉及不属于 L 的属性集 K ，则有：

π _L （ σ _F （ E ））≡ π _L （ σ _F （ π _{L ∧ U} （ E ）））

（6）选择对笛卡儿积的分配律

设 E ₁ 和 E ₂ 是两个关系代数表达式，若 F 只涉及 E ₁ 的属性，则：

σ _F （ E ₁ × E ₂ ）≡ σ _F （ E ₁ ）× E ₂

若 F = F ₁ ∧ F ₂ ，并且 F ₁ 只涉及了 E ₁ 中的属性， F ₂ 只涉及了 E ₂ 中的属性，则：

若 F ₁ 只涉及了 E ₁ 中的属性，而 F ₂ 涉及了 E ₁ 和 E ₂ 中的属性，则：

（7）选择对并的分配律

设 E ₁ 和 E ₂ 有相同的属性名，或者 E ₁ 和 E ₂ 表达的关系的属性有对应性，则：

σ _F （ E ₁ ∪ E ₂ ）≡ σ _F （ E ₁ ）∪ σ _F （ E ₂ ）

（8）选择对差的分配律

设 E ₁ 和 E ₂ 有相同的属性名，或者 E ₁ 和 E ₂ 表达的关系的属性有对应性，则：

σ _F （ E ₁ -E ₂ ）≡ σ _F （ E ₁ ） -σ _F （ E ₂ ）

（9）投影对并的分配律

设 E ₁ 和 E ₂ 有相同的属性名，或者 E ₁ 和 E ₂ 表达的关系的属性有对应性，则：

π _L （ E ₁ ∪ E ₂ ）≡ π _L （ E ₁ ）∪ π _L （ E ₂ ）

（10）投影对笛卡儿积的分配律

设 E ₁ 和 E ₂ 是两个关系代数表达式， L ₁ 是 E ₁ 的属性集， L ₂ 是 E ₂ 的属性集，则：

其他的等价关系变换规则请查阅相关文献，此处不一一列举。

2．关系表达式的优化算法

关系代数表达式的优化由DBMS的DML编译器完成。对于给定的查询，根据关系代数等价规则，得到与之等价的优化关系表达式序列，其中每个表达式序列执行的代价有所不同。对于优化器而言，存在选择查询最佳策略问题。

等价规则变换优化关系表达式的算法（关系代数表达式的优化）。

输入：一个待优化的关系表达式的语法树。

输出：计算表达式的一个优化序列。

方法：

1）利用等价变换规则（4）将 变换为 。

2）对每一个选择，利用等价变换（4）～（8），尽可能将它移动到树的叶端。

3）对每一个投影，利用等价变换规则（3）、（5）、（10）中的一般表达式，尽可能将它移动到树的叶端。

4）利用等价变换规则（3）～（5），将选择和投影的串接合并为单个选择、单个投影或一个选择后跟一个投影。使多个选择或投影能同时执行，或在一次扫描中全部完成。

5）将上述得到的语法树的内节点分组。每一个二元运算和它所有的直接祖先为一组。若其后代直到叶子全是一元运算，则也将它们并入该组，但当二元运算是广义笛卡儿积并且后面不是与它组成等值连接的选择时，则不能将选择与这个二元运算组成一组，而是将这些一元运算单独分为一组。

讨论思考：

1）什么是关系演算？在关系演算公式中，各运算符优先级是怎样的？

2）记录关系演算和域关系演算有何区别及联系？

3）进行查询优化的主要原因是什么？

4）试举例说明关系表达式优化的过程。 10r4we/x92t0ZKDb9humbUmOv6POE1u1KiNYLrKsO4ncc0yQz+NGU6A9WpxjmBf4