第2章 关系型数据库

第2章关系型数据库

主要内容：

●关系数据库概述。

●关系模型的物理与数学定义。

●关系代数运算。

●关系演算：元组演算与域演算。重点：关系代数运算2.1

关系数据库概述关系数据库系统是支持关系模型的数据库系统。关系数据结构关系操作关系完整性约束关系模型由三部分组成：1、关系数据结构关系模型中的数据结构是二维表格。关系模型数学定义为笛卡尔集中的有意义的子集。2、关系操作查询操作更新（增、删、改）操作其中，查询是更新的基础，它是关系最重要和最基本的操作。关系的操作：关系操作的结果：关系（集合）。关系代数:选择、投影、连接、除、并、交、差等。关系元组演算关系域演算关系演算：关系操作的数学表达：常用的关系操作的语言：SQL关系操作语言的特点：具有完备的表达能力。非过程化的集合操作语言。语句即可交互使用又可嵌套到高级语言中使用。3、关系完整性约束关系的完整性：指关系中数据的相容性和正确性。实体完整性参照完整性用户定义完整性

关系三类完整性：关系模型物理表示：二维表格。数学表示：笛卡尔积上有意义的子集。关系模型：直观地说就是用二维表格表示实体集，外键表示实体间联系的数据模型。关系模型表示：一、关系模型的物理表示二维表格表示，如：一张学生注册表学号姓名性别出生年月99019902

…张一王三…男女…80.179.12…行关系模式R(表头)元组1元组2……实体集(文件)r:元组集合(关系)值域(列)

关系模型=关系模式+关系关系模式:它是静态的(不随时间变化),稳定的,它由属性名组成.关系是由元组组成的值集.它是随操作而变化.1、关系模式(relationschema)

组成:取自二维表的表头中的数据.一般组成:关系模式是一个五元组:R(U,D,DOM,F)

其中:R为关系模式名:可取自二维表的表名;不同的关系模式其名不同.U为属性名表:上例:学号,姓名,出生年月,性别;属性名各异.D为属性的域名,指属性取值的类型;如:学号的类型为字符串.DOM为属性的取值的宽度(长度);如:学号取值8个字符(最大).F为属性间依赖关系的集合,表明属性间的语义;如:学号姓名.

关系模式通常简记为:

R(A1,A2,….,An);其中：A1,A2,….,An为属性名。

如:上例:student(sno,name,sex,date)2、关系关系（表体中的数据）：元组的集合。每一个元组描述一个实体，关系对应实体集。

基本表：实际存在的表，实际存储数据的逻辑表示。

查询表：对DB操作后的结果表（结果关系）。

视图(虚表)：由基本表或其他视图导出的表，不对应实际存储数据。注：在实际中，常把关系和关系模式系统称为关系，可根据上下文区分。关系的三种类型：3、基本关系的性质（对关系的限定）关系中每一列（属性）必须是不可再分的基本数据项，且具有同一类型，列名各异，列的排列次序无关紧要。关系中不允许出现相同的元组，元组之间的次序任意。4、关键字（Key）超键：唯一标识元组的属性集。如(sno,name)侯选键：不含多余属性的超键。如sno或name（无同名同姓时）。主键：被选用的侯选键。如：sno或可选name（无同名同姓时）。外键：用来联系关系的键。如：stu(sno,name,sex,date,dno)dno是外键；dept(dno,dname,addr)5、名词对照表人工管理信息世界关系领域层次、网状领域计算机表头表框架关系模式记录型记录型表体实体集关系（元组集）记录值集文件行实体元组记录值记录值列（栏目）属性属性数据项字段列值属性值集属性值集域值字段值识别项实体标识符关键字（键）码（键）码二、关系模型的数学定义关系模型是建立在集合代数的基础之上。关系用笛卡尔积来定义的。

笛卡尔积定义：给定一组域D1，D2，……Dn，这些域可以完全相同或不同或部分相同，则n个集合的笛卡尔积：

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

