第2章 关系模型和 关系运算理论

本章重要概念（一） （1）基本概念 关系模型，关键码（主键和外键），关系的定义和性质，三类完整性规则，ER模型到关系模型的转换规则，过程性语言与非过程性语言。 （2）关系代数 五个基本操作，四个组合操作，七个扩充操作。

本章重要概念（二） （3）关系演算 元组关系演算和域关系演算的原子公式、公式的定义。关系演算的安全性和等价性。 （4）关系代数表达式的优化 关系代数表达式的等价及等价转换规则，启化式优化算法。 （5）关系逻辑 谓词、原子、规则和查询，规则的安全性，用规则模拟关系代数表达式。

本章概要 本章先介绍关系模型的基本概念；然后介绍关系运算的三种理论：关系代数、关系演算和关系逻辑。

关系模型和关系运算理论 2.1 关系模型的基本概念 2.2 关系代数 2.3 关系演算 2.4 关系代数表达式的优化 2.5 关系逻辑

2.1 关系模型的基本概念 基本术语 关系的定义和性质 关系模型的三类完整性规则 ER模型向关系模型的转换规则 关系模型的三级体系结构 关系模型的形式定义和优点 关系查询语言和关系运算 返回

基本术语(1) 用二维表格表示实体集，用关键码进行数据导航的数据模型称为关系模型（relational Model）。这里数据导航(data navigation)是指从已知数据查找未知数据的过程和方法。 职工登记表

基本术语 在关系模型中，字段称为属性，字段值称为属性值，记录类型称为关系模式。记录称为元组（tuple），元组的集合称为关系（relation）或实例（instance）。一般用大写字母A、B、C、… 表示单个属性，用大写字母 …、X、Y、Z表示属性集，用小写字母表示属性值，有时也习惯称呼关系为表或表格，元组为行(row)，属性为列(column)。 关系中属性个数称为“元数”（arity），元组个数为“基数”(cardinality)。

2.1.1 基本术语(3) 关系模式名是R，关系元数为5，基数为4。 关系模型的术语 文 件 关 系 一般术语 关系模型术语 2.1.1 基本术语(3) 关系模式名是R，关系元数为5，基数为4。 一般术语 关系模型术语 字段、数据项 属性 记录类型 关系模式 记录1 元组1 记录2 元组2 记录3 元组3 记录4 元组4 字段值 属性值 关系模型的术语 文 件 关 系

基本术语(4) 关键码(key,简称键)由一个或多个属性组成。在实际使用中，有下列几种键。 （1）超键（Super Key） （2）候选键（Candidate Key） （3）主键(Primary Key) 在职工登记表中，（工号，姓名）是模式的一个超键，但不是候选键， 而（工号）是候选键。在实际使用中，如果选择（工号）作为删除或查找元组的标志，那么称（工号）是主键。 （4）外键（Foreign Key） 返回

关系的定义和性质 关系是一个属性数目相同的元组的集合。 在关系模型中，对关系作了下列规范性限制 关系中每一个属性值都是不可分解的 关系中不允许出现重复元组（即不允许出现相同的元组） 由于关系是一个集合，因此不考虑元组间的顺序，即没有行序 元组中的属性在理论上也是无序的，但使用时按习惯考虑列的顺序。 返回

关系模型的完整性规则(1) 实体完整性规则（entity integrity rule） 要求关系中元组在组成主键的属性上不能有空值。如果出现空值，那么主键值就起不了惟一标识元组的作用。

关系模型的完整性规则 (2) 参照完整性规则（reference integrity rule） 如果属性集K是关系模式R1的主键，K也是关系模式R2的外键，那么在R2的关系中，K的取值只允许两种可能，或者为空值，或者等于R1关系中某个主键值 这条规则的实质是“不允许引用不存在的实体” 关系模式R1的关系称为“参照关系”，关系模式R2的关系称为“依赖关系”。“主表”和“副表”，“父表”和“子表”。

关系模型的完整性规则 (3) 下面各种情况说明了参照完整性规则在关系中如何实现的。 在关系数据库中有下列两个关系模式： S（S#，SNAME，AGE，SEX） SC（S#，C#，GRADE） 这里带 线者为主键，带 线者为外键。据规则要求关系SC中的S#值应该在关系S中出现。如果关系SC中有一个元组（S7,C4,80），而学号S7却在关系S中找不到，那么我们就认为在关系SC中引用了一个不存在的学生实体，这就违反了参照完整性规则。 另外，在关系SC中S# 不仅是外键，也是主键的一部分，因此这里S# 值不允许空。

