第3章关系运算

第3章关系运算及关系系统关系代数关系演算关系代数、元组演算的等价性查询优化关系系统习题3.1

关系代数关系数据库操作--关系运算。关系运算分为两种方法：基于代数定义的称为关系代数；基于逻辑定义的称为关系演算。SQL:具有关系代数和关系演算双重特点的语言。关系代数运算分为两类：传统的集合运算：并、交、差和广义笛卡尔乘积。专门的关系运算：选择、投影、连接和除。关系代数的运算对象是关系，运算结果也是关系。关系代数运算涉及到两类辅助运算符：（1）比较运算符：＞、≥、＜、≤、＝、≠。（2）逻辑运算符：｛~~｝（非）、∧（与）、∨（或）。3.1.1

传统的集合运算传统的集合运算是二目运算。设两个关系

R和S均为n

元关系，且相应的属性取自同一个域（R和S为同类型关系：属性集相同、次序相同）1．并（∪）关系R和S的并为：R∪S={t|t∈R∨t∈S}其结果仍为n目关系。任取元组t，当且仅当t属于R或t属于S时，t属于R∪S。（一个元素在并集中只出现一次）2．差（－）关系R和S的差为：R－S={t|t∈R∧t(S}其结果仍为n目关系。任取元组t，当且仅当t属于R且t不属于S时，t属于R-S。3．交（

∩）关系R和S的交为：R∩S={t|t∈R∧t∈S}其结果仍为n目关系。任取元组t，当且仅当t既属于R又属于S时，t属于R∩S。关系的交运算可表示为差运算？R∩S=R-(R-S）4．广义笛卡尔乘积（×）设R为m目关系，S为n目关系，则R和S的广义笛卡尔乘积为：R×S={t|t=〈tr，ts〉∧tr∈R∧ts∈S}其结果为m+n目关系。元组的前m列是关系R的一个元组，元组的后n列是关系S的一个元组。若R

有k1

个元组，

S

有k2

个元组，

则R×S

有k1×k2个元组。实际运算时，可从R的第一个元组开始，依次与S的每一个元组组合，然后对R的下一个元组进行同样的操作，直至R的最后一个元组也进行完相同操作为止，即可得到R×S的全部元组。【例3.1】

给定两个同类型关系R和S，计算

R∪S，

R－S，

R∩S，R×S的结果。图3.2

传统集合运算举例3.1.2

专门的关系运算专门的关系运算包括选择、投影、连接和除。1．选择（

σ

）设R是n目关系，F是条件，其结果为

“真”或“假”，则R的选择操作定义为：σF（R）={t|t∈R∧F（t）=true}即取出满足条件F的所有元组。F包含下列两类符号：运算对象（元组分量、常数）；运算符（＞、≥、…..｛~~｝、∧、∨）。学号＞′11018′例如：

σ

（student），取出学号大于11018的元组，σ性别=′男′∧[6]≥′600′（student）。取出入学成绩大于等于600的男性。F中的常量需用单引号括起。选择操作从行的角度进行运算。2．投影（

π）设R是n目关系，R在其分量Ai

,

Ai

,,

Ai

(m

£

n;i1,i2

,,im1

2

m）上的投影操作定义为：>˛

R}pi

,i

,i1

2

m=

{t

|

t

=<

ti

,

ti

,ti

> <

t1,,

ti

,,

tn1

2

m

m即取出所有元组在特定分量

Ai

,

Ai

,,

Ai1

2

m上的值。例如，对图3.1可写出：πA，C（S），ACa1a2c2c1图3.3投影说明举例π[1]，[4]，[6]（student）。投影操作从列的角度进行运算，可以改变关系中列的顺序。投影操作消去部分列后，可能会出现重复元组，根据关系特性，应将重复元组删去。3.

连接（

）θ连接，含义从两个关系的笛卡尔积中选取属性间满足一定条件的元组R==σAθB（R×S）A和B：分别为R和S上度数相等且可比的属性组θ：比较运算符从R和S的广义笛卡尔积R×S中选取在A属性组（R关系）上的值与在B属性组（S关系）上值满足比较关系的元组。AθBS

=

{

tr

ts

|

tr

˛

R∧ts

˛

S∧tr[A]θts[B]

}两类常用的连接运算–等值连接–θ为“＝”的连接运算称为等值连接等值连接的含义–从关系R与S的广义笛卡尔积中选取A、B属性值相等的那些元组，即等值连接为：RA=B

S

=

{

tr

ts

|

tr

˛

R∧ts

˛

S∧tr[A]

=

ts[B]

}自然连接特殊的等值连接»两个关系中进行比较的分量必须是相同的属性组»在结果中把重复的属性列去掉自然连接的含义R和S具有相同的属性组BR S

=

{

tr

ts

|

tr

˛

R∧ts

˛

S∧tr[B]

=

ts[B]

}自然连接和等值连接的区别是：①等值连接相等的属性可以是相同属性，也可以是不同属性；自然连接相等的属性必须是相同的属性。②自然连接必须去掉重复属性，而等值连接无此要求。③一般地，自然连接用于有公共属性的情况中。如果两个关系没有公共属性，那么它们的自然连接就退化为笛卡尔乘积。RS举例ABCa1b15a1b26a2b38a2b412BEb13b27b310b32b52RSAR.BCS.BEa1b15b27a1b15b310a1b26b27a1b26b310a2b38b310R

SC＜E等值连接RSR.B=S.BAR.BCS.BEa1b15b13a1b26b27a2b38b310a2b38b32自然连接RSABCEa1b153a1b267a2b3810a2b382给定如下关系R和S，计算：(1）

R（3）R

SS（2）

RR

.B=S.B∧R.C=SS.CB＜D图3.4

选择、

投影、

连接举例4．除(÷)关系R（X，Y）和S（Y，Z），其中X，Y，Z为属性或属性组合。R中的Y和S中的Y可以有不同的属性名，但必须出自相同的域集。R÷S定义形式为：

R÷S=πX（R）－πX（（πX（R）×S）－R）除法的性质：R÷S的结果属性是由属于R但不属于S的所有属性构成的。R÷S的任一元组都是R中某元组的一部分。R（X，

Y）÷S（Y，

Z）≡R（X，

Y）÷πY（S）R÷S=πX（R）－πX（（πX（R）×S）－R）（4）

R÷S的计算过程如下：①

T=πX（R）;②

W=（T×S）－R;③

V=πX（W）;④R÷S=T－V。【例3.3】给定关系R和S，求R÷S。图3.5除法操作举例练习：基于关系数据库E、P、EP：职工E（E＃，EN，EA，EE，ED）项目P（P＃，PN，PL）Key={E＃}Key={P＃}职

工

参

加

项

目

EP

（

E

＃

，

P

＃

，

L

）Key={E＃，

P＃}EE职工性别，L工时，PL项目所在地用关系代数完成下列问题的查询：用关系代数完成下列问题的查询：①检索维修班的全体职工。②检索年龄大于48岁的女职工。③查询职工的姓名和所在的部门。④检索参与了P5项目号的职工的职工号与工时，进而给出对应职工的姓名。⑤检索未参与项目名为“礼堂”的职工号、姓名。答案：用关系代数完成下列问题的查询：①检索维修班的全体职工。σED=′WX′（E）②检索年龄大于48岁的女职工。σEE=′女′∧3＞′48′（S）③查询职工的姓名和所在的部门。πEN，

ED（P）④检索参与了P5项目的职工的职工号与工时，进而给出对应职工的姓名。π1，

3（σ2=′P5′（EP））πEN（

π1，

3

（σP＃=′P5′（EP））E）⑤检索未参与名为“礼堂”项目的职工号、姓名。π

E＃EN（（（σPN=′礼堂′（P））EP）

E）未参与名为“礼堂”项目的职工号、姓名。π

E＃EN（E）－π

E＃EN（（（σPN=′礼堂′（P））EP）

E）E）⑥检索参与项目号为P2或P4的职工号、姓名。T=πE＃（σP＃=′P2′∨P＃=′P4′（EP））R=π

E＃

EN（

πE＃（σP＃=′P2′∨P＃=′P4′（EP））⑦检索同时参与项目号为P2和P4的职工号。π[1]（σ

[2]=′P2′∧[5]=′P4′∧[1]=[4]（EP×EP））或构造临时关系T={P2，P4}，再求πE＃，

P＃（EP）÷T⑧检索参与全部项目职工姓名。πEN（（（πE＃，

P＃（EP））÷πP＃（P））

E）⑨检索参与项目包含职工E3参与项目的职工号，πE＃，

P＃（EP）÷πP＃（σE＃=′E3′（EP））或参与项目不包含职工E3所参与项目的职工号及姓名。πE＃（E）－（πE＃，P＃（EP）÷πP＃（σE＃=′E3′EP）））πEN（（πE＃（E）－（πE＃，

P＃（EP）÷πP＃（σE＃=′E3′（EP））））

E）教材P49-50，例2-6SQL语言3.1.3

扩充的关系代数运算根据前面讨论可知，涉及两个及两个以上关系表的查询必然用到连接运算,包括等值连接、非等值连接、自然连接。除此之外，为了保留更多信息，还有外连接、半连接、外部并-----扩充的关系代数运算。1．外连接（Outer

join）两个关系R和S作自然连接时，两个关系公共属性上值不相等的元组无法进入连接后的新关系，造成R和S中部分元组值被舍弃。有时希望这些该舍弃的元组继续保留在新关系中-----外连接。【例3.5】关系数据库S和SC两个关系有如下元组（如图3.6）：S（S＃，

SN，

SA，

SE，

SD）SC（S＃，

C＃，

G）执行运算S SC后，

结果如图3.7。图3.6

基本关系R和S图3.7

S

SC运算结果结果关系中没有95003袁野和95004赵婷两个学生的数据，原因在于他们没有选课。如想以S为主体列出每个学生的基本情况及选课情况，若该生未选课，则只输出该生的基本信息，选课信息为空值，则需用到外连接。即产生如图3.8

所示的结果。图3.8

外连接说明举例

S

=

SC外连接定义:如果R和S作自然连接时，把该舍弃的元组也保留在新关系中，在新增加的属性上填上空值（NULL），用符号：R S表示。根据保留元组的不同，外连接又分为左外连接和右外连接。（1）左外连接。如果R和S作自然连接时，只把R中原该舍弃的元组保留在新关系中，则这种操作称为左外连接，用符号R

S表示。（2）右外连接。如果R和S在作自然连接时，只把S中原该舍弃的元组保留在新关系中，那么这种操作称为右外连接.用符号：R

S表示。【例3.6】在图3.9中给出两个基本关系R和S其自然连接、外连接、左外连接、右外连接分别为(c)，(d)，(e)，(f)。从上述结果可见，外连接的交换律不成立图3.9外连接操作举例外连接（续）例：以学生为主体，查询每个学生及其选修课程的情况(要求学生信息均保留,用外连接).显示：Sno，Sname，Ssex，Sage，Sdept，Cno，GradeOracle中实现外联接SELECT

Student.Sno，Sname，Ssex，Sage，Sdept，Cno，GradeFROM

Student，SCWHERE

Student.Sno

=

SC.Sno(+)；外连接（续）结果：Student.SnoSnameSsexSageSdeptCnoGrade95001李勇男20CS19295001李勇男20CS28595001李勇男20CS38895002刘晨女19IS29095002刘晨女19IS38095003王敏女18MA95004张立男19IS2．外部并（Outer

union）关系的并运算R∪S，由属于R或属于S的元组构成。此时要求两个关系R和S均为n

目关系，且相应的属性取自同一个域。现实应用中，经常需要在具有不同关系模式（目不同或属性的域不同）的两个关系R和S上进行并运算，涉及到外部并运算。外部并定义：如果R和S是不同的关系模式，R∪

S（外部并），其结果关系的属性由R和S的所有属性组成（公共属性只取一次），该关系的元组由属于R或属于S的元组构成，元组在新增加的属性上填上空值。【例3.7】在图3.9

(a)和(b)

中给出两个基本关系R和S，其外部并操作结果如图3.10。图3.10

外部并操作举例修改基本表语句格式ALTER

TABLE<表名>[ADD<新列名><数据类型>[完整性约束]]

[DROP<完整性约束名>][MODIFY<列名><数据类型>]；ADD子句：增加新列和新的完整性约束条件DROP子句：删除指定的完整性约束条件MODIFY子句：用于修改列名和数据类型例题向R表增加“D”列，S表增加“A”列；其数据类型为CHAR。ALTER

TABLE

R

ADD

D

CHAR(1)；ALTER

TABLE

S

ADD

A

CHAR(1)；不论基本表中原来是否已有数据，新增加的列一律为空值。如果基本表中原来已有数据，新增列不可有NOT

NULL约束FROM

RSql>SELECT

*UNIONSELECT

*

FROM

S；默认地，UNION操作符选取不同的值。如果允许重复的值，请使用UNION

ALL。3．

半连接（Semi

join）半连接定义：两个关系R和S的自然连接运算结果在关系R所有属性上的投影，记作：R∝S，即：R

∝

S≡πAtt(R)（R

S）【例3.8】在图3.9(a)和(b)给出的两个基本关系R和S，其自然连接和半连接操作结果如图3.11。图3.11

半连接操作举例sql>SELECT

R.A，R.B，R.C，FROM

R，SWHERE

R.B=S.B

and

R.C=

S.C；关系代数的查询功能是相当强的。可以证明，关系代数操作集（∪，π，-，σ，×）是完备的操作集，任何其它关系代数操作都可以用这五种操作的组合来表示。任何一个DBMS，只要它能完成这五种操作，就称它是关系完备的。3.2

关系演算3.2.1

元组关系演算元组演算关系表达式用{t|φ(t)}来表示。t是元组变量，φ(t)为元组演算公式（公式）。{t|φ(t)}表示所有使φ(t)为真的元组的集合。1．φ(t)的基本形式——原子公式原子公式有三类。（1）

R(t)。R：关系名，t：元组变量。

原子公式R(t)表示t是R的元组。{t|R(t)}

表示由t构成的集合，t是R中的一个元组。（2）

t［i］θu［j］。t和u为元组变量，θ是比较运算符，t［i］和u［j］表示t的第i个分量和u的第j个分量原子公式t［i］θu［j］表示元组t的第i个分量和元组u的第j个分量之间满足θ运算。如t［1］＞u［3］表示元组t的第1个分量大于元组u的第3个分量。元组表达式{t|R(t)∧t［3］≥t［5］}的含义？（3）

t［i］θC或Cθt［i］。C为常量。t［i］θC表示元组t的第i个分量和常量C之间满足θ运算。如t［1］≠30表示元组t的第1个分量不等于30。元组表达式{t|R(t)∧t［3］

≥55}

的含义？2．变量的约束特性程序设计中大量使用变量，根据变量作用域的不同，变量可分为局部变量和全局变量。元组演算中也涉及同类问题--元组变量的自由和约束概念。自由元组变量与约束元组变量（1）自由元组变量。一个公式中，元组变量的前面没有全称量词（

"）或存在量词（

$），则该元组变量称为自由元组变量。（2）约束元组变量。一个公式中，元组变量的前面有全称量词（

"），或者有存在量词（

$

），则该元组变量称为约束元组变量。3．公式φ(t)的递归定义每个原子公式是公式。如果φ1和φ2为公式，则

φ1，

φ1∧φ2，φ1

∨φ2，φ1

φ2（

φ1为真，则φ2为真）为公式。如果φ1为公式，则$

t(φ1)为公式。表示：存在一个元组t使φ1为真。如果φ1为公式，则"t(φ1)为公式。表示：对于所有元组t均使φ1为真。公式中各运算符的优先级从高到低依次是：①算术比较运算符；②量词；③

逻辑运算符，且内部按 、

∧、

∨顺序计算；④嵌套时先内括号后外；有限次地使用上述五条规则得到的公式是元组演算公式，其它公式不是元组演算公式。【例3.9】已知

R(A,B,C)={（1，2，3），（4，5，6），（7，8，9）}S(A,B,C)={（1，2，3），（3，4，6），（5，6，9）}求：R1={t|R(t)∧﹁S(t)}R2={t|(

$

u)(S(t)∧R(u)∧t［3］＜u［2］)}R3={t|("

u)(R(t)∧S(u)∧t［3］＞u［1］)}R4={t|(

$

u)($

v)(R(u)∧S(v)∧u［1］＞v［2］∧t［1］=u［2］∧t［2］=v［3］∧t［3］=u［1］)}R1=R－S；R2=πAtt(S)（R

R.B＞S.CS）；R3=πAtt

(R)(（RR.C＞S.A

S）

÷

S)；R4=πR.B,

S.C,

R.A（R

R.A＞S.B

S）；所以关系代数与关系演算也存在等价性。图3.12

元组关系演算举例

P555．元组关系演算与关系代数的等价性关系代数运算可用元组关系演算表示；

元组关系演算可用关系代数运算表示。关系代数运算能用五种基本操作（∪，π，-，σ，×）来表示。五种基本操作表示为元组演算表达式（1）并操作（∪）：R∪S={t|R(t)∨S(t)}（2）

差操作（-）：

R－S={t|R(t)∧┐S(t)}（3）笛卡尔乘积（×）：R×S

={t(m+n)|($u(m))($v(n))(R(u)∧S(v)∧t［1］=u［1］∧t［2］=u［2］∧…t［m］=u［m］∧t［m+1］=v［1］∧t［m+2］=v［2］∧…∧t［m+n］=v［n］)}投影（π）：πi1,

i2,

…,

ik={tk|(

$u)(R(u)∧t［1］=u［i1］∧t［2］=u［i2］∧…t［k］=u［ik］)}选择（σ）：σF（R）={t|R(t)∧F′}F′是F在元组演算中等价的表示形式。练习：设有如图所示的三个关系R1,R2,R3,请写出R4,R5,R6所对应的关系代数表达式。R4={t‰R1[t]

t[3]‡4}R5={t‰($u)(R1(t)

R2(u)

t[3]<u[3])}A1A2A3ae8cf6db4df3R1A1A2A3ae8cc5db4df6R6={t‰($u)

($v)

(R1(u)

R3(v)

u[2]=”f”

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

t[3]=u[1])

t[4]=v[2])

t[5]=u[2])}R2

R3B1B24x5d3.2.2

域关系演算域关系演算和元组关系演算类似，所不同的是公式中的元组变量由域变量代替，且域变量具体代替的是元组变量的每一个分量，其变化范围是某个值域而不是一个关系。域关系演算表达式的一般形式为：{t1t2…tk|φ(t1,t2,…,tk)}。t1,t2,…,tk是域变量，φ(t1,t2,…,tk)为域关系演算公式。{t1t2…tk|φ(t1,t2,…,tk)}表示所有使φ为真的那些t1,t2,…,tk所组成元组的集合。1．φ的基本形式——原子公式原子公式有三类：（1）

R(t1,t2,…,tk)。R是一个k元关系，ti为元组的第i个分量。R(t1,t2,…,tk)表示由分量t1,t2,…,tk组成的元组属于R。（2）

tiθuj。ti为元组t的第i个分量，uj为元组u的第j个分量。

tiθuj表示域变量ti和uj满足θ关系。例如t1＞u3表示：元组t的第1个分量大于元组u的第3个分量。（3）

tiθc或cθti。c为常量。tiθc表示：域变量ti和常量c之间满足θ运算。t1≠30表示域变量ti不等于30。域演算表达式{t1t3|R(t1,t2,

t3)∧t3≥55}?2．变量的约束特性域关系演算中变量的约束特性与元组关系演算变量的约束特性完全相同，也分为自由域变量和约束域变量。3．公式φ(t)的递归定义每个原子公式是公式。原子公式中的域变量是自由域变量。如果φ1和φ2为域关系演算公式，则｛

﹁｝φ1，φ1∧φ2，φ1∨φ2也是域关系演算公式。如果φ为域关系演算公式，则($

ti)φ也是域关系演算公式。如果φ为域关系演算公式，则("ti)φ也是域关系演算公式。（5）公式中各运算符的优先级从高到低依次是：①算术比较运算符；②量词；、∧、∨顺③逻辑运算符，且内部按序计算；④嵌套时先内括号后外；（6）有限次地使用上述五条规则得到的公式是元组演算公式，其它公式不是元组演算公式。【例3.12】图3.13（a）、（b）、（c）是给定的三个关系R、S和W，（d）、（e）、（f）分别是下列三个域关系演算表达式的值。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)}这里($

u)($

v)可简写成($

uv)。图3.13域关系演算举例P493.2.3

关系运算的安全性在数据库技术中，不产生无限关系的运算称为安全运算，相应的表达式称为安全表达式，所采取的措施称为安全约束。关系代数中，以集合论为基础研究的关系均为有限元组的集合，基本操作是并、差、笛卡尔乘积、投影和选择，其运算结果是有限的，所以关系代数运算总是安全的。关系演算可能产生无限关系。例如，元组关系演算{t|R(t)}是有限的，而{t|｛﹃｝R(t)}是无限的，由不属于R的元组构成。元组演算公式的安全性定义:设Ψ是一个元组关系演算公式。由如下两类符号构造集合：Ψ中的常量；Ψ中出现的所有元组的所有属性值。把该集合称作Ψ的符号集合（记作：DOM（Ψ））。例如公式P(t)是t［1］=′a′∨R(t)，若R是二元关系，则DOM（P）={a}∪π1(R)∪π2(R)。【例3.14】给定关系R和S（如图3.14），Ψ={t|t［1］=′b′∨｛﹃｝R(t)∨｛﹃｝S(t)

}，求DOM（Ψ）。图3.14

符号集求解用例关系解：根据定义进行解答：DOM（Ψ）

={b}∪πA(R)∪πB(R)∪πC(R)∪πD(S)∪πE(S)∪πF(S)={b,

a,

3,

5,

g,

h,

1,

6,

7,

d,

c,

f,

e}【例3.16】给定关系R（如图3.15（a）），Ψ={t|｛﹃｝R(t)}，若不进行安全限制，则元组运算表达式是不安全的，求DOM（Ψ）。解：根据定义：DOM（Ψ）=πA(R)∪πB(R)∪πC(R)={{a1,

a2},

{b1,

b2},

{c1,

c2}}不限制时，{t|

﹁R(t)}只要取不属于R的元组即可，为无限关系，如图3.15（b）。如果进行限定：要求Ψ（t）为真的元组各分量的值来自DOM（Ψ），则此时构成关系如图3.15（c）(Ψ是DOM（Ψ）中各域的笛卡尔乘积与R的差集)

，

而且是惟一的，有限关系。

所以施加限制，

{t|

﹁

R(t)}演算结果将会变得安全。图3.15

符号集求解用例关系3.4

查询优化查询检索是数据库系统最主要的应用功能。查询速度的快慢直接影响系统效率。关系模型主要的缺点是查询效率低。查询效率不高普遍存在于非过程化语言系统。非过程化语言:用户只需指出“做什么”，而“怎么做”由系统来决定。用户方便，系统负担重.系统效率和数据独立性，用户使用的方便性和系统实现的便利性都是互相矛盾的。查询优化目标：系统自动进行查询优化，使查询性能上达到甚至超过非关系系统。3.4.1

举例关系代数对同一个问题可有不同的解决途径，结果相同，但执行效率有较大差别。E（E＃，

EN，

EA，

EE，

ED）P（P＃，

PN，

PL）Key={E＃}Key={P＃}Key={E＃，

P＃}EP（E＃，

P＃，

L）求：参与了P2项目的职工姓名。解：参与了P2项目的职工姓名Q1=πEN（σE.E＃=EP.E＃∧EP.P＃

=′P2′（E×EP）)Q2=πEN（σEP.P＃

=′P2′（EEP））Q3=πEN（E（σEP.P＃

=′P2′（EP）））Q1、Q2、Q3的执行过程?假定：E中记录数为1000个，EP中记录数为10000个参与P2项目50个，每秒读写20块，一块能装10个E元组或100个EP元组，Q1、的执行过程：①计算广义笛卡尔积。做法：在内存中尽可能多地装入某个表（如E表）的元组，留出一块存放另一个表（如EP表）的元组;如在内存中存放5块E元组，1块EP元组，EP的每个元组和E的每个元组连串，连串后的元组装满一块后写到中间文件上;再从EP中读入一块和内存中的E元组连串，直到EP表处理完。再一次读入若干E元组，读入一块EP元组，重复上述过程，直到把E表处理完。读取块数为：E：1000/10=100块

EP：10000/100=100块EP

需读20遍:（1000/（

10*5

）=20）读取总块数为：100块+100块*20=2100块读E和EP总计需要

2100/20=105秒。E×EP后的元组数?E×EP后的元组数为103×104=107,设每块能装10个元组，写这些块到中间文件花107/（10*20）=5×104秒则计算广义笛卡尔积的时间：读E和EP

的时间+写中间文件的时间105秒+5×104秒②读入E×EP后的中间文件，按照选择条件选满足要求的记录（假定内存处理时间不计）。读取中间文件花费的时间需5×104秒满足条件的元组50个，假设均可放在内存。③把第二步的结果在EN上作投影输出，得到最终结果（假定内存处理时间不计）。Q1执行查询的总时间为:105+2×（5×104），约为105秒。所有内存处理时间均忽略不计。Q2的执行过程：①计算自然连接。读取E和EP表的方式不变，总的读取仍为2100块，花费时间105秒。自然连接的结果是多少条?自然连接的结果为104个，写这些元组花费的时间为104÷10÷20=50秒，②读取中间文件，执行选择运算，花费时间为50秒。③将上一步结果投影输出。执行Q2的总时间为:105秒+50秒+50秒=205秒。Q3的执行过程：①先对EP表做选择运算，只需读一遍EP表，读取100块花费时间为5秒。由于满足条件的元组只有50个，不必使用中间文件。②读取E表，把读入的E元组和内存中的EP元组做连接，读一遍E表共100块，花费时间为5秒。③把连接结果投影输出。总的执行时间为10秒。例子说明了关系数据库进行查询优化的必要性，例子说明了那些初步的查询优化的方法？3.4.2

查询优化准则查询优化主要是合理安排操作的顺序，以使系统效率较高。优化策略：(1)尽可能早地执行选择操作。最基本最重要的一条。选择运算使中间结果显著变少，从而使执行时间降低好几个数量级。(2)适当地对文件进行预处理。预处理包括索引和排序。在一些使用频率较高的属性上建立索引或排序，可大大提高存取效率。例如：E

EP，对E和EP按E＃进行索引或排序后，读E中的某一条E＃值，直接定位EP中相应的第一条记录，当扫描到与E＃不相同的第一个EP元组时，再返回E表扫描下一个元组E＃。E和EP均只扫描一遍。同一关系上的投影和选择运算同时进行，减少表的扫描次数。把投影运算同其前或后的双目运算结合起来，没必要为去掉某些属性而扫描一遍关系。把某些选择运算同其前执行的笛卡尔乘积结合起来成为一个连接操作。多次出现的公共子表达式，应将表达式结果预先计算并加以保留，需要时直接从文件读取，以免重复计算。3.4.3

关系代数等价变换规则关系代数表达式的等价，指用不同的关系表达式取得的结果关系是相同的。两个关系代数表达式E1和E2等价，表示为：E1≡E2。常用的等价变换准则有：(1)连接和笛卡尔乘积的交换律。E1和E2是两个关系代数表达式，F是连接运算的条件，则：F

FE1

E2≡E2

E1E1

E2≡E2

E1E1×E2≡E2×E1(2)连接和笛卡尔乘积的结合律。E1和E2是两个关系代数表达式，F1和F2是连接运算的条件，F1只涉及E1和E2的属性，F2只涉及E2和E3的属性，则：F1

F1（E1

E2）

E3≡E1

(E2

E3）（E1

E2）F2

E3≡E1

（E2F2

E3）（E1×E2）×E3≡E1×（E2×E3）E1:S

E2:C

E3:SC?投影的串接律(级联)。E是关系代数表达式，F1、F2和F3是E的属性集，且F1˝

F2

˝

F3，则：πF1（πF2（πF3（E）））≡πF1（E）选择的串接律(级联)。E是两个关系代数表达式，F1和F2是选择运算条件，则：σF1（σF2（E））≡（σF1∧F2（E））(5)选择和投影的交换律。E是关系代数表达式，F是选择条件，F只涉及L中的属性，则：σF（πL（E））≡πL（σF（E））如F还涉及不在L中的属性集L1，则：πL（σF（E））≡

πL（σF

（πL

∪

L1（E））)---规则(5)的一般形式(6)

选择和笛卡尔乘积的分配律。E1和E2是两个关系代数表达式，F是选择条件，且只涉及E1，则：σF（E1×E2）≡σF（E1）×E2若有F=F1∧F2，并且F1只涉及E1中的属性，F2只涉及E2中的属性，则：σF（E1×E2）≡σF1（E1）×σF2（E2）若F=F1∧F2，且F1只涉及E1中的属性，F2涉及到E1和E2中的属性，则：σF（E1×E2）≡σF2（σF1（E1）×E2）选择对并的分配律。E1和E2是两个相容的关系，则：σF（E1∪E2）≡σF（E1）∪σF（E2）选择对差的分配律。E1和E2是两个相容的关系，则：σF（E1－E2）≡σF（E1）－σF（E2）选择对自然连接的分配律。E1和E2是两个关系代数表达式，F只涉及E1和E2的公共属性，则：σF（E1

E2）≡σF（E1）

σF（E2）投影对笛卡尔乘积的结合律。E1和E2是两个关系代数表达式，L1是E1的属性集，L2是E2的属性集，则：1

21

2

L

1L

2(E

·

E

)p

”

p

(EL

L)

p

(E

)(11)投影对并的分配律。E1和E2是两个相容的关系，则：πL（E1∪E2）≡πL（E1）∪πL（E2）(12)选择与连接操作的结合律：E1和E2是两个关系代数表达式，则：σF（E1×E2）≡E1FF2σF1（E1

E2）≡E1E2F1∧F2

E2并与交的交换律。E1∪E2≡E2∪E1E1∩E2≡E2∩E1并与交的结合律。（E1∪E2）∪E3≡E1∪（E2∪E3）（E1∩E2）∩E3≡E1∩（E2∩E3）3.4.4

关系代数表达式优化的算法按优化准则，尽可能早执行选择操作，多步操作组合一步完成，进行适当地预处理，计算公共子表达式等。优化的基本算法如下：算法：关系代数表达式的优化。输入：一个关系代数表达式的语法树。输出：表达式的优化树（算法）。优化的基本方法如下：利用规则(4)把形如（σF1∧F2∧…∧Fn（E））的表达式变换为σF1（σF2（…（σFn（E））…））。对每个选择操作，利用规则(4)~(9)，尽可能把它移到树的叶端。对每个投影操作，利用规则(3)、(5)、(10)、(11)，尽可能把它移到树的叶端。其中规则(3)可使某些投影消失，而规则(5)可能会把一个投影变为两个投影，其中一个有可能被移向树的叶端。(4)

利用规则(3)~(5)，把选择和投影的串接合并成单个的选择、单个投影或一个选择后跟一个投影，使多个选择和投影能同时进行，或在一次扫描中全部完成。(5)

将上述得到语法树的内结点分组，每一双目运算（×，

∪，

-，）和它的直接祖先为一组（直接祖先是σ和π运算），如果其后代直到叶子全是单目运算，则也将它们并入该组；但当双目运算是笛卡尔乘积（×），而且其后的选择不能与它结合为等值连接时除外。3.4.5

关系代数表达式优化步骤将查询转化为关系代数语法树将语法树转换成优化形式。利用等价变换规则，把原始的语法树转换为优化的形式。P63-64

例题结结投投(EN)选选(EP.P#＝'P2')连连(E.E#＝EP.E#)E

EPpENsEP.P#＝'P2'×EEPpENsE.E#＝EP.E#sEP.P#＝'P2'×EEPpENsE.E#＝EP.E#×EsEP.P#＝'P2'EP(a)(b)

(c)图3.16

简单的查询过程优化图解(d)sE.E#＝EP.E#【例3.21】有职工和部门构成的关系数据库：EMP（编号E＃，姓名EN，性别SEX，年龄AGE，工资SAL，部门D＃）DEPT（部门号D＃，部门名DN，管理者号MGR，地址ADD）求出管理者号为18的职工姓名，且他们的工资不超过1500元。解：依据题意可写出如下查询：Q1：

πEN（σ

SAL<1500（σMGR=18（

σEMP.D#=DEPT.D#

（EMP

×

DEPT））））优化树？优化表达式？3.5

关系系统关系数据库系统是目前应用最广泛的数据库系统。实际应用中各类关系产品的功能都是有差异的，根据其支持运算的不同，关系系统可分为(最小)关系系统、完备关系系统、全关系系统。3.5.1

关系系统的定义关系系统的最小要求，当一个系统同时满足以下两点要求时，就是一个最小的关系系统：支持关系数据库。在用户眼里，数据库只有表这种结构。支持关系代数中选择、投影和（自然）连接运算，并且不能要求用户定义任何物理存取路径。仅仅支持关系数据库而不支持选择、投影和连接功能的系统，不是关系系统。支持上述三种运算，但要求用户定义物理存取路径的系统，仍然不是关系系统。关系系统的最大优点在于方便用户，而不支持上述三种运算的系统是不方便用户的。如果一个系统，要求用户定义存取路径才能进行上述三种操作，那么，就丧失了数据的物理独立性，带来操作的复杂性。因此，关系系统必须能自动选择路径，必须能查询优化，这是关系系统的关键技术。上述三种操作并非关系代数的全部运算，但却是最重要、最有用的运算。有了这三种运算功能，就能解决绝大部分的实际问题。3.5.2

关系系统的分类上述关系系统的定义确定了关系系统的基本要求，根据E.F.Codd的思想，关系系统主要分为三类。（最小）关系系统：仅支持关系数据结构和选择、投影、连接三种关系操作。完备关系系统：不仅支持关系数据结构，而且支持所有关系代数操作。(3)全关系系统：支持关系模型所有特征的系统为全关系系统。它们不仅支持数据结构中域的概念，不仅是完备关系，而且支持实体完整性和参照完整性（十二条基本准则）

。目前，很多关系系统已接近这个目标。用图形表示以上关系分类，其中S代表结构、

I代表完整性、M代表数据操纵，图中阴影表示对三类特性的支持程度。图3.18

关系系统的分类（a）

（最小）关系系统;（b）

完备关系系统; (c)

全关系系统SMISMIMIS(a)(b)(c)3.5.3全关系系统的十二条基本准则E.F.codd提出的全关系系统的十二条基本准则，只有遵循这些准则的系统才是全关系系统。准则0：一个RDBMS必须能完全通过自身的关系能力来管理数据库。一个自称为关系型的DBMS必须能在关系这个级别支持数据库的插入、修改和删除。不满足准则0的DBMS都不是RDBMS。准则1：信息准则。RDBMS的所有信息都应在逻辑一级用同一个方法——表（Table）中的值显示出来。而且，每个表的表名，表中的列名和域名等，都是用系统内的数据字典表中的值表示的。数据字典本身是一个描述元数据的关系数据库。准则2：保证访问原则。依靠表名、主码和列名的组合，应保证能够访问关系数据库中的每个数据项值。必须采用关系系统独有的关联寻址的访问模式。准则3：空值的系统化处理。空值是“不知道”或“无意义”的值，它不是一个具体的值（如零、空字符串等）。要用一个系统化的方式处理空值。准则4：基于关系模型的动态联机数据字典。数据库的描述在逻辑级上应和一般数据采用相同的表示方法，使得授权用户能使用查询一般数据所用的关系语言来查询数据库的描述信息。准则5：统一的数据子语言准