其中每一个元素（d1,d2,…,dn）称为一个元组；元素中每一个分 量值di称为元组的一个分量。笛卡尔积是一个以元组为元素的集合，且笛卡尔积可以表示一个二维表。例：给定D1={0,1},D2={a,b,c}，则：

D1×D2={(0,a),(0,b),(0,c),(1,a),(1,b),(1,c)}(即每个元组的第一个分量取值为D1,第二个分量取值为D2,……)笛卡尔积的二维表示：D1D201abc×=D1D2000111abcabc基数：2×3=6个元组关系模式的笛卡尔积定义：笛卡尔积D1×D2…×Dn的任一子集称为定义在D1，D2，…，Dn上的一个n元关系模式，简记为:

R（D1，D2，…，Dn)。

注：实际关系数据库中的每一个关系都是一个笛卡尔积的有意义的子集,即其中的每个元组必须符合实际意义。例：设D1={张三，李四}，D2={男，女}则有：D1×D2={（张三，男），（张三，女），（李四，男），（李四，女）}假定：张三本是男，李四本是女，显然（张三，女）和（李四，男）是没有意义的元组,应该去掉。即有意义的子集：

D1×D2={（张三，男），（李四，女）}注意：关系的基数：就是元组的个数。上例：关系的基数为6

关系的元数（度或目）：属性的个数。

上例：关系的元数为2。三、关系完整性为了保证关系模型中数据的正确性和一致性，必须对关系中数据作完整性的约束。三类完整性约束规则：实体完整性约束规则参照完整性约束规则用户自定义约束规则：用户定义，系统检查。系统自动支持1、实体完整性规则关系中所有主属性都不能取空值。而不是仅主关键字不能取空值。组成候选关键字的属性称为主属性。如：选课（学号，课号，成绩）中：主属性学号和课号都应有值，即不能为空值（无值）。2、参照完整性规则

不引用不存在的实体.例：有关系模式s(sno,name,sex,age)sc(sno,cno,grade)其中：sno是s的主关键字，也是sc中的外键，它联系着s与sc，这时称s为参照关系；sc为被参照关系（或称依赖关系）。如果关系sc中有一个元组（s7,c4,80），此时学号s7在关系s中找不到,则认为在sc中引用了一个不存在的学生实体，这就违反了参照完整性规则。3、用户自定义完整性规则用户自定义完整性规则反映某一具体应用涉及的数据必须满足的语义要求。如：学生的“年龄”定义两位整数，则值范围太大；写一条规则，把“年龄”属性取值规定15～30之间。2.3关系代数

关系DB操作语言是以数学中的关系代数和谓词演算为基础研制的。关系查询语言：关系代数语言：以集合代数操作为基础运算的DML（非过程性弱）关系演算语言：以谓词演算为基础的DML（非过程性强）分为：元组关系演算语言域关系演算语言一、关系代数的5种基本操作关系代数的操作：传统的集合运算：∪，-，∩，×扩充的关系运算：π（投影）、σ（选择）、（联接）、÷（除）关系代数完备的且基本的操作集：∪，－，×，∏,σ五种。其它的运算并非基本，都可由这5种操作导出。1、并（∪）设R和S是同类关系（模式相同：属性相同，个数相等），R∪S结果为一同类关系，它由既属于R又属于S中的元组构成的集合。用元组变量形式定义：R∪S≡{t|t∈R∨t∈S};t为元组变量。⋈ABCadcbabcfdABCbdgaaf例：ABCadcbbabgcfdaRSR∪S相同元组只选一个特征：∪为二目运算从“行”上取值作用：在一个关系中插入一个数据集合，自动去掉相同元组。2、差（—）

设R与S为同类关系，则R和S的差是由属于R而不属于S的所有元组组成的集合。用元组变量形式定义：例：ABCacbbcd作用：从某关系中删去另一关系R-S3、笛卡尔积（×）

设R为K1元关系，S为K2元关系，则R×S是一个（K1+K2）元数的集合，其中元组的前K1个分量是R的一个元组，后K2个分量是S的一个元组。共有n×m个元组（n为R元组数，m为S元组数）。用元组变量形式定义：R×S≡{t|t=<t,t>∧t∈R∧t∈S}k1k1k2k2例：ABC142536DEacbdABCDE114422553366acacbdbdRSR×Sk1=3k2=2k1+k2=3+2=5属性n×m=2×2=4个元组特征：“列”合并，“行”组合作用：将两个关系（同类或不同类）无条件地连成一个新关系。4、投影（л

