数据库原理及应用

第4章关系数据库方法

本章主要内容

　本章将主要介绍关系数据数据库的基本概念，关系运算和关系表达式的优化问题，其中关系运算和关系表达式的优化问题是本课程的重点内容之一。关系运算是关系数据模型的理论基础。

（1）基本概念

关系形式定义，关键码（主键和外键），三类完整性规则，关系模式、关系子模式和存储模式。

（2）关系代数

五个基本操作及其组合操作。

（3）关系演算

元组关系演算和域关系演算的原子公式、公式的定义。关系演算的安全性和等价性。

（4）关系代数表达式的优化

关系代数表达式的等价及等价转换规则，启化式优化算法。

关系数据库方法

4.1 关系数据库的基本概念

4.2 关系代数

4.3 关系演算

4.4 关系查询优化

本章小结

4.1 关系数据库的基本概念

4.1.1　关系的形式化定义

4.1.2　关系模式、关系子模式和存储模式

4.1.3 关系模型的完整性规则

4.1.4 关系数据库模式

4.1.1 关系的形式化定义(1)

1）关系的集合表示

一个关系由若干个不同元组组成，因此，可把关系视为元组的集合。此外，关系中每个属性都有其相应的值域或简称域(Domain)。

例如，学生性别的域是｛男，女｝，学生成绩的域是0~100的整数集合。

假设一组域，是由D_¹,D_²，…,D_ⁿ n个域组成。D_¹,D_²，…,D_ⁿ上的D_¹×D_²×…×D_ⁿ定义为集合：

D_¹×D_²×…×D_ⁿ＝｛(d_¹, d_^2,,…,d_ⁿ) ｜d_ⁱ∈D_ⁱ，i=1，2，…，n｝

其中:每个元素(d_¹，d_²，…，d_ⁿ)称为一个元组。

若D_ⁱ（i=1,2,…,n）为有限集，其基数为m_ⁱ（i=1,2，…，n)

则D_¹×D_²×…×D_ⁿ的基数为：

4.1.1 关系的形式化定义(2)

【例4-1】设有二个域教师名域T＝｛胡恒，丁伟｝、课程名域C＝｛C语言，数据结构，计算机原理｝，由T和C的笛卡儿积定义为集合：

T×C＝｛（胡恒，C语言），（胡恒，数据结构），（胡恒，计算机原理），

（丁伟，C语言），（丁伟，数据结构），（丁伟，计算机原理）｝

该笛卡儿积的基数为2×3＝6，也就是说，T×C一共2×3＝6个元组.

4.1.1 关系的形式化定义(3)

如果取该笛卡儿积的这六个元素，并将它们放到一张名为T_C的二维表中，

显然，这是一个关系。于是有下面的定义4-1。

4.1.1 关系的形式化定义(4)

定义4-1：一个在域D¹,D²，…,Dⁿ上的关系(Relation)就是笛卡儿积D¹×D²×…×Dⁿ的子集，用R(D¹,D²，…,Dⁿ)表示,　R D¹×D²×…×Dⁿ。

关系的成员为元组，即笛卡儿积的子集的元素(d¹，d²，…，dⁿ)。　

例如，我们用教师名代替教师（假设无同名教师存在），用课程名代替课程，教师任教的课程可用关系TC（教师，课程）表示，它是教师名域和课程名域的笛卡儿积T×C的子集，任一学期教师任教的课程记录是这个关系的元组，如：

TC＝｛（胡恒，C语言），（丁伟，数据结构）｝表示本学期胡恒老师上C语言课程，丁伟老师上数据结构课程。

4.1.1 关系的形式化定义(5)

2）关系的一阶谓词表示

关系模型不但可以用关系代数表示，还可以用一阶谓词演算表示。

定义4-2：设有关系模式R，其原子谓词表示形式为P (t)。其中，P是谓词，t为个体变元，以元组为其表现形式。关系R(元组的集合)与谓词P (t)之间的联系描述为：

R＝｛t｜P (t)｝,

表示所有使谓词P为真或满足谓词P的元组t都属于关系R。

关系R与原子谓词P之间的关系如下：

P(t)＝True，t在R内, P(t)＝Fals，t不在R内。

例：｛t[姓名]｜t∈Student AND t.性别＝‘女’ ｝

4.1.1 关系的形式化定义(6)

职工编号

姓名

部门

性别

年龄

身份证号码

2113

程晓清

销售部

男

310110720306405

2116

刘红英

财务部

女

310110700508506

2136

李小刚

管理部

男

310110740609507

2138

蒋民

采购部

男

310110610808406

2141

王国洋

销售部

男

310110630909407

表4.1 职工表（实体集）

可将关系看成是一张二维表格。