关系模型的完整性规则 (4) 设工厂数据库中有两个关系模式： DEPT(D#，DNAME) EMP(E#，ENAME，SALARY，D# ) 车间模式DEPT的属性为车间编号、车间名，职工模式EMP的属性为工号、姓名、工资、所在车间的编号。每个模式的主键与外键已标出。在EMP中，由于D# 不在主键中，因此D# 值允许空。

关系模型的完整性规则 (5) 设课程之间有先修、后继连系。模式如下： R（C#，CNAME，PC#） 其属性表示课程号、课程名、先修课的课程号。如果规定，每门课程的直接先修课只有一门，那么模式R的主键是C#，外键是PC#.。这里参照完整性在一个模式中实现。即每门课程的直接先修课必须在关系中出现。

关系模型的完整性规则 (6) 用户定义的完整性规则 在建立关系模式时，对属性定义了数据类型，即使这样可能还满足不了用户的需求。此时，用户可以针对具体的数据约束，设置完整性规则，由系统来检验实施，以使用统一的方法处理它们，不再由应用程序承担这项工作。 例如学生的年龄定义为两位整数，范围还太大，我们可以写如下规则把年龄限制在15～30岁之间： CHECK（AGE BETWEEN 15 AND 30） 返回

2.1.4 ER模型向关系模型的转换规则 (1) ER模型向关系模型的转换，实际上就是把ER图转换成关系模式的集合。 规则2.1（实体类型的转换）：将每个实体类型转换成一个关系模式，实体的属性即为关系模式的属性，实体标识符即为关系模式的键。 规则2.2（二元联系类型的转换） ① 若实体间联系是1:1。 ② 若实体间联系是1:N。 ③ 若实体间联系是M:N。

2.1.4 ER模型向关系模型的转换规则 (2) 图2.3 一对一联系 职称 校名 地址 校长 学校 电话 姓名 性别 年龄 1 图2.3 一对一联系 任职年月 职称 校名 地址 校长 任职 学校 电话 姓名 性别 年龄 1 学校（校名，地址，电话， 校长名，任职年月） 校长（姓名，性别，年龄，职称）

2.1.4 ER模型向关系模型的转换规则 (3) 图2.4 一对多联系 系号 系名 教师 聘用 系 电话 聘期 工号 姓名 性别 年龄 1 N 系（系号，系名，电话） 教师（工号，姓名，性别， 年龄，系号，聘期）

2.1.4 ER模型向关系模型的转换规则 (4) 图2.5 多对多联系 学号 姓名 课程 学生 年龄 成绩 性别 M N 课程号 课程名 教师名 选课 性别 M N 学生（学号，姓名，年龄，性别） 选课（学号，课程号，成绩） 课程（课程号，课程名，教师名） 返回

2.1.5 关系模型的三级体系结构 -- 关系模式 学生关系模式S(S#，SNAME，AGE，SEX) 2.1.5 关系模型的三级体系结构 -- 关系模式 在关系模型中，记录类型称为关系模式，而关系模式的集合就是数据库的概念模式。在系统实现时，关系模式和属性的命名一般都用英文单词。譬如图2.5的ER图转换成的关系模式集可用图2.6表示。而图2.7是这个关系模型的三个具体关系。 学生关系模式S(S#，SNAME，AGE，SEX) 选课关系模式SC(S#，C#，GRADE) 课程关系模式C(C#，CNAME，TEACHER) 图2.6 关系模式集

成绩子模式 G(S#，SNAME，C#，GRADE) 2.1.5 关系模型的三级体系结构 --子模式 子模式是用户所用到的那部分数据的描述。除此之外，还应指出数据与关系模式中相应数据的连系。例如，用户需要用到子模式G（图2.8）。 成绩子模式 G(S#，SNAME，C#，GRADE)

2.1.5 关系模型的三级体系结构 --存储模式 图2.10 关系S和SC的环结构 在有些DBMS中，关系存储是作为文件看待的，每个元组就是一个记录。由于关系模式有键，因此存储一个关系可用散列方法或索引方法实现。如果关系的元组数目较少（100个以内），那么也可以用“堆文件”方式实现（即没有特定的次序）。此外，还可对任意的属性集建立辅助索引。

2.1.6 关系模型的形式定义 关系模型有三个重要组成部分：数据结构，数据操纵，数据完整性规则。 （1）数据结构：数据库中全部数据及其相互连系都被组织成“关系”（二维表格）的形式。关系模型基本的数据结构是关系。 （2）数据操纵：关系模型提供一组完备的高级关系运算，以支持对数据库的各种操作。关系运算分成关系代数、关系演算和关系逻辑等三类。 （3）数据完整性规则：数据库中数据必须满足实体完整性，参照完整性和用户定义的完整性等三类完整性规则。

2.1.6 关系模型的优点 与其它数据模型相比，关系模型突出的优点如下： （1）关系模型提供单一的数据结构形式，具有高度的简明性和精确性。 2.1.6 关系模型的优点 与其它数据模型相比，关系模型突出的优点如下： （1）关系模型提供单一的数据结构形式，具有高度的简明性和精确性。 （2）关系模型的逻辑结构和相应的操作完全独立于数据存储方式，具有高度的数据独立性。 （3）关系模型使数据库的研究建立在比较坚实的数学基础上。 （4）关系数据库语言与一阶谓词逻辑的固有内在连系，为以关系数据库为基础的推理系统和知识库系统的研究提供了方便。 返回

2.1.7 关系查询语言和关系运算 关系数据库的数据操纵语言（DML）的语句分成查询语句和更新语句两大类。查询语句用于描述用户的各种检索要求；更新语句用于描述用户进行插入、删除、修改等操作。关于查询的理论称为“关系运算理论”。 关系查询语言根据其理论基础的不同分成三类： （1）关系代数语言。 （2）关系演算语言。 （3）关系逻辑语言。 返回

2.2 关系代数 关系代数的五个基本操作 关系代数的四个组合操作 关系代数运算的应用实例 关系代数的七个扩充操作 返回

关系代数的五个基本操作 (1) 差（Difference） 并（Union） 设关系R和S具有相同的关系模式，R和S的并是由属于R或属于S的元组构成的集合，记为R∪S。形式定义如下： R∪S≡{t | t∈R ∨ t∈S}，t是元组变量，R和S的元数相同。 差（Difference） 设关系R和S具有相同的关系模式，R和S的差是由 属于R但不属于S的元组构成的集合，记为R－S。形式定义如下： R－S≡{ t | t∈R ∧ t∈S}，R和S的元数相同。

关系代数的五个基本操作 (2) 笛卡尔积（Cartesian Product） R×S≡{t|t＝<tr，ts>∧tr∈R∧ts∈S} tr、ts中r，s为上标。若R有m个元组，S有n个元组，则R×S有m×n个元组。

关系代数的五个基本操作 (2) πi1，…，im（R）≡ {t|t＝〈ti1，…，tim〉∧〈t1，…，tk〉∈R} 投影（Projection）（对关系进行垂直分割） πi1，…，im（R）≡ {t|t＝〈ti1，…，tim〉∧〈t1，…，tk〉∈R} 例如，π3，1（R）表示新关系中第1列为R的第3列，新关系的第2列为R的第1列。如果R的每列标上属性名，那么操作符π的下标处也可以用属性名表示。例如，关系R（A，B，C），么πC，A（R）与π3，1（R）是等价的。

2.2.1 关系代数的五个基本操作 (3) 选择（Selection）（据条件对关系做水平分割） σF（R）＝{ t | t∈R ∧ F（t）= true } σ2＞ˊ3ˊ（R）表示从R中挑选第2个分量值大于3的元组所构成的关系。书写时，为了与属性序号区别起见，常量用引号括起来，而属性序号或属性名不要用引号括起来。

关系代数的五个基本操作 (例) 有两个关系R和S，（a）、（b）表示R∪S和R－S。（c）表示R×S，此处R和S的属性名相同，就应在属性名前注上相应的关系名，例如R.A、S.A等。图2.13的（d）表示πC，A（R），即π3，1（R）。（e）表示σB=ˊbˊ（R）。 （a）关系R （b）关系S

关系代数的五个基本操作 (例) σB='b'（R） πC，A（R） R∪S R－S R×S 关系代数操作的结果 返回

关系代数的四个组合操作 (1) 交（intersection） 关系R和S的交是由属于R又属于S的元组构成的集合，记为R∩S，这里要求R和S定义在相同的关系模式上。形式定义如下： R∩S≡{t︱t∈R ∧ t∈S}，R和S的元数相同。 由于R∩S = R-（R-S），或R∩S = S-（S-R），因此交操作不是一个独立的操作。 在图2.12中，R∩S的结果是只有一个元组 （d，a，f）。

关系代数的四个组合操作 (2) 连接（join） θ连接 F连接 R S≡{t︱t=<tr，ts>∧tr∈R∧ts∈S∧triθtsj} F连接 F连接是从关系R和S的笛卡尔积中选取属性间满足某一公式F的元组, 这里F是形为F1∧F2∧…∧Fn的公式，每个FP是形为iθj的式子，而i和j分别为关系R和S的第i、第j个分量的序号。 iθj

θ连接和F连接的例子 A B C D E 1 2 3 4 5 6 7 8 9 (a)关系R (b)关系S (c) R S (d) R S 2<1 2<1∧1≥2

关系代数的四个组合操作 (3) R S≡ π去掉S中的公共属性(σ公共属性上值相等(R×S)) 关系R和S的自然连接操作计算过程如下： 自然连接（natural join） 关系R和S的自然连接操作计算过程如下： R S≡ π去掉S中的公共属性(σ公共属性上值相等(R×S))

自然连接的例子 A B C D a b c d e f （a）关系R （b）关系S （c）R S

关系代数的四个组合操作 (4) 除法（division） R÷S≡π1，2，…，r-s(R) 设关系R和S的元数分别为r和s（设r>s>0），那么R÷S是一个（r-s）元的元组的集合。（R÷S）是满足下列条件的最大关系：其中每个元组t与S中每个元组u组成的新元组<t，u>必在关系R中。 R÷S≡π1，2，…，r-s(R) -π1，2，…，r-s((π1，2，…，r-s(R)×S)-R) 返回

除法操作的例子 R P1 R÷P1 S1 BAO C1 DB C2 OS S2 GU C3 P2 S3 AN C4 MIS S4 LI SNO SNAME CNO CNAME P1 R÷P1 S1 BAO C1 DB C2 OS S2 GU C3 P2 S3 AN C4 MIS S4 LI R÷P2 P3 R÷P3

2.2.3 关系代数运算的应用实例 例2.7 设教学数据库中有三个关系： 学生关系 S（S#，SNAME，AGE，SEX） 在关系代数运算中，把由五个基本操作经过有限次复合的式子称为关系代数表达式。这种表达式的运算结果仍是一个关系。我们可以用关系代数表达式表示各种数据查询操作。 例2.7 设教学数据库中有三个关系： 学生关系 S（S#，SNAME，AGE，SEX） 选课关系 SC（S#，C#，GRADE） 课程关系 C（C#，CNAME，TEACHER） 返回

S（S#，SNAME，AGE，SEX） SC（S#，C#，GRADE） πS#，GRADE（σC#='C2'（SC）） 表达式中也可以不写属性名，而写上属性的序号： π1，3（σ2='C2'（SC）） ⑵ 检索学习课程号为C2的学生学号与姓名。 πS#，SNAME（σC#='C2'（S⋈SC）） 由于这个查询涉及到两个关系S与SC，因此先要对这两个关系进行自然联接操作，然后再执行选择和投影操作。

S（S#，SNAME，AGE，SEX） SC（S#，C#，GRADE） C（C#，CNAME，TEACHER） ⑶ 检索选修课程名为MATHS的学生学号与姓名。 πS#，SNAME（σCNAME='MATHS'（S⋈SC⋈C）） ⑷ 检索选修课程号为C2或C4的学生学号。 πS#（σC#='C2'∨C#='C4'（SC）） ⑸ 检索至少选修课程号为C2和C4的学生学号。 π1（σ1=4∧2='C2'∧5='C4'（SC×SC）） 这里（SC×SC）表示关系SC自身相乘的笛卡尔积操作。

S（S#，SNAME，AGE，SEX） SC（S#，C#，GRADE） πSNAME，AGE(S)－πSNAME，AGE(σC#='C2'(S⋈SC)) 这里要用到集合差操作。先求出全体学生的 姓名和年龄，再求出学了C2课的学生的姓名 和年龄，最后执行两个集合的差操作。 πSNAME，AGE(σC#≠'C2'(S⋈SC))

S（S#，SNAME，AGE，SEX） SC（S#，C#，GRADE） C（C#，CNAME，TEACHER） ⑺ 检索学习全部课程的学生姓名。 ·学生选课情况可用操作πS#，C#(SC)表示； ·全部课程可用操作 πC#(C) 表示； ·学了全部课程的学生学号可用除法操作表示，操作结果是学号S#集：πS#，C#(SC)÷πC#(C) ·从S#求学生姓名SNAME，可以用自然联接和投影操作组合而成： πSNAME(S (πS#，C#(SC)÷πC#(C)))

⑻ 检索所学课程包含学生S3所学课程的学生学号。 ·学生选课情况可用操作πS#，C#(SC)表示； SC（S#，C#，GRADE） ⑻ 检索所学课程包含学生S3所学课程的学生学号。 ·学生选课情况可用操作πS#，C#(SC)表示； ·学生S3所学课程可用操作πC#(σS#='S3'(SC)) 表示； ·所学课程包含学生S3所学课程的学生学号，可以用除法操作求得： πS#，C#(SC)÷πC#(σS#='S3'(SC))

2.2.4 关系代数的七个扩充操作 改名 广义投影 赋值 外连接（outer join） 外部并（outer union） 半连接（semijoin） 聚集操作 返回

外连接（outer join） (a)关系R (b)关系S (c)R S (d)R S （e）R S （f）R S A B C D a b g null (a)关系R (b)关系S (c)R S (d)R S A B C D a b c d e f null g （e）R S （f）R S

外部并（outer union） A B C D a b c d null f e g (a)关系R (b)关系S (c) R和S的外部并

半连接（semijoin） R S ≡ πR（R S） A B C D a b c d e f (a)关系R (b)关系S (c) R S (d)R S (e)S R

2.3 关系演算 把数理逻辑的谓词演算引入到关系运算中，就可得到以关系演算为基础的运算。关系演算又可分为元组关系演算和域关系演算，前者以元组为变量，后者以属性（域）为变量。 2.3.1 元组关系演算 2.3.2 域关系演算 2.3.3 关系运算的安全约束和等价性 返回

2.3.1 元组关系演算 (1) 在元组关系演算（Tuple Relational Calculus）中，元组关系演算表达式简称为元组表达式，其一般形式为 { t | P（t）} 其中，t是元组变量，表示一个元数固定的元组；P是公式，在数理逻辑中也称为谓词，也就是计算机语言中的条件表达式。{ t | P（t）}表示满足公式P的所有元组t的集合。

2.3.1 元组关系演算 (2) 在元组表达式中，公式由原子公式组成。 定义2.4 原子公式（Atoms）有下列三种形式： ① R（s） 2.3.1 元组关系演算 (2) 在元组表达式中，公式由原子公式组成。 定义2.4 原子公式（Atoms）有下列三种形式： ① R（s） ② s[i]θu[j] ③ s[i]θa或aθu[j]。 在定义关系演算操作时，要用到“自由”（Free）和“约束”（Bound）变量概念。在一个公式中，如果元组变量未用存在量词∃或全称量词符号定义，那么称为自由元组变量，否则称为约束元组变量。

2.3.1 元组关系演算 (3) 定义2.5 公式（Formulas）的递归定义如下： ①每个原子是一个公式。其中的元组变量是自由变量。 2.3.1 元组关系演算 (3) 定义2.5 公式（Formulas）的递归定义如下： ①每个原子是一个公式。其中的元组变量是自由变量。 ② 如果P1和P2是公式，那么┐P1、P1∨P2、P1∧P2和P1P2也都是公式。 ③ 如果P1是公式，那么（s）（P1）和（s）（P1）也都是公式。 ④ 公式中各种运算符的优先级从高到低依次为：θ，和，┐，∧和∨，。在公式外还可以加括号，以改变上述优先顺序。 ⑤ 公式只能由上述四种形式构成，除此之外构成的都不是公式。

R5={t|(u)(v)(R(u)∧S(v) 2.3.1 元组关系演算 (4) 例2.16 图2.20的（a）、（b）是关系R和S，（c）～（g）分别是下面五个元组表达式的值： R1={t|S(t)∧t[1]>2} R2={t|R(t)∧┐S(t)} R3={t|(u)(S(t)∧R(u)∧t[3]<u[2])} R4={t|(u)(R(t)∧S(u)∧t[3]>u[1])} 图2.20 元组关系演算的例子 R5={t|(u)(v)(R(u)∧S(v) ∧u[1]>v[2]∧t[1]=u[2] ∧t[2]=v[3]∧t[3]=u[1])}

2.3.1 元组关系演算 (5) ① P1∧P2 等价于 ┐(┐P1∨┐P2)； P1∨P2 等价于 ┐(┐P1∧┐P2)。 2.3.1 元组关系演算 (5) 在元组关系演算的公式中，有下列三个等价的转换规则： ① P1∧P2 等价于 ┐(┐P1∨┐P2)； P1∨P2 等价于 ┐(┐P1∧┐P2)。 ② (s)(P1(s)) 等价于 ┐(s)(┐P1(s))； (s)(P1(s)) 等价于 ┐(s)(┐P1(s))。 ③ P1P2 等价于 ┐P1∨P2。

2.3.1 元组关系演算 (6) 关系代数表达式到元组表达式的转换 例2.17 R∪S可用{ t | R（t）∨S（t）}表示； 2.3.1 元组关系演算 (6) 关系代数表达式到元组表达式的转换 例2.17 R∪S可用{ t | R（t）∨S（t）}表示； R-S可用{ t | R（t）∧┐S（t）} 表示； R×S可用{ t |（u）（v）（R（u）∧S(V) ∧t[1]=u[1] ∧t[2]=u[2]∧t[3]=u[3]∧t[4]=v[1] ∧t[5]=v[2] ∧t[6]=v[3]）} 表示。 设投影操作是π2,3（R），那么元组表达式可写成： { t |(u)（R（u）∧t[l]=u[2]∧t[2]=u[3]）} σF（R）可用{ t |R(t)∧F'}表示，F'是F的等价表示形式。譬如σ2='d'（R）可写成{ t |（R（t）∧t[2]='d'）。 返回

例2.18 设关系R和S都是二元关系， π1,4（σ2=3（R×S）） {t|(u)(v)(R(u)∧S(v)∧t[1]=u[1]∧t[2]=u[2] ∧t[3]=v[1]∧t[4]=v[2])} ⑵ σ2=3（R×S）: 在上述表达式的公式中加上“∧t[2]=t[3]”即可。 ⑶ π1,4（σ2=3（R×S））: {w|(t)(u)(v)(R(u)∧S(v)∧t[1]=u[1]∧t[2]=u[2] ∧t[3]=v[1]∧t[4]=v[2]∧t[2]=t[3] ∧w[1]=t[1]∧w[2]=t[4])} ⑷ 再对上式化简，去掉元组变量t，可得下式： {w|(u)(v)(R(u)∧S(v) ∧u[2]=v[1]∧w[1]=u[1]∧w[2]=v[2])}

例2.19 对于例2.7中查询语句的关系代数表达式形式也可以用元组表达式形式表示： 例2.19 对于例2.7中查询语句的关系代数表达式形式也可以用元组表达式形式表示： ⑴ 检索学习课程号为C2的学生学号与成绩。 πS#，GRADE（σC#='C2'（SC）） {t|(u)(SC(u)∧u[2]='C2'∧t[l]=u[1] ∧t[2]=u[3])} ⑵ 检索学习课程号为C2的学生学号与姓名。 πS#，SNAME（σC#='C2'（S⋈SC）） {t|(u)(v)(S(u)∧SC(v)∧v[2]='C2‘ ∧u[l]=v[1]∧t[l]=u[1]∧t[2]=u[2])}

例2.19 对于例2.7中查询语句的关系代数表达式形式也可以用元组表达式形式表示： 例2.19 对于例2.7中查询语句的关系代数表达式形式也可以用元组表达式形式表示： ⑶检索选修课程名为MATHS的学生学号与姓名。 πS#，SNAME（σCNAME='MATHS'（S⋈SC⋈C）） {t|(u)(v)(w)(S(u)∧SC(v)∧C(w) ∧u[l]=v[1]∧v[2]=w[1]∧w[2]='MATHS' ∧t[l]=u[1]∧t[2]=u[2])} ⑷ 检索选修课程号为C2或C4的学生学号。 πS#（σC#='C2'∨C#='C4'（SC）） {t|(u)(SC(u)∧(u[2]='C2'∨u[2]='C4') ∧t[l]=u[1])}

例2.19 对于例2.7中查询语句的关系代数表达式形式也可以用元组表达式形式表示： 例2.19 对于例2.7中查询语句的关系代数表达式形式也可以用元组表达式形式表示： ⑸ 检索至少选修课程号为C2和C4的学生学号。 π1（σ1=4∧2='C2'∧5='C4'（SC×SC）） {t|(u)(v)(SC(u)∧SC(v)∧u[2]='C2' ∧v[2]='C4'∧u[l]=v[1]∧t[l]=u[1])} ⑹ 检索不学C2课的学生姓名与年龄。 πSNAME，AGE（S）－πSNAME，AGE（σC#='C2'（S⋈SC）） {t|(u)(v)(S(u)∧SC(v) ∧(u[l]=v[1]v[2]≠'C2‘) ∧t[1]=u[2]∧t[2]=u[3])}

例2.19 对于例2.7中查询语句的关系代数表达式形式也可以用元组表达式形式表示： 例2.19 对于例2.7中查询语句的关系代数表达式形式也可以用元组表达式形式表示： ⑺ 检索学习全部课程的学生姓名。 πSNAME（S⋈（πS#，C#（SC）÷πC#（C））） {t|(u)(v)(w)(S(u)∧C(v)∧SC(w) ∧u[l]=w[1]∧v[1]=w[2]∧t[1]=u[2])} ⑻ 检索所学课程包含学号S3所学课程的学生。 πS#，C#（SC）÷πC#（σS#='S3'（SC）） {t|(u)(SC(u)∧(v)(SC(v)∧ (v[1]='S3' (w)(SC(w)∧w[1]=u[1]∧w[2]=v[2]))) ∧t[l]=u[1])}

2.3.2 域关系演算 (1) 原子公式有两种形式： ⑴ R（x1…xk）； ⑵ xθy。 2.3.2 域关系演算 (1) 原子公式有两种形式： ⑴ R（x1…xk）； ⑵ xθy。 公式中也可使用∧、∨、┐和等逻辑运算符,(x)和（x），但变量x是域变量，不是元组变量。 自由域变量、约束域变量等概念和元组演算中一样。 域演算表达式是形为 ｛t1…tk∣P（t1，…，tk）｝ 的表达式，其中P（t1，…，tk）是关于自由域变量t1，…，tk 的公式。

2.3.2 域关系演算 (2) 例2.20 图2.21的（a）、（b）、（c）是三个关系R、S、W，（d）、（e）、（f）分别表示下面三个域表达式的值。 (a)关系R (b)关系S (c)关系W (d)R1 (e)R2 (f)R3 图2.21 域关系演算的例子 R1={xyz|R(xyz)∧x<5∧y>3} R2={xyz|R(xyz)∨(S(xyz)∧y=4)} R3={xyz|(u)(v)(R(zxu)∧w(yv)∧u>v)}

2.3.2 域关系演算 (3) 元组表达式到域表达式的转换 我们可以很容易地把元组表达式转换成域表达式，转换规则如下： 2.3.2 域关系演算 (3) 元组表达式到域表达式的转换 我们可以很容易地把元组表达式转换成域表达式，转换规则如下： ⑴ 对于k元的元组变量t，可引入k个域变量t1…tk，在公式中t用t1…tk替换，元组分量t[i]用ti替换。 ⑵ 对于每个量词（u）或（u），若u是m元的元组变量，则引入m个新的域变量u1…um。 在量词的辖域内，u用u1…um替换，u[i]用ui替换，（u）用（u1）…（um）替换，（u）用（u1）…（um）替换。 返回

例2.18 设关系R和S都是二元关系， π1,4（σ2=3（R×S）） 例2.18 转换成的元组表达式： {w|(u)(v)(R(u)∧S(v)∧u[2]=v[1] ∧w[1]=u[1]∧w[2]=v[2])} 再转换成域表达式： {w1w2|(u1)(u2)(v1)(v2)(R(u1u2)∧S(v1v2) ∧u2=v1 ∧w1=u1 ∧w2=v2)} 再进一步简化，可消去域变量u1、v1、v2，得到下式： {w1w2|(u2)(R(w1u2)∧S(u2w2))}

例2.22 对于例2.7、例2.19的查询，可转换成下列域表达式： ⑴ 检索学习课程号为C2的学生学号与成绩。 {t1t2|(u1)(u2)(u3)(SC(u1u2u3)∧u2='C2‘ ∧t1=u1∧t2=u3)} 可化简为：{t1t2|SC(t1'C2't2)} ⑵ 检索学习课程号为C2的学生学号与姓名。 {t1t2|(u1)(u2)(u3)(u4)(v1)(v2)(v3) (S(u1u2u3u4)∧SC(v1v2v3)∧v2='C2‘ ∧u1=v1∧t1=u1∧t2=u2)} 可化简为： {t1t2|(u3)(u4)(v3) (S(t1t2u3u4)∧SC(t1'C2'v3))}

2.3.3关系运算的安全约束和等价性 定义2.6 在数据库技术中，不产生无限关系和无穷验证的运算称为安全运算，相应的表达式称为安全表达式，所采取的措施称为安全约束。 并、差、笛尔卡积、投影和选择是关系代数最基本的操作，并构成了关系代数运算的最小完备集。已经证明，在这个基础上，关系代数、安全的元组关系演算、安全的域关系演算在关系的表达和操作能力上是完全等价的。 返回

关系运算的安全性 元组表达式{t|┐R（t）}，这是一个无限关系。 验证公式(u)(P1(u))为假时，必须对所有可能的元组u进行验证，当所有的u都使P1(u)为假时，才能断定公式(u)(P1(u))为假。 验证公式(u)(P1(u))也是这样，当所有可能的u使P1(u)为真时，才能断定公式(u)(P1(u))为真。这在实际上是行不通的。 我们必须采取措施，防止无限关系和无穷验证的出现。

关系运算的安全性（续） 对于元组表达式{t|P（t）}，将公式P(t)的“域”（Domain）定义为出现在公式P(t)中的常量和关系的所有属性值组成的集合，记为DOM(P(t))。 由于所有关系都是有限的，因此DOM(P)也是有限的。 例如P(t)是t[1]='a'∨R（t），R是二元关系，那么DOM(P)={a}∪π1（R）∪π2（R）。

关系运算的安全性（续） 安全的元组表达式{t|P(t)}应满足下列三个条件： ①表达式的元组t中出现的所有值均来自DOM(P)。②对于P(t)中每个形如(u)(P1(u))的子公式，如果元组u使P1(u)为真，那么u的每个分量必是DOM(P1)的元素。换言之，如果u有某个分量不属于DOM(P1)，那么P1(u)必为假。 ③对于P(t)中每个形如(u)(P1(u))的子公式，如果元组u使P1(u)为假，那么u的每个分量必是DOM(P1)的元素。换言之，如果u有某个分量不属于DOM(P1),那么P1(u)必为真。

关系运算的等价性 ISBL（Information System Base Language）语言与关系代数非常接近。 QUEL语言（Query Language）是一种基于元组关系演算的数据语言。 QBE（Query By Example,按例查询）是一种特殊的屏幕编辑语言。是一种域演算语言，现在，QBE的思想已渗入到许多DBMS中。 SQL（Structured Query Language）是介乎于关系代数和元组演算之间的一种关系查询语言，现已成为关系数据库的标准语言，我们将在第3章详细介绍。

2.4 关系代数表达式的优化 2.4.1 关系代数表达式的优化问题 2.4.2 关系代数表达式的等价变换规则 2.4.3 关系代数表达式的优化算法 返回

2.4.1 关系代数表达式的优化(1) 在关系代数表达式中需要指出若干关系的操作步骤。那么，系统应该以什么样的操作顺序，才能做到既省时间，又省空间，而且效率也比较高呢？这个问题称为查询优化问题。 在关系代数运算中， 笛卡儿积和连接运算 是最费时间的。

2.4.1 关系代数表达式的优化(2) E1 = πA（σB=C∧D='99'（R×S）） 例2.23 设关系R和S都是二元关系，属性名分别为A，B和C，D。 E1 = πA（σB=C∧D='99'（R×S）） E2 = πA（σB=C（R×σD='99'（S）） E3 = πA（R ⋈ σD='99'（S）） 这三个关系代数表达式是等价的，但执行的效率大不一样。显然，求El，E2，E3的大部分时间是花在连接操作上的。 B=C 返回

2.4.2 等价变换规则 (1) 连接和笛卡尔积的交换律 连接和笛卡尔积的结合律 投影的级联 选择的级联 选择和投影操作的交换 2.4.2 等价变换规则 (1) 连接和笛卡尔积的交换律 连接和笛卡尔积的结合律 投影的级联 选择的级联 选择和投影操作的交换 选择对笛卡尔积的分配律 选择对并的分配律

2.4.2 等价变换规则 (2) 选择对集合差的分配律 选择对自然连接的分配律 投影对笛卡尔积的分配律 投影对并的分配律 2.4.2 等价变换规则 (2) 选择对集合差的分配律 选择对自然连接的分配律 投影对笛卡尔积的分配律 投影对并的分配律 选择与连接操作的结合 并和交的交换律 并和交的结合律 返回

2.4.3 优化算法 (1) ·尽可能早地执行选择操作； ·尽可能早地执行投影操作； 2.4.3 优化算法 (1) 在关系代数表达式中，最花费时间和空间的运算是笛卡尔积和连接操作，为此，引出三条启发式规则，用于对表达式进行转换，以减少中间关系的大小。 ·尽可能早地执行选择操作； ·尽可能早地执行投影操作； ·避免直接做笛卡尔积，把笛卡尔积操作 之前和之后的一连串选择和投影合并起 来一起做。

2.4.3 优化算法 (2) 算法2.1 关系代数表达式的启发式优化算法。 输入：一个关系代数表达式的语法树 输出：计算表达式的一个优化序列 2.4.3 优化算法 (2) 算法2.1 关系代数表达式的启发式优化算法。 输入：一个关系代数表达式的语法树 输出：计算表达式的一个优化序列 方法：① 把每个形为σF1∧… ∧Fn（E）的子表达式转换成选择级联形式： σF1（…（σFn（E））…） ② 在语法树中，尽可能把每个选择操作下推到最早可能执行的地方（即移向树的叶端）。 ③ 对每个投影操作，尽可能往下推，移向树的叶端。 ④ 把选择和投影合并成单个选择、单个投影或一个选择后跟一个投影。 ⑤ 将上述步骤得到的语法树的内结点分组。每个二元运算（×、∪、－）结点与其直接祖先（不超过别的二元运算结点）的一元运算结点（σ或π）分为一组。 ⑥ 生成一个序列，每一组结点的计算是序列中的一步，各步的顺序是任意的，只要保证任何一组不会在它的子孙组之前计算。 返回

2.4.3 优化算法 (3) 例2.24 检索至少学习LIU老师所授一门课程的女学生学号和姓名。 该查询语句的关系代数表达式如下： 2.4.3 优化算法 (3) 例2.24 检索至少学习LIU老师所授一门课程的女学生学号和姓名。 该查询语句的关系代数表达式如下： πS#，SNAME(σTEACHER=’LIU’∧SEX=’F’(C⋈SC⋈S)) 上式中，符号用π、σ、×操作表示，可得下式： πS#，SNAME(σTEACHER=’LIU’∧SEX=’F’( πL(σC.C#=SC.C#∧SC.S#=S.S#(C×SC×S))))

2.4.3 优化算法 (4) 图2.22 关系代数表达式的初始语法树 π σ × S SC C S.S#，SNAME 2.4.3 优化算法 (4) S.S#，SNAME C.C#，CNAME，TEACHER，S.S#，GRADE，SNAME，AGE，SEX TEACHER='LIU'∧SEX='F' C.C#=SC.C#∧SC.S#=S.S# π σ × S SC C 图2.22 关系代数表达式的初始语法树

2.4.3 优化算法 (5) 图2.23 优化过程中的语法树 π σ × S SC C S.S#，SNAME SC.S#=S.S# 2.4.3 优化算法 (5) S.S#，SNAME SC.S#=S.S# π σ × S SC C 图2.23 优化过程中的语法树 SEX='F' C.C#=SC.C# TEACHER='LIU'

2.4.3 优化算法 (6) 图2.24 优化的语法树及其分组 π × σ S SC C S.S#，SNAME SC.S#=S.S# 2.4.3 优化算法 (6) σ S.S#，SNAME SC.S#=S.S# π × 图2.24 优化的语法树及其分组 S SC C SEX='F' C.C#=SC.C# TEACHER='LIU' SC.S# SC.S#，SC.C# C.C#

2.5 关系逻辑 (1) 2.5.1 关系运算的成分 2.5.2 规则的安全性 2.5.3 从关系代数到关系逻辑的转换 2.5.4 递归过程 2.5 关系逻辑 (1) 2.5.1 关系运算的成分 2.5.2 规则的安全性 2.5.3 从关系代数到关系逻辑的转换 2.5.4 递归过程 2.5.5 关系逻辑与关系代数的差异

2.5 关系逻辑 (2) 谓词 原子 关系逻辑中用谓词表示关系 外延谓词，其关系存储在数据库中的谓词称为外延谓词 2.5 关系逻辑 (2) 谓词 关系逻辑中用谓词表示关系 外延谓词，其关系存储在数据库中的谓词称为外延谓词 内涵谓词，由逻辑规则定义的谓词 原子 关系原子，谓词符号，带一个参数表 算数原子，算数比较表达式

2.5 关系逻辑 (2) 定义2.9 实际上，规则 W←P1∧P2∧…∧Pn， 就是逻辑蕴涵式 P1∧P2∧…∧Pn→W， 2.5 关系逻辑 (2) 定义2.9 实际上，规则 W←P1∧P2∧…∧Pn， 就是逻辑蕴涵式 P1∧P2∧…∧Pn→W， 即 if（P1∧P2∧…∧Pn）then W， 或者 ┐P1∨┐P2∨…∨┐Pn∨W。

2.5 关系逻辑 (3) 例2.28 设有关系R(A,B,C)和S(A,B,C)， 那么 R∩S 可用下列规则计算： 2.5 关系逻辑 (3) 例2.28 设有关系R(A,B,C)和S(A,B,C)， 那么 R∩S 可用下列规则计算： W(a,b,c)← R(a,b,c)∧S(a,b,c) 例2.29 那么 R∪S 可用下列规则计算： ① W(a,b,c)← R(a,b,c) ② W(a,b,c)← S(a,b,c) 例2.30 那么 R-S 可用下列规则计算： W(a,b,c)← R(a,b,c)∧┐S(a,b,c)

2.5 关系逻辑 (4) 例2.31 设有关系R(A,B,C) ， 那么πC，A（R）可用下列规则计算： W(c,a)← R(a,b,c) 2.5 关系逻辑 (4) 例2.31 设有关系R(A,B,C) ， 那么πC，A（R）可用下列规则计算： W(c,a)← R(a,b,c) 例2.32 设有关系R(A,B,C) ， 那么σB≥’5’∧ C=’18’(R)可以写成下列规则： W(a,b,c)← R(a,b,c)∧b≥'5'∧c='18' 例2.33 设有关系R(A,B,C) ， 那么σB≥’5’∨ C=’18’(R)可以用两个规则表示： ① W(a,b,c)← R(a,b,c)∧b≥'5' ② W(a,b,c)← R(a,b,c)∧c='18'

2.5 关系逻辑 (5) W(a,b,c,x,y,z)← R(a,b,c)∧S(x,y,z) 2.5 关系逻辑 (5) 例2.34 设有关系R(A,B,C)和S(D,E,F)， 那么 R×S 可用下列规则表示： W(a,b,c,x,y,z)← R(a,b,c)∧S(x,y,z) 例2.35 设有关系R(A,B,C)和S(C,D,E)， 那么 R⋈S 可用下列规则定义： W(a,b,c,d,e)← R(a,b,c)∧S(c,d,e)

2.5 关系逻辑 (6) 例2.36 对于例2.7中查询语句可以用关系逻辑的规则形式表示： ⑴ 检索学习课程号为C2的学生学号与成 绩。 2.5 关系逻辑 (6) 例2.36 对于例2.7中查询语句可以用关系逻辑的规则形式表示： ⑴ 检索学习课程号为C2的学生学号与成 绩。 W(a,h)← SC(a,'C2',h) ⑵ 检索学习课程号为C2的学生学号与姓 名。 W(a,b)←S(a,b,c,d)∧SC(a,'C2',h）

2.5 关系逻辑 (7) ⑶ 检索选修MATHS的学生学号与姓名。 W(a,b)← S(a,b,c,d)∧SC(a,e,h) 2.5 关系逻辑 (7) ⑶ 检索选修MATHS的学生学号与姓名。 W(a,b)← S(a,b,c,d)∧SC(a,e,h) ∧C(e,'MATHS',g） ⑷ 检索选修C2或C4的学生学号。 W(a)← SC(a,'C2',h) W(a)← SC(a,'C4',h) ⑸ 检索至少选修C2和C4的学生学号。 W(a)← SC(a,'C2',h)∧SC(a,'C4‘,h)

2.5 关系逻辑 (8) ⑹ 检索不学C2课的学生姓名与年龄。 W(b,c)← S(a,b,c,d)∧┐SC(a,'C2',h) 2.5 关系逻辑 (8) ⑹ 检索不学C2课的学生姓名与年龄。 W(b,c)← S(a,b,c,d)∧┐SC(a,'C2',h) ⑺ 检索学习全部课程的学生姓名。 W(b)←S(a,b,c,d)∧(C(e,f,g)=> SC(a,e,h)) ⑻ 检索所学课程包含学生S3所学课程 的学生学号。 W(e)← SC(e,f,g)∧(SC('S3',x,y)=> SC(e,x,z))

小 结 在2.3.3节中提到关系代数和关系演算在表达功能上是等价的。那么关系代数和关系逻辑在表达功能上是否等价？已有文献证明，这两者之间相差甚大。在规则中没有否定时，关系代数与关系逻辑在表达功能方面已不相适应，每个都能表达另一个不能表达的内容。在规则中带有否定时，关系逻辑比关系代数更富于表现力。只有在规则被约束为安全的、非递归的、在带有某些否定的情况下，关系代数才与关系逻辑等价。由于关系逻辑中引进了基于逻辑的规则概念，使得关系逻辑比关系代数在模拟现实世界能力方面更强。关系逻辑一般是用在知识库的知识表达中。

本章的重点篇幅 （1）教材中P56的例2.7 （关系代数表达式的应用实例）。 （2）教材中P63的例2.19 （关系逻辑的规则表示）。

重要内容分析（一） （1）一般规则 ·对于只涉及到选择、投影、连接的查询可用下列表达式表示： π…（σ…（R×S）） ·对于否定的操作，一般要用差操作表示，例如“检索不学C2课的学生姓名”。 ·对于检索具有“全部”特征的操作，一般要用除法操作表示，例如“检索学习全部课程的学生姓名”。

重要内容分析（二） πSNAME，AGE(σC#≠'C2'(S SC)) 决不能用下式表示： πSNAME，AGE(σC#≠'C2'(S SC)) 一定要用“差”的形式： πSNAME，AGE(S)－πSNAME，AGE(σC#='C2'(S SC)) （3）“检索学习全部课程的学生学号”， 要用πS#，C#（SC）÷πC#（C）表示， 而不能写成 πS# （SC÷πC#（C））形式。这是因为一个学生学的课程的成绩可能是不一样的。

重要内容分析（三） 2．非过程性语言与过程性语言的区别 编程时必须指出“干什么”及“怎么干”的语言，称为过程性语言； 编程时只须指出“干什么”，不必指出“怎么干”的语言，称为非过程性语言。