）

在n元关系R（A1，A2，…An）中选取k（k≤n）列属性，并去掉重复元组构成的新关系：R1(A1，A2，…，Ak）。用元组变量定义лi1,i2,…,im(R)≡{t|t=<ti1,…,Tim>∧<t1,…tk>∈R}例：ABC147258369AC147369RЛA，C（R）=Л[1]，[3]（R）若有重复元组应去掉。特征：运算对象为单个关系，在“列”上纵向分割关系。作用：在关系中选取某些列组成一个新关系。5、选择（σ）其中：F由下列成分组成：运算对象：常数（用引号括起来），属性名或属性的列号。

算术比较符：<,≤,>,≥,=,≠;

逻辑运算符：￢，∧,∨用元组变量形式定义：

σF（R）≡{t|t∈R∧F(t)=true}从关系R中挑选满足条件F为真的元组组成新关系，记为σF（R）例：ABCadcbcbcbdABCacbbcdRσB=‘b’(R)≡σ[2]=‘b’(R)特征：对一个关系进行“行”运算，即为横向选择。作用：在一个关系中，选择满足条件的元组构成新关系（关系模式不变）运算符：二、关系代数的4种组合运算包括：交（∩），联接（），自然联接（

）和除法（÷）操作。1.交（∩

）求同类关系R和S中相同的元组的集合.用元组变量形式定义：R∩S≡{t|t∈R∧t∈S}θ例：ABCb2cABCab32bcABCabc124bcdSRR∩S注：R∩S=R-（R-S）用差运算表示。特征：关系模式不变，从两关系中取相同的元组。⋈⋈

2.联接（

）设R（A1，A2，…Ak1）和S（B1，B2，…，Bk2（1≤i≤k1,1≤j≤k2），i，j分别是R和S的第i个分量和第j个分量；θ联接是笛卡尔积中的一个子集，其元组必须符合R的第i个分量值和S的第j个分量值之间的θ关系，记为R

S。用元组变量形式定义：R

S≡{t|=<t,t>∧t∈R∧t∈S∧tθt}

其中：t和t分别表示R中的第i个分量值，和S中第j个分量值，

tθt

表示这两个分量值满足θ操作。θ[i]θ[j]k1k1k1k2k2k2ij[i]θ[j]k1k2ijk2k1ji即：R

S≡σ

(R×S)[i]θ[j][i]θ[j]运算步骤：（1）求R×S

=T（A1，A2，…，Ak1，B1，B2，…Bk2）

RS（2）在T中选择[i]θ[j]成立的元组。⋈⋈⋈⋈例：求R

S=σ[3]>[5](R×S)ABC147258369DEab78ABCDE778899ab78ABCDE114477225588336699ababab787878RS（1）求R×S（2）

σ[3]>[5](R×S)ABCDE789a7[3]>[2]注：当θ为“=”时，R

S称为等值联接。[i]=[j]求：R

S[1]=[2]特征：两个关系不一定有公共属性不去掉重复属性。作用：将两个关系按一定的条件联接在一起。⋈⋈⋈3.自然联接（）自然联接是

的特殊情况。设关系R和S有相同的属性名Ai(i=1,2,…,k)，则R

S是从R×S中挑选R·A1=S·A1∧R·A2=S·A2∧…∧R·Ak=S.Ak的所有元组，并去掉重复属性的元组集合。元组变量形式表示:

{t|t=<t,t>∧(R(t)∧S(t))∧R·A1=S·A1∧R·A2=S·A2∧…∧R·Ai=S·Ai}运算过程：计算R×S挑选R·Ai=S·Ai（即属性名相同，值相等）的所有元组去掉重复属性即：R

S≡лi1,i2,…,im(σ

R·A1=S·A1∧…

∧

R·AK=S·AK(R×S))θ⋈⋈R⋈s=

⋈⋈例:BCD259368235ABC147258369ABCD14253623RS①R×S

③去掉重复属性B,C：R⋈S

ABCS.BS.CD

1

2

3

2

3

2

1

2

3

56

3

1

2

3

9

8

5

4

5

6

2

3

2

4

5

6

5

6

3

4

5

6

9

8

5

7

8

9

2

3

2

7

8

9

5

6

3

7

8

9

9

8

5ABCS.BS.CD

1

2

3

2

3

2

4

5

6

5

6

3②σR.B=S.B∧R.C=S.C(R×S)注：（1）在无公共属性时，自然联接变化为笛卡尔积。（2）等值联接与自然联接的区别：a.等值联接要求相等的属性不一定相同。自然联接要求相等的属性一定相同。b.等值联接不要求去掉重复属性。自然联接要求去掉重复属性。

（3）自然联接是关系DB中最重要的操作之一。4.除法（÷）

设关系R和S分别为m元和n元关系，则R÷S结果为一个m－n元关系。其元组决定为：先将被除关系R中的m－n列按值分成若干组，每个组中参入分组的m－n列以外的那些列中是否包含除关系S的全部元组，包含则取该m－n列的值作为商关系的一个元组，否则不取。用元组变量形式表示:R÷S≡{t|t=<t,t…t>∧若t∈s,则<t,t>∈R}m1n2nnm-nn例:ABCDaaaeebbbddcedcedfedfCDcedfABaebdRSR÷S

三、关系代数表达式及应用用关系代数对关系运算，即写出运算表达方式。步骤：

①根据已知条件确定关系

②根据查询结果确定关系

③根据运算语义写出查询代数表达式。是否其条件属性与结果属性在同一关系中，若不在同一关系中，根据什么属性联系的。例：设DB中有三个关系模式：学生关系：s(s#，sname，age，sex)学习关系：sc（s#，c#，grade）课程关系：c（c#，cname，teacher）用关系代数表达式，表示下列各种查询。1．查找学习课程号为C2的学生的学号与成绩∏s#,grade(σc#=′c2′(sc))(学号、成绩与课程号在同一关系sc中)2．查找选修课程号为C2或为C4的学生的学号∏s#(σc#=′c2′∨c#=′c4′(sc)(学号与课程号在同一关系sc中)或：∏s#(σc#=‘c2’∨c#=‘c4’（лs#,c#(sc)))(说明表达式不唯一)3．查找至少学习C2和C4课程的学生的学号

∏

[1](σ[1]=[4]∧[2]=‘c2’∧[5]=

‘c4’(sc×sc))s#[1]c#[2]grade[3]s#[4]c#[5]grade[6]sc×sc4．查找不学习C2课的学生的姓名与学号

∏sname,s#(s)-∏sname,s#(σc#=‘c2’(s

sc））

错误写法

:∏s#,sname(σc#≠‘c2’(s

sc）)5．查找选修全部课程的学生姓名

∏

sname(s(∏

s#,c#(sc)÷∏

c#(c)))(在三个关系中关联查找)6．查找学习课程名为DB的学生姓名∏sname(s∏

s#(sc

∏

c#(σcname=′DB′(c))))在三个关系中找,或

∏

sname(∏

s#,sname(s)∏s#(лs#,c#(sc)

∏

c#(σcname=‘DB’(C))))课号与姓名不在同一关系中，分别在sc

和s

，但s和sc

通过s#

联系的⋈⋈⋈⋈⋈⋈⋈2.3.3关系代数式的查询优化一.关系DB的查询优化概述

关系DB的查询优化分为：代数优化和物理优化。代数优化：指关系代数表达式的优化。（本节重点）物理优化：指存取路径的选择和低层操作算法的选择。

1.关系DB的查询处理过程查询处理过程：查询分析，查询检查，查询优化，查询执行。查询分析：对查询语句进行扫描，词法分析和语法分析。判断查询语句是否合法。查询检查：根据数据字典，检查查询语句的语义，用户的存取权限和完整性的定义。检查通过后，把SQL语句转换成等价的关系代数表达式。一般用查询树（又称：语法分析树）表示关系代数表达式。查询优化：选择高效执行的查询处理策略。

查询执行：由代码生成器执行根据查询策略生成的查询计划的代码。查询优化过程：查询语句

词法分析，语法分析，语义分析，符号名转换安全性检查，完整性检查

查询树代数优化，物理优化执行策略描述代码生成查询计划的执行代码数据库数据字典查询语句代数表达式的语法分析树物理优化策略查询优化代码代码生成器

2.关系代数运算的优化问题

问题：选择怎样的关系代数表达式表示查询，省时，省空间，速度快呢？

例：有三个等价的关系代数表达式E1，E2，E3：

E1=лA（σB=C∧D=’99’（R×S）)，先做笛卡尔积，后做选择和投影。

E2=лA（σB=C（R×σ

D=’99’（S））)，先做选择，后做笛卡尔积。

E3=л

A（R（σ

D=’99’（S）），先做选择，后做联接。注：E1：先做笛卡尔积，占大量的内存空间。

E2和E3:先对S做选择操作会减少大量的元组，再与R做联接时，内存空间花费小，存取的次数少，花费CUP的时间少。

关系代数运算的优化原则：在保证语义正确的情况下，先安排选择，投影运算，然后进行笛卡尔积，联接运算。

B=C⋈二.关系代数表达式的优化算法利用等价变换规则（见p53）对关系代数表达式优化的算法如下：算法：输入：关系代数表达式的一棵语法树。（树中的叶子结点是关系，非叶子结点是操作符）输出：计算该表达式的优化程序。算法思想：

①.利用变换规则将表达式写成只包含五种关系代数的基本运算(∪，－，×，∏，σ)，绘出表达式的语法树；

②.将选择操作尽量向叶子结点移动（即，先做选择操作）；然后，将投影操作尽量向叶子结点移动（即，后做投影操作）。最后得到一棵表达式的优化的语法树。

③.对优化的语法树，由下至上扫描，就是计算该表达式的优化程序。例子：教学数据库：S(SNO,SNAME,AGE,SEX);SC(SNO,CNO,GRADE);C(CNO,CNAME,TEACHER)。

有一查询：查询至少学习LI老师所授一门课的女学生的学号与姓名。关系代数表达式：

л

SNO，SNAME（σ

TEACHER=’LI’

∧SEX＝‘

F’（SCCS））

(1)

建立语法树将上式中的用л,σ,×操作表示：

л

SNO，SNAME（σ

TEACHER=’LI’

∧SEX＝‘

F’(лL(σ

SC.CNO=C.CNO∧SC.SNO＝S.SNO

（SC×C×S）))）其中：L为：SNO,SNAME,AGE,SEX,CNO,CNAME,GRADE,TEACHER.⋈⋈⋈语法树如下：л

|SNO，SNAME

σ

|TEACHER=‘LI’∧SEX=‘F’

л|L:SNO,SNAME,AGE,SEX,CNO,CNAME,GRADE,TEACHER.

σ

|SC.CNO=C.CNO∧SC.SNO=S.SNO

××SSCC(2).优化处理

.分裂选择的条件，并尽量向叶子结点移动；（先执行选择操作）

.分布投影条件；（后执行投影操作）。优化的语法树：л

|SNO，SNAME

σ

|SC.SNO=S.SNO

×

л

л

|SC.SNO|S.SNO,SNAME

σ

σ

|SC.CNO=C.CNO|SEX=‘F’

×S

л

л

|

SC.CNO,SC.SNO

|C.CNO

SC

σ

|TEACHER=‘LI’C

执行时，从叶子端依次向上扫描。2.4关系演算把数理逻辑的谓词引入到关系中的运算。元组关系运算：以元组为变量。域关系运算：以属性（域）为变量。关系演算：一、元组关系运算（tuplerelationcalculus）1．元组运算表达式一般形式：{t|p(t)}其中：t为元组变量；P（t）是由原子公式和运算符组成的公式。含义：满足公式P所有元组的集合。（1）原子公式a．R（t）：R为关系名，t为元组变量。含义：t为R中的任意一个元组。b.t[i]θu[j]：t和u是元组变量，t[i]和u[j]为分量，θ是算术比较符。含义：元组t的第i个分量与元组u的第j个分量满足θ关系为真。例：t[3]﹥u[2]：t的第3个分量值大于u的第2个分量值时为真。c.t[i]θc或cθu[j]:c为常量。含义：元组t的第i分量与常量c满足θ关系时为真。例：t[2]=2:表示元组t的第2个分量的值等于2时为真。（2）运算符θ算术比较符>，≥，<，≤，=，≠存在量词：

和全程量词:

逻辑运算符：￢（非），

∧（与），∨（或）括号运算优先级最高低高高低2．元组运算例：设有关系R和S如下A1A2A31790afec1895A1A2A31342aacb1540RS计算下列元组表达式的值:(1)R1={t|R(t)∧￢s(t)}≡R-SA1A2A3342acb540R1A1A2A313aa15R2(2)R2={t|R(t)∧

t[2]=a}≡σ[2]

=‘a’(R)说明：若t作为R的元组变量：R(t)，则t[1],t[2],t[3]分量分别表示A1,A2,A3(3)R3={t|(

u)(R(t)∧s(u)∧t[1]<u[3]∧t[2]≠b)}

≡σR[1]<S[3]∧R[2]≠b(R×S)(4)R4={t|（

u)(R(u)∧t[1]=u[3]∧t[2]=u[1])}≡∏

[3],[1]

(R)(5)R5={t|(

u)(

v)(R(u)∧S(v)∧u[1]>V[1]∧t[1]=u[2]∧t[2]=v[2]∧t[3]=u[1])}R·A2S·A2R·A1aaaccbbcacacac1334422A1A2A3143aca145A3A115401342R5R4R3例：已知学生关系模式S（Sno,Sname,age,sex）用元组演算表达式表示查询查询所有男同学姓名和学号:{t|(

u)(S(u)∧u[4]=‘男’∧

t[1]=u[2]∧t[2]=u[1])}二、域关系运算(domainrelationcalculus)域关系表达式一般形式：{X1，X2……,XK∣φ(X1，X2……,XK

)}

其中：X1，X2……Xk表示关系中的域变量；φ是原子公式与运算符组成的公式

含义：所有使得φ为真的那些X1，X2……XK组成的元组集合。

R（X1，X2，……XK）；R为K元关系,Xi为常量或域变量含义：由分量X1，X2……，XK组成的元组属于R.

XiθC或CθXi：C为常量，Xi为域变量;θ为运算符，含义同前

XiθXj

：xi和yj

分别为元组X和Y的域变量。原子公式：例：设关系R和S，W如下：DEF254abcdefABC552bdc634ABC541bac168RSW计算（1）R1={xyf|R(xyf)∧(f>5

∨

y=a)}(2)R2={xyf|R(xyf)∨S(xyf)∧x=5

∧

f≠6}(3)R3={xyf|(

v)(

u)(R(yxu)∧

w(vTf)

∧

u＞v)}ABC41ac68BAFaaaccc444111defdefABC5415bacd1683R1R2R32．域演算例子将元组表达式化为等价的域表达式方法：元组变量t,用域变量名替代：对于k元的元组变量t，引入k个域变量t1,t2,…,tk；在公式中t,用t1，t2，…，tk替换。元组分量t[i]，用域变量名ti替换。每个量词（

u）或（

u）元组变量u,用域变量u1，u2，…um代替。u[i]用ui

替换例：{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)}化简：{w1w2|(

u2)(R(w1u2)∧S(u2w2))}例：已知关系SC（Sno，Cno，grade）用域表达式表示下列查询:查找课程号为“1”的学生学号和成绩第一步首先写成元组表达式：

{t|(

u)(SC(u)∧u[2]=‘1’∧t[1]=u[1]∧t[2]=u[3])}第二步，将元组表达式转换域表达式

{t1t2|(

u1)(

u2)(

u3)(SC(u1u2u3)∧u2=‘1’∧t1=u1∧t2=u3)