(1)关系（表）可以看成是由行和列(5行和6列）交叉组成的二维表格。

(2)表中一行称为一个元组。可用来表示实体集中的一个实体。

(3)表中的列称为属性，表中的属性名不能相同。

(4)列的取值范围称为域，同列具有相同的域，不同的列可有相同的域

(5)表中任意两行（元组）不能相同。能惟一标识表中不同行的属性或属性组称为主键。

4.1.1 关系的形式化定义(7)

3）关键码和表之间的联系

在关系数据库中，关键码（简称键）是关系模型的一个重要概念。通常键由一个或几个属性组成，通常有如下几种键：

(1)超键：

在一个关系中，能惟一标识元组的属性或属性集称为关系的超键。

(2)候选键：

如果一个属性集能唯一标识元组，且又不含有多余的属性，那么这个属性集称为关系的候选键。

(3)主键：

若一个关系中有多个候选键，则选其中的一个为关系的主键。用主键实现关系定义中“表中任意两行（元组）不能相同”的约束。包含在任何一个候选键中的属性称为主属性，不包含在任何键中的属性称为非主属性或非键属性。

4.1.1 关系的形式化定义(8)

职工编号

姓名

部门

性别

年龄

身份证号码

2113

程晓清

销售部

男

310110720306405

2116

刘红英

财务部

女

310110700508506

2136

李小刚

管理部

男

310110740609507

2138

蒋民

采购部

男

310110610808406

2141

王国洋

销售部

男

310110630909407

表4.1 职工表（实体集）

例如：表4.1的关系中，设属性集K=（职工编号，部门），虽然K能惟一标识职工，但K只能是关系的超键，还不能作候选键使用。因为K中“部门”是一个多余属性，只有“职工编号”能惟一标识职工。因而“职工编号”是一个候选键。

还有“身份证号”也可以是一个候选键。

另外，如果规定“不允许有同名同姓的职工”，那么“姓名”也可以是一个候选键。

关系的候选键可以有多个，但不能同时使用，只能使用一个，譬如使用“职工编号”来标识职工，那么“职工编号”就是主键了。

4.1.1 关系的形式化定义(9)

(4)外键：

若一个关系R中包含有另一个关系S的主键所对应的属性集F,则称F为R的外键。并称关系S为参照关系，关系R为依赖关系。

例如，职工关系和部门关系分别为：

职工（职工编号，姓名，部门编号，性别，年龄，身份证号码）

部门（部门编号，部门名称，部门经理）

职工关系的主键为职工编号，部门关系的主键为部门编号，在职工关系中，部门编号是它的外键。

4.1.2 关系模式、关系子模式和存储模式

关系模型基本上遵循数据库的三级体系结构。在关系模型中，概念模式是关系模式的集合，外模式是关系子模式的集合，内模式是存储模式的集合。

1）关系模式

关系模式是对关系的描述，它包括模式名，组成该关系的诸属性名、值域名和模式的主键。具体的关系称为实例。

一般形式是R(A_¹,A_²，…,A_ⁿ)，其中R是关系名, A_¹,A_²，…,A_ⁿ是该关系的属性名。

例如关系模式T_C(T,C)。

4.1.2 关系模式、关系子模式和存储模式

学生关系模式S(SNO, SNAME，AGE, SEX, DNAME)

课程关系模式C（CNO, CNAME，DNAME, TNAME）

选课关系模式SC(SNO, CNO, SCORE)

图4.1表示的实体联系图(ER图)转换成关系模式集如下：

学生

课程

选课

学号

姓名

性别

年龄

成绩

所在系

课程号

课程名

所在系

教师

例如，图4.1是一个教学模型的实体联系图。

4.1.2 关系模式、关系子模式和存储模式

学生关系S

SNO

SNAME

AGE

SEX

DNAME

程宏

男

计算机

刘莎莎

女

电子

李刚

男

自动化

蒋天峰

男

电气

王敏

女

计算机

CNO

CNAME

DNAME

TNAME

计算机基础

计算机

孙立

C语言

计算机

胡恒

电子学

电子

钱敏

数据结构

计算机

丁伟

课程关系C

关系模式是用数据定义语言(DDL)定义的。关系模式的定义包括：模式名、属性名、值域名以及模式的主键。由于不涉及到物理存储方面的描述，因此关系模式仅仅是对数据本身的特征的描述。

SNO

CNO

SCORE

选课关系SC

SNO

SNAME

AGE

SEX

DNAME

程宏

男

计算机

刘莎莎

女

电子

…

SNO

CNO

SCORE

…

4.1.2 关系模式、关系子模式和存储模式

SNO

SNAME

CNO

SCORE

程宏

刘莎莎

…

2）关系子模式

有时，用户使用的数据不直接来自关系模式中的数据，而是从若干关系模式中抽取满足一定条件的数据。这种结构可用关系子模式实现。

关系子模式是用户所需数据的结构的描述，其中包括这些数据来自哪些模式和应满足哪些条件。

例如：用户需要用到成绩子模式G(SNO, SNAME, CNO, SCORE)。子模式G对应的数据来源于表S和表SC,构造时应满足它们的SNO值相等。子模式G的构造过程如图所示。

3）存储模式

存储模式描述了关系是如何在物理存储设备上存储的。关系存储时的基本组织方式是文件。由于关系模式有键，因此存储一个关系可以用散列方法或索引方法实现。如果关系中元组数目较少（100以内），那么也可以用堆文件方式实现．此外，还可以对任意的属性集建立辅助索引。

4.1.2 关系模式、关系子模式和存储模式

SCORE

4.1.3 关系模型的完整性规则 (1)

关系模型的完整性规则是对数据的约束。关系模型提供了三类完整性规则，实体完整性规则、参照完整性规则、用户定义的完整性规则。其中实体完整性规则和参照完整性规则是关系模型必须满足的完整性的约束条件，称为关系完整性规则。

1）实体完整性规则

实体完整性规则：关系中元组的主键值不能为空。

2）参照完整性规则

在关系数据库中，关系与关系之间的联系是通过公共属性实现的。这个公共属性是一个表的主键和另一个表的外键。外键必须是另一个表的主键的有效值，或者是一个“空值”。

4.1.3 关系模型的完整性规则 (2)

导师编号

导师姓名

性别

职称

301

程星

女

教授

308

刘成柄

男

副教授

316

吴海英

女

副教授

学号

学生姓名

性别

研究方向

导师编号

98104

程明

男

计算机

308

98106

刘英

女

电子

316

98107

韩伟海

男

自动化

98110

刘刚

男

计算机

318

导师

研究生

导师编号不允许

是重复值和空值

允许为空值

这是一个错误值

(引用了不存在的编码318)

例如，图4.4所示研究生表的主键是学号，不包含空的数据项；导师表的主键是导师编号，也不包含空的数据项，所以，这两个表都满足实体完整性规则。

而学号为“98110”的研究生的导师编号为“318”，由于导师表中不存在导师编号“318”，所以这个值是非法的，违反了参照完整性规则。

4.1.3 关系模型的完整性规则 (3)

3）用户定义的完整性规则

这是针对某一具体数据的约束条件，由应用环境决定。它反映某一具体应用所涉及的数据必须满足的语义要求。系统应提供定义和检验这类完整性的机制，以便用统一的系统方法处理它们，不再由应用程序承担这项工作。

例如学生成绩应该大于或等于零，职工的工龄应小于年龄，等等。

4.1.4 关系数据库模式(1)

一个关系数据库是多个关系的集合，这些具体关系构成了关系数据库的实例。由于每个关系都有一个模式，所以，构成该关系数据库的所有关系模式的集合构成了关系数据库模式。

例如，一个学生选课数据库系统的模式有下面三个关系模式构成：

S(SNO，SNAME，SEX，AGE，DNAME)

C(CNO，CNAME，PRE_CNO)

SC(SNO，CNO，SCORE）

4.1.4 关系数据库模式(2)

关系数据库管理系统一般向用户提供四种基本数据操纵功能：

(1)数据检索

数据检索是指按照用户指定的条件查询一个关系内的数据或多个关系间的数据。

(2)数据插入

在关系内插入一些新的元组。

(3)数据删除

在关系内删除一些元组。

(4)数据修改

　　该操作实际上可分解为两个更基本的操作：先删除要修改的元组，再将修改后的元组插入。

4.1.4 关系数据库模式(3)

上述四类数据操作的对象都是关系，这样，对关系模型的数据操纵可描述为：

（1）操纵对象是关系。

（2）基本操纵方式有五种：

属性指定，指定一个关系内的某些属性，确定二维表中的列。主要用于检索或定位。
元组选择，用一个逻辑表达式给出一个关系中满足此条件的那些元组，确定二维表中的行。主要用于检索或定位。
关系合并，将两个关系合并成一个关系。用以合并多张表，从而实现多张表间的检索和定位。
元组插入。在一个关系中添加一些元组，用以完成数据插入或修改。
元组删除。先确定所要删除的元组，然后将它（们）删除。用于数据删除或修改。

4.2 关系代数

4.2.1 关系代数的五个基本操作

4.2.2 关系代数的组合操作

4.2.3 关系代数表达式应用举例

4.2.1 关系代数的五个基本操作

关系代数操作集｛∪,－,× , σ,Π ｝是个完备的操作集，任何其他关系代数操作都可以用这五种操作来表示。

商品编号

品名

数量

2008230

冰箱

2008234

彩电

2007156

空调

(a）库存关系R

设关系R和S具有相同结构的关系模式，R和S的并是由属于R或属于S的元组构成的集合，记为R∪S。形式定义如下：

R∪S≡{t | t∈R ∨ t∈S}，t是元组变量，R和S的元数相同。

例如：有库存和进货两个表（见下表），要将两个表合并为一个表，可利用并运算来实现。

商品编号

品名

数量

2008214

电熨斗

2008310

微波炉

（b）进货关系S

商品编号

品名

数量

2008230

冰箱

2008234

彩电

2007156

空调

2008214

电熨斗

2008310

微波炉

（c）并运算R∪S结果

1）并（Union）

2）差（Difference）

设关系R和S具有相同结构的关系模式，R和S的差是由属于R但不属于S的元组构成的集合，记为R－S。形式定义如下：

R－S≡{ t | t∈R ∧ t? S}，R和S的元数相同。

考生号

20013211

20011231

20017156

20018124

20013610

(a)成绩合格考生号R

例如：有考生成绩合格者名单和身体不合格名单两个关系，按录取条件将成绩合格且身体健康的考生中产生录取名单关系。

(b)身体不合格考生号S

考生号

20011231

20018124

考生号

20013211

20017156

20013610

(c)差运算R－S结果

事例

表4.6 （a）WORKER(职工)

E＃

NAME

SALARY

AGE

DEPT＃

123

张国华

1800

462

李明

2500

263

刘英明

2100

068

王飞

2700

表4.6（b）MANAGER（经理）

E＃

NAME

SALARY

AGE

DEPT＃

068

王飞

2700

059

曾富

3200

表4.6（c）WORKER∪MANAGER

E＃

NAME

SALARY

AGE

DEPT＃

123

张国华

1800

462

李明

2500

263

刘英明

2100

068

王飞

2700

059

曾富

3200

表4.6（d）WORKER-MANAGER

E＃

NAME

SALARY

AGE

DEPT＃

123

张国华

1800

462

李明

2500

263

刘英明

2100

表4.8 MANAGER × DEPTINFO

NAME

SALARY

AGE

M.DEPT＃

D.DEPT＃

DNAME

DTASK

068

王飞

2700

技术部

产品设计

068

王飞

2700

市场部

产品销售

059

曾富

3200

技术部

产品设计

059

曾富

3200

市场部

产品销售

3）笛卡儿积(Cartesian Product)

表4.7 DEPTINFO（部门信息）

DEPT＃

DNAME

DTASK

技术部

产品设计

市场部

产品销售

表4.6（b）MANAGER（经理）

E＃

NAME

SALARY

AGE

DEPT＃

068

王飞

2700

059

曾富

3200

[例4.3]:假定部门信息存放在表DEPTINFO中（见表4-6），则表MANAGER与表DEPTINFO的笛卡儿积如表4.7所示。

笛卡儿积定义

设有关系R和S，它们分别是n目和m目关系（即它们的属性个数分别为n和m），分别有p和q个元组。则关系R,S经笛卡儿积运算的结果T是一个n＋m目关系，共有p×q个元组，这些元组是由R与S的元组组合而成的。

关系R与S的笛卡儿积记为R×S，形式定义如下：

4）选择运算(Selection)

这个操作是根据某些条件对关系做水平分割，即在一个关系内选择符合条件的元组称为选择运算。选择运算可表示为：

σ_^C（R）＝｛t｜t∈R∧C[t]=True｝

C表示逻辑条件表达式。这个表达式按以下规则组成：

①αθβ，其中α、β是属性名或常量，但α、β不能同为常量。θ是比较运算符，它可以是＜、≤、＞、≥、＝或≠。称αθβ为基本逻辑条件。

②由若干基本逻辑条件经过逻辑运算∧（与）、∨（或）、-（非）构成复合逻辑条件。

选择运算事例

表4.6 （a）WORKER(职工)

E＃

NAME

SALARY

AGE

DEPT＃

123

张国华

1800

462

李明

2500

263

刘英明

2100

068

王飞

2700

表4.9

E＃

NAME

SALARY

AGE

DEPT＃

462

李明

2500

对表WORKER执行下列选择运算：

5）投影(Project)

这个操作是对一个关系进行垂直分割，即对一个关系内属性的指定称为投影运算。

设关系R有n个属性：A_¹,A_²，…，A_ⁿ，则对R上属性A_ⁱ¹ , _ⁱ²，…,A_^im（A_^ij∈｛A_¹,A_²，…，A_ⁿ｝投影的结果记为：

对例4-2中的表WORKER执行下列投影运算：

∏_^NAME,AGE（WORKER）、 ∏_^DEPT＃(WORKER)

　其结果如表所示。

投影运算事例

表4.6（a）WORKER(职工)

E＃

NAME

SALARY

AGE

DEPT＃

123

张国华

1800

462

李明

2500

263

刘英明

2100

068

王飞

2700

表4.10 ∏_^NAME,AGE（WORKER）

NAME

AGE

张国华

李明

刘英明

王飞

表4.11 ∏_^DEPT＃（WORKER）

DEPT＃

关系代数操作的结果

（b）R∪S （c）R－S （d）R×S （e）π^C，A（R）（f）σ^B='b'（R）

事例

关系R 关系S

图(a) 两个关系

4.2.2 关系代数的组合操作

1）交（intersection）

　设关系R和S具有相同的元数n，相应的属性取自同一个域，则关系R和S的交记为R∩S，由既属于R又属于S的元组组成，其结果仍然一个n元关系。形式定义如下：

　　　　　R∩S＝｛t｜t∈R∧t∈S｝,t是元组变量。

关系的交可以由关系的差来表示，即：

　　　　R∩S＝R－（R－S）或R∩S＝S－（S－R）

例如：以上例中的WORKER和MANAGER为例，其交运算WORKER∩MANAGER的结果表4-5（E）所示。可以其按差运算WORKER－（WORKER－MANAGER）来计算，其结果分别如表4-5（E1）、表4-5（E2）所示。

交操作事例

表4.13（a）WORKER(职工)

E＃

NAME

SALARY

AGE

DEPT＃

123

张国华

1800

462

李明

2500

263

刘英明

2100

068

王飞

2700

表4.13（b）MANAGER（经理）

E＃

NAME

SALARY

AGE

DEPT＃

068

王飞

2700

059

曾富

3200

表4.13（E）WORKER∩MANAGER

E＃

NAME

SALARY

AGE

DEPT＃

068

王飞

2700

E＃

NAME

SALARY

AGE

DEPT＃

123

张国华

1800

462

李明

2500

263

刘英明

2100

表4.13（E1）WORKER-MANAGER

E＃

NAME

SALARY

AGE

DEPT＃

068

王飞

2700

表4.13（E2）WORKER-(WORKER-MANAGER)

2）连接(Join)运算

就是说，连接操作是笛卡儿积和选择操作的组合。

（1）条件连接

　条件连接运算又可称θ-连接，这是一个二目运算，通过它将两个关系合并成一个关系。设有关系S和n目关系R以及比较表达式iθj ,其中i是R中的属性,j是S的属性, θ含义同前（比较运算符）。形式定义如下：

【例4.8】设关系EMP表4.14表示职工的年龄和工龄情况，关系ELIT表4.15表示一个职工工作年限和可以享受的福利级别。使用下列θ连接：

连接运算事例

表4.14 关系EMP

NAME

AGE

YEARS

李亚当

王明

赵亮

陈宾

表4.15 关系ELIT

YEARS

LEVEL

表4.16 每个职工享有的全部福利(例4.8结果）

NAME

AGE

EMP.YEARS

ELIT.YEARS

LEVEL

李亚当

王明

赵亮

陈宾

EMP × ELIT

NAME

AGE

EMP.YEARS

ELIT.YEARS

LEVEL

李亚当

王明

赵亮

陈宾

（2）自然连接(Natural Join)

R?S最常用的是θ-连接的一种特例，可以定义为:

R?S

R?S计算的具体过程为:

计算R×S；
设R和S的公共属性是B_¹ ,B_² ,…, B_ⁿ，挑选R×S中满足

R.B_¹＝S.B_¹,…, R.B_ⁿ＝S.B_ⁿ的那些元组；

去掉S.B_¹,…,S.B_ⁿ这些列（保留R.B_¹,…,R.B_ⁿ）。

【例4.9】查询各部门经理及他们所在部门的信息。该查询可用一个自然连接运算实现： MANAGER ? DEPTINFO，其查询结果如表所示。

自然连接事例

表4.17 MANAGER × DEPTINFO

NAME

SALARY

AGE

M.DEPT＃

D.DEPT＃

DNAME

DTASK

068

王飞

2700

技术部

产品设计

068

王飞

2700

市场部

产品销售

059

曾富

3200

技术部

产品设计

059

曾富

3200

市场部

产品销售

表4.7 DEPTINFO（部门信息）

DEPT＃

DNAME

DTASK

技术部

产品设计

市场部

产品销售

表4.6（b）MANAGER（经理）

E＃

NAME

SALARY

AGE

DEPT＃

068

王飞

2700

059

曾富

3200

表4.18 MANAGER?DEPTINFO

NAME

SALARY

AGE

DEPT＃

DNAME

DTASK

068

王飞

2700

市场部

产品销售

059

曾富

3200

技术部

产品设计

（3）半连接(SemiJoin)

两个关系R和S的半连接运算定义为：

表4.14 关系EMP

NAME

AGE

YEARS

李亚当

王明

赵亮

陈宾

表4.15 关系ELIT

YEARS

LEVEL

表4.19

NAME

AGE

YEARS

王明

3）除法运算(Division）

有关系R和S，R能被S除的条件有两个：

一是R中的属性包含S中的属性；
二是R中的有些属性不出现在S中。

R除以S表示为R/S或R÷S。

　　R÷S是由R中那些不出现在S中的属性组成，其元组则是S中所有元组在R中对应值相同的那些元组值。

表4.20 SC

S＃

C＃

表4.21 C

C＃

表4.22 SC÷C

S＃

除法运算计算过程

设有关系R和S的元数分别为r和s，则 R÷S是一个(r-s)元的元组集合，其计算过程如下：

（a）T＝∏_^1,2,…,r-s（R）

（b）W＝（T×S）－R

（c）V＝∏_^1,2,…,r-s（W）

（d）R÷S＝T－V

即R÷S＝∏_^1,2,…,r-s（R）－∏_^1,2,…,r-s（（T×S）－R）

除法运算不是基本运算，它可由其他基本运算推出。

除法运算计算事例（SC÷C ）

(a)T＝∏^1,2,…,r-s（SC）

S＃

（T×C）

S＃

C＃

(b) W＝（T×C）－SC

S＃

(d) R÷S＝T－V

S＃

表4.20 SC

S＃

C＃

表4.21 C

C＃

4.2.3 关系代数表达式应用举例

关于教学数据库的关系模式如下：

S（SNO，SNAME，AGE，SEX，DNAME）

C（CNO，CNAME，PRE_CNO，TEACHER）

SC（SNO，CNO，SCORE）

（1）检索“陈军”老师所授课程的课程号（CNO）和课程名（CNAME）

∏_{^{CNO,
SNAME}}（σ_{^{TEACHER=’陈军’}}（C））

（2）检索年龄大于21的男学生学号（SNO）和姓名（SNAME）

∏_^SNO,SNAME（σ_^AGE>21_^∧_{^{SEX=’男’}}（S））

（3）检索至少选修“陈军”老师所授全部课程的学生姓名（SNAME）

∏_^SNAME（S?（∏_{^{SNO,
CNO}}（SC） ÷ ∏_^CNO（σ_{^{TEACHER=’陈军’}}（C））

∏_{^{SNO,
CNO}}（SC）÷∏_^CNO （σ_{^CNO=’k1’}_^∨_{^CNO=’k5’}（C））

应用举例

（4）检索“李强”同学不学课程的课程号（CNO）

∏_^CNO（C）－∏_^CNO（σ_{^{SNAME=’李强’}}（S）?SC）

（5）检索至少选修两门课程的学生学号（SNO）

∏_^SNO（σ_¹⁼⁴_^∧_²_^≠_⁵ （SC×SC）

（6）检索全部学生都选修的课程的课程号（CNO）和课程名（CNAME）

∏_{^{CNO,
CNAME}}（C?（∏_{^{SNO,
CNO}}（SC）÷∏_^SNO（S））

（7）检索选修课程包含“陈军”老师所授课程之一的学生学号（SNO）

∏_^SNO（SC?∏_^CNO（σ_{^{TEACHER=’陈军’}}（C））

（8）检索选修课程号为k1和k5的学生学号（SNO）

（9）检索选修全部课程的学生姓名（SNAME）

∏_^SNAME（S?（∏_{^{SNO,
CNO}}（SC） ÷ ∏_^CNO（C）））

应用举例

（10）检索选修课程包含学号为S2的学生所修课程的学生学号（SNO）

∏_{^{SNO,
CNO}}（SC）÷∏_^CNO（σ_{^SNO=’S2’}（SC））

（11）检索选修课程名为“C语言”的学生学号（SNO）和姓名（SNAME）

∏_{^{SNO,
SNAME}}（S?（∏_^SNO（SC?（σ_{^{CNAME=’C语言’}}（C）））））

（12）从关系SC中删除课程号为“C2”的课程成绩

DELETETUPLE＝σ_{^CNO=’C2’}（SC）

SC＝SC－DELETETUPLE

（13）将元组＜C6，数据库原理及应用，C4，胡拓＞插入课程关系C中

NEWTUPLE＝＜C6，数据库原理及应用，C4，胡拓＞

C = C ∪ NEWTUPLE

4.3 关系演算

把数理逻辑的谓词演算引入到关系运算中，就可得到以关系演算为基础的运算。

关系演算又可分为元组关系演算和域关系演算，前者以元组为变量，后者以属性（域）为变量。

4.3.1 元组关系演算

　 4.3.2 域关系演算

4.3.1 元组关系演算

在元组关系演算（Tuple Relational Calculus）中，元组关系演算表达式简称为元组表达式，其一般形式为:

　　 { t | P（t）}

　其中，t是元组变量，表示一个元数固定的元组；P是公式，在数理逻辑中也称为谓词，也就是计算机语言中的条件表达式。{ t | P（t）}表示满足公式P的所有元组t的集合。

设r目关系R和s目关系S的谓词分别为R(u)和S(v)，用它们表示并、差、选择、投影和笛卡儿积如下：

1）并：R∪S＝｛t｜R（t）∨S（t）｝

2）差：R－S＝｛t｜R（t）∧ ? S（t）｝

3）选择：σ_^F (R)＝｛t｜R（t）∧F’｝

　　其中F’是条件表达式F在谓词演算中的表示形式。

4）投影：

5）笛卡儿积：

　　下面首先介绍关系演算的原子公式定义，然后介绍关系演算公式定义。

定义4.3:关系演算的原子公式（简称原子公式）定义如下：

(1) 原子谓词R(u)是原子公式，其中u为元组。

(2) u[i]θv[j]是原子公式，其中u和v为元组, θ是比较运算符。

(3) u[i]θa是原子公式，其中a是常量。

(4) 原子公式仅有上面三种定义方式。

　定义4.4：关系演算公式（简称公式）递归定义如下：

(1) 每个原子公式都是一个公式。

(2) 如果φ_¹、φ_²是公式，则φ_¹∧φ_²、φ_¹∨φ_²、?φ_¹也都是公式。

(3) 如果φ是公式，φ中有元组变量t，则(?t)(φ)、(?t)(φ)均为公式。

(4) 公式仅由上面三种定义方式。

在公式中运算符的优先次序为：

比较运算符最高
量词?、?次之，
否定符?再次之，最后是∧∨（与或）运算。
加括号时，括号中运算优先。

元组关系演算表达查询事例

设有关系模式S(S#,SN,SEX,SA,SD)

例4.11：列出计算机科学系CS的所有学生：

例4.12：列出所有年龄大于或等于20的学生：

例4.13：求学生姓名及所在的系：

例4.14：设有关系模式R(A,B,C)和S(B,E)，用元组关系演算表示连接运算如下:

元组关系演算事例

例:下图的（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]）}

R5 = { t |(?u)(?v)(R(u)∧ S(v)

∧t[1]=u[2]∧t[2]=v[3]

∧t[3]=u[1]∧u[1]>v[2])}

4.3.2 域关系演算

　域演算的运算符基本上与元组关系演算相同，主要区别是公式中的变元不再是元组而是元组分量的域，简称域变量。

　域演算表达式的形式是：

　　｛X_¹，X_²，…，X_^k｜Φ（X_¹，X_²，…，X_^k）｝

原子公式有三类：

(1) R（X_¹，X_²，…，X_^k）,R是K元关系，X_ⁱ是域变量或常量。R（X_¹，X_²，…，X_^k）表示由分量X_¹，X_²，…，X_^k组成的元组属于R。

(2) XθY，X、Y是域变量,θ是算术比较符，XθY表示X与Y满足比较关系θ。

(3) Xθc或cθX,这里c为常数，表示域变量x与常数c之间满足比较关系θ。

域关系演算事例

例：下图（a）、（b）、（c）是三个关系R、S、W，（d）、（e）、（f）分别表示下面三个域表达式的值。

（a）关系R （b）关系S （c）关系W （d）R1 （e）R2 （f）R3

域关系演算的例子

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 ）}

4.4 关系查询优化

用户输入查询

查询的内部表示

执行查询步骤

向用户报告查询结果

查询语句的句法分析

查询优化

处理查询

查询是数据库的最基本、最常用、最复杂的操作。

数据库的查询一般从查询语句出发，直到获得查询结果，需要一个处理过程，这个过程叫做查询处理。

在关系数据库的查询中用户不必关心查询语言的具体执行过程，而由DBMS确定合理的、有效的执行策略，称为查询优化。

4.4.1 查询优化的一般策略

(1)尽可能早地执行选择、投影等一目运算。

(2)把先做笛卡儿积，后做选择结合起来，使之成为一个连接运算。

(3)同时计算一串选择和一串投影运算，以免分开运算造成多次扫描文件。

(4)找出表达式里的公共子表达式。

(5)适当的预处理。

(6)把投影同其前面的双目运算结合起来，没有必要为了去掉某一个或某几个属性而扫描一遍关系。

4.4.2关系代数优化

1）表达式的求值

　两个等价的关系代数表达式E_¹和E_²等价，记为E_¹=E_²，就是说，当两个表达式中的同名变量代入相同关系后产生相同结果。基于这一定义，可得到许多代数表达式的等价转换规则。

第一种定义：关系是一个k一元组(k -tuples )的集合，其中k是固定的。两个关系相等，当且仅当有相同的元组集合。
第二种定义：关系是从属性名到其值域的映射的集合；按这种定义，如果两个关系有相同的映射集，它们是相等的。

2）关系代数等价变换规则

⑴连接和笛卡儿积的交换律

⑵连接和笛卡儿积的结合律

(E_¹ × E_²) × E_³＝E_¹ ×(E_²× E_³)

E_¹×E_²＝E_²×E_¹

等价变换规则

⑶投影的串接

⑷选择的串接

⑸选择和投影的交换

其中：

更一般地，如果F_¹只涉及到E_¹中的属性，而F_²涉及到E_¹和E_²两者的属性,则：

等价变换规则

(6)选择移入笛卡儿积

如果F中所涉及的属性都在E_¹中，那么 :

如果F是F_¹∧ F_²形式，并且F_¹只涉及E_¹中的属性,F_²只涉及E_²的属性,则：　

等价变换规则

⑺选择与并运算交换

⑻选择与差运算交换

　⑼投影移入笛卡儿积

设A_¹，…,A_ⁿ是E_¹的属性，中出现的B_¹，…，B_^m是E_²的属性，则：

⑽投影移入并运算

3）代数优化的算法

下面给出一个通用的优化算法：

优先应用单项的选择和投影；
优先应用一般选择和投影；
对笛卡儿积、并运算、差运算，若它们前面加有选择和投影，则先做选择和投影。

优化算法

算法：关系表达式的优化

输入：表示关系代数表达式的语法分析树

输出：计算这个表达式的程序

方法：(1)使用规则④把形式为的选择变成选择串接的形式：

(2)对每个选择用规则④ ~ ⑧，尽可能地将选择向树的叶端移动。

(3)对每个投影，利用规则③，⑨，⑩和一般化规则⑤，将投影尽可能地向树的叶端移动。

(4)利用规则③~⑤把串接的选择和投影组合为一个选择、一个投影或带投影的选择。

(5)把所得到的树的内部结点划分成组。

图书管理数据库，其关系如下：

BOOKS (LC_NO , TITLE，AUTHOR，PNAME）

PUBLISHERS (PNAME，PADDR，PCITY)

BORROWERS (CARD_NO, NAME，ADDR，CITY)

LOANS(CARD_NO，LC_NO，DATE)

为了解借书情况，我们定义一个关系XLOANS存放借书信息。XLOANS是关系BOOKS,BORROWERS和LOANS的自然连接，即：

其中,F是条件表达式：

BORROWERS.CARD_NO=LOANS.CARD_NO ∧ BOOKS.LC_NO=LOANS.LC_NO

S是投影表达式：

TITLE,AUTHOR,PNAME,LC_NO,NAME,ADDR,CITY,CARD_NO,DATE

表达式的语法分析树

∏^{TITLE,
NAME}

σ^{DATE<01/01/1999}

∏^{TITLE,
AUTHOR, PNAME, LC_NO, NAME, NAME, ADDR,
CITY, CARD_NO, DATE}

σ^{BORROWERS.CARD_NO=LOANS.CARD_NO
∧ BOOKS.LC_NO=LOANS.LC_NO}

BOOKS

BORROWERS

LOANS

σ^{BORROWERS.CARD_NO=LOANS.CARD_NO}^∧^{BOOKS.LC_NO=LOANS.LC_NO}分解成

σ^{BORROWERS.CARD_NO=LOANS.CARD_NO}和σ^{BOOKS.LC_NO=LOANS.LC_NO}两个运算

将三个选择尽可能向树叶端移动
将该语法树中的两个投影合并为一个投影运算。

选择下移且合并投影后的语法树

　　∏^{TITLE,
NAME}

σ^{DATE<01/01/1999}

σ^{BOOKS.LC_NO=LOANS.LC_NO}

BOOKS

BORROWERS

LOANS

σ^{BORROWERS.CARD_NO=LOANS.CARD_NO}

在上面的笛卡儿积运算乘积之下增加一个投影运算：

∏^{TITLE,
NAME, BOOKS.LC_NO, LOANS.LC_NO}

并将投影替换分解成两个投影，一个是作用在BOOKS上：

∏^{TITLE,
BOOKS.LC_NO}

另一个是作用在笛卡儿积右边：

∏^{NAME, LOANS.LC_NO}

进一步优化后的语法树

BORROWERS

∏^{TITLE,
NAME}

σ^{DATE<01/01/1999}

σ^{BOOKS.LC_NO=LOANS.LC_NO}

BOOKS

LOANS

σ^{BORROWERS.CARD_NO=LOANS.CARD_NO}

∏^{TITLE,
BOOKS.LC_NO}

∏^{NAME,
LOANS.LC_NO}

最下面的笛卡儿积运算运算前增加两个投影运算：

∏^{NAME, BORROWERS.CARD_NO}

∏^LOANS.LC_NO^，^{LOANS.CARD_NO}

最后的语法树

∏^{TITLE,
NAME}

σ^{BOOKS.LC_NO=LOANS.LC_NO}

BOOKS

σ^{BORROWERS.CARD_NO=LOANS.CARD_NO}

∏^{TITLE,
BOOKS.LC_NO}

∏^{NAME,
LOANS.LC_NO}

σ^{DATE<01/01/1999}

LOANS

BORROWERS

∏^{NAME,
BORROWERS.CARD_NO}

∏^{LOANS.LC_NO,
LOANS.CARD_NO}

4.4.3 基于存取路径的规则优化

1）选择操作的实现和优化

选择条件分为等值、范围和集合三种。

选择操作的实现方式：

顺序扫描
索引技术

无序索引
排序索引
多属性索引

散列技术

　　排序和簇集虽然对某些查询有利，但在插入新元组时，要移动其他元组，而且修改该关系上的所有索引，就十分费时了。

　　关系只对按排序或簇集的这个属性上进行查询有利，而对其他属性上的查询没有什么好处，还要额外地增加索引维护的开销。

(1)如果是小关系，则直接使用顺序扫描，不考虑其他存取路径。

(2)如果无索引或散列等存取路径可用，使用顺序扫描。

(3)对于主关键字等值查找，如果最多只有一个元组中选，则优先采用主关键字上的索引或散列。

(4)对于非主属性等值查找，若选中元组个数在关系中所占的比例。小于20％，使用无序索引，否则，使用簇集索引或顺序扫描。

(5)对于范围查找，可以先通过索引找到范围的边界，再沿索引顺序集搜索。

(6)对于用AND连接的合取条件，最好使用相应的多属性索引。

(7)对于用OR连接的析取条件表达式，只能按各个子条件分别选出相应的元组集合，然后计算这些元组集的并。

(8)因为采用索引结构能够提高检索速度，所以，只要有可能，应优先使用索引查找。

选择操作的启发式规则

2）连接操作的实现和优化

（1）嵌套循环(Nested Loop）法

对于R的每个元组，S要顺序扫描一次。

嵌套循环算法:

／*设R有n个元组，S有m个元组*／

(1) i←1，j←1

(2) while (i≤n)

(3) do｛while (j≤m)

(4) do｛if R(i)[A]＝S (j)[B]

(5) then输出<R(i),S(j)＞至T;

(6) j←j＋1 ｝

(7) j←1，i←i＋1;

　　　｝／*T为R,S连接的结果*／

　以R为外关系，S为内关系，用嵌套循环法进行连接时所需访问的物理块数为：

　若以S为外关系,R为内关系，则所需访问的物理块数为：

　其中：b_^R,b_^S分别为分配给R和S的物理块数,n_^B为可供连接用的缓冲块数

（2）利用索引或散列寻找匹配元组法

如果内关系有合适的存取路径（例如索引或散列），则可以考虑使用这些存取路径取代顺序扫描，以减少I/O次数，尤其当连接属性上有簇集索引或散列时，最为有利。
如果连接属性中只有无序索引，在一般情况下要比嵌套循环法好，但不如簇集索引和散列那样效果显著。
尤其当可供连接用的缓冲块增多时内关系的扫描次数将减少，每次循环从内关系所选的匹配元组数将增大，当每次循环所选的匹配元组数在内关系中占有较大比例（例如20％）时，用无序索引还不如顺序扫描。

（3）排序归并法

R.A

…

S.B

…

跳过

排序归并示意图

排序归并算法

　　　 (1) i←1，j←1;

(2) while(i≤n) and (j≤m)

(3) 　do｛if R(i)[A]>S(j)[B]

(4) 　then j←j＋1;

(5) 　 else if R(i)[A]<S(j)[B]

(6) 　　 then i←i＋1；

(7) 　 else｛／*R(i)[A]=S(j)[B]，输出连接元组*／

(8) 　　输出＜(R(i),S(j)＞至T;

　　　　　　　／*输出R(i)与S中除S(j)外的其他元组所组成的连接元组*／

(9) 　　p←j＋1

(10) 　　while(p≤m) and (R(i)[A]=S(p)[B])

(11) 　 do｛输出<R(i),S(p)>至T;

(12) 　 p←p＋1; ｝

　　／*输出S(j)与R中除R(i)外的其他元组所组成的连接元组*／

(13) 　　 k←i＋1；

(14) 　　while (k≤n) and (R(k) [A]=S (j) [B])

(15) 　　do｛输出<R(k),S(j)>至T;

(16) 　 k←k＋1；｝

(17) 　i←i＋1，j←j＋1；

(18) ｝｝

（4）散列连接法(Hash Join)

当连接属性R.A和S.B具有相同的域时，可以用A、B作为R、S的散列键，并用相同的散列函数把R和S散列到同一散列文件中。符合连接条件的R和S的元组必然位于同一桶中，但同一桶中的R和S的元组未必都满足连接条件。
只要把桶中所有匹配的元组取出，就可以获得连接的结果。
散列连接法的关键是要建立一个供连接用的散列文件。
建立散列文件时，也可以在桶中不填入R、S的实际元组，而代之以它们的tid（元组标识）。可取出∏_^A（R）和∏_^B(S)附在相应的tid后。
在连接时，以桶为单位，按∏_^A（R）＝∏_^B(S)条件找出匹配的tid对，在得到匹配的tid对后，可按tid对中的tid取出元组进行连接。

连接方法的启发式规则

①如果两个关系都已按连接属性排序，则优先用排序归并法。如果两个关系中已有一个关系按连接属性排序，另一个关系很小，方可考虑对此未排序的关系按连接属性排序，再用排序归并法连接。

②如果两个关系中有一个关系在连接属性上有索引（特别是簇集索引）或散列，则可令另一关系为外关系，顺序扫描，并利用内关系上的索引或散列寻找其匹配元组，以代替多遍扫描。

③如果应用上述两规则的条件都不具备，且两个关系都比较小，可以用嵌套循环法。

④如果①、②、③规则都不适用，可用散列连接法。

以上启发式规则，仅在一般情况下可以选取合理的连接方法，若要获得好的优化效果，须进行代价比较。

3）投影操作的实现

用排序法消除重复元组的投影算法。

(1) 对关系R的每个元组t，生成t[(投影属性集)]，并存于T'中

／*T'是未消除重复元组的投影结果，有n个元组*／

(2) if（投影属性集）含有R的主关键字

(3) then T←T'；

(4) else {T'按所有属性排序；

(5) i←1，j←2；

(6) while i≤n

(7) do｛输出元组T'(i)至T;

(8) while T(i)=T'(j)do j←j十1，

／*消除重复元组*／

(9) i←j，j←i+1；

｝

/ *T中为消除重复元组后的投影结果*／

4）集合操作的实现

(1)并操作算法

(1) 将R,S按主关键字升序排序；

(2) i←1，j←1；

(3) while (i ≤ n) and (j ≤ m)

(4) do{(if R(i)>S(j)

／*指R(i)的关键字大于S(j)的关键字，下同*／

(5) then｛输出S(j)至T;

(6) j←j＋1；｝

(7) else if R(i)<S(j)

(8) then｛输出R(i)至T;

(9) i←i＋1； }

(10) else j←j+1；／*跳过一个重复元组*／｝

(11) if（i≤n）then把R(i)至R (n)的元组输出至T;

(12) if（j≤m）then把S(j)至S(m)的元组输出至T;

／*T中的结果为R∪S*／

4）集合操作的实现

(2)交操作算法

(1) 将按R、S主关键字升序排序；

(2) i←1，j←1；

(3) while (i≤n) and (j≤m)

(4) do｛if R(i)>S(j)

／*指R(i)的主关键字大于S(j)的主关键字，下同*／

(5) then j←j＋1；

(6) else if R(i)<S(j)

(7) then i←i＋1

(8) else｛输出R(i)至T; ／*R(i)=S(j)，输出一元组*／

(9) i←i＋1，j←j+1；｝

／*T中结果为R∩S*／

4）集合操作的实现

(3)差操作算法

(1) 将按R、S主关键字升序排序；

(2) i←1，j←1;

(3) while (i≤n) and (j≤m)

(4) do｛if R(i)>S(j)

／*指R(i)的主关键字大于S(j)的主关键字，下同*／

(5) then j←j＋1；

(6) else if R(i)<S(j)

(7) then｛输出R(i)至T；

(8) i←i＋1；｝

(9) else i←i＋1，j←j＋1；

(10) if（i≤n）then将R(i)至R(n)的元组输出至T;

／*T中的结果为R－S*／

5）组合操作

∏

R¹

∏¹

σ¹

∏²

σ²

R²

组合操作的例子

本章小结

关系运算理论是关系数据库查询语言的理论基础。只有掌握了关系运算理论，才能深刻理解查询语言的本质和熟练使用查询语言。
本章先介绍了关系数据库的基本概念。关系定义为元组的集合，但关系又有它特殊的性质。
关系代数的五个基本操作以及由它们组成的组合操作，这是本章的重点。要能进行两方面的应用：一是计算关系代数表达式的值；二是根据查询语句写出关系代数表达式的表示形式。
关系演算是基于谓词演算的关系运算，理论性较强。主要理解表达式的语义，计算其最优值，并能根据简单的查询语句写出元组表达式。
查询优化是指系统对关系代数表达式要进行优化组合，以提高系统效率。本章介绍了关系代数的表达式的若干变换规则和优化的一般策略，然后提出了一个查询优化的算法。