《【教学课件】第3章关系数据库的基本理论.ppt》由会员分享,可在线阅读,更多相关《【教学课件】第3章关系数据库的基本理论.ppt(62页珍藏版)》请在三一办公上搜索。
1、第3章 关系数据库的基本理论,冯万利,本章重要概念,(1)基本概念关系数据模型,关键码(主键和外键),关系的定义和性质,三类完整性规则,ER模型到关系模型的转换规则,过程性语言与非过程性语言。(2)关系代数五个基本操作,四个组合操作,七个扩充操作。(3)关系代数表达式的优化关系代数表达式的等价及等价转换规则,启化式优化算法。,主要内容,3.1关系数据模型3.1.1 关系模式 3.1.2 关系操作3.2关系模型的完整性规则3.2.1 关系的三类完整性约束3.2.2 实体完整性3.2.3 参照完整性3.2.4 用户自定义完整性3.3关系代数的基本运算3.3.1 传统的集合运算3.3.2 专门的关系
2、运算3.3.3 关系代数表达式及其应用实例,*3.4关系演算元组关系演算域关系演算3.5 查询优化3.5.1 查询优化的一般策略3.5.2 代数表达式的等价变换规则3.5.3 优化算法,3.1关系数据模型,3.1.1 关系模式,每个关系都有一个模式,称为关系模式(Relation Schema),由一个关系名及它的所有属性名构成。在关系模式中,字段称为属性,字段值称为属性值,记录类型称为关系模式。在图3.1中:关系模式名是R记录称为元组(tuple)元组的集合称为关系(relation)或实例(instance)一般用前面的大写英语字母A、B、C、表示单个属性,用后面的大写字母、W、X、Y、Z
3、表示属性集,用小写字母表示属性值。,数据库技术的术语 关系模型的术语,关系具有的特点,关系(表)可以看成是由行和列交叉组成的二维表格。它表示的是一个实体集合。表中一行称为一个元组,可用来表示实体集中的一个实体。表中的列称为属性,给每一列起一个名称即属性名,表中的属性名不能相同。列的取值范围称为域,同列具有相同的域,不同的列可有相同的域。例如,SEX的取值范围是M(男),F(女),AGE为整数域。表中任意两行(元组)不能相同。能惟一标识表中不同行的属性或属性组称为主键。,关系的性质,属性值是原子的,不可分解。没有重复元组。没有行序。理论上没有列序,但一般使用时都有列序。,关键码和表之间的联系,超
4、键:在一个关系中,能惟一标识元组的属性或属性集称为关系的超键。候选键:如果一个属性集能惟一标识元组,且又不含有多余的属性,那么这个属性集称为关系的候选键。主键:若一个关系中有多个候选键,则选其中的一个为关系的主键。外键:若一个关系R中包含有另一个关系S的主键所对应的属性组F,则称F为R的外键。并称关系S为参照关系,关系R为依赖关系。,关系模式举例,例如,学生关系和系部关系分别为:学生(SNO,SNAME,SEX,AGE,SDNO)系部(SDNO,SDNAME,CHAIR)学生关系的主键是SNO,系部关系的主键为SDNO,在学生关系中,SDNO是它的外键。更确切地说,SDNO是系部表的主键,将它
5、作为外键放在学生表中,实现两个表之间的联系。在关系数据库中,表与表之间的联系就是通过公共属性实现的。我们约定,在主键的属性下面加下划线,在外键的属性下面加波浪线。,关系模式、关系子模式和存储模式,例3.1 下图是一个教学模型的实体联系图。实体类型“学生”的属性SNO、SNAME、SEX、AGE、SDEPT分别表示学生的学号、姓名、性别、年龄和学生所在系部;实体类型“课程”的属性CNO、CNAME、CDEPT、TNAME分别表示课程号、课程名、课程所属系和任课教师。学生用S表示,课程用C表示。S和C之间有M:N的联系(一个学生可选多门课程,一门课程可以被多个学生选修),联系类型SC的属性成绩用G
6、RADE表示。右图表示的实体联系图(ER图)。,关系模式是对关系的描述,它包括模式名,组成该关系的诸属性名、值域名和模式的集合。具体的关系称为实例。,关系模式,该图表示的学生情况的部分转换成相应的关系模式为:S(SNO,SNAME,SEX,AGE,SDPET)关系模式S描述了学生的数据结构,它是下表中学生实体的关系模式。其中SNO,CNO为关系SC的主键,SNO、CNO又分别为关系SC的两个外键。,学生关系实例如下表;选修关系实例如右表。,关系模式(9),课程关系实例如下表:,关系子模式,用户使用的数据不直接来自关系模式中的数据,而是从若干关系模式中抽取满足一定条件的数据构成关系子模式。关系子
7、模式是用户所需数据结构的描述,其中包括这些数据来自哪些模式和应满足哪些条件。例3.2 用户需要用到成绩子模式G(SNO,SNAME,CNO,GRADE)。子模式G对应的数据来源于表S和表SC,构造时应满足它们的SNO值相等。子模式G的构造过程如下图所示。,关系子模式,一 一对应,描述关系是如何在物理存储设备上存储的。关系存储时的基本组织方式是文件。由于关系模式有键,因此存储一个关系可以用散列方法或索引方法实现。如果关系中元组数目较少(100以内),那么也可以用堆文件方式实现。此外,还可以对任意的属性集建立辅助索引。,存储模式,关系模型中常用的关系操作包括查询(Query)操作和插入(Inser
8、t)、删除(Delete)、修改(Update)操作。查询操作又可以分为:选择(Select)、投影(Project)、连接(Join)、除(Divide)、并(Union)、差(Except)、交(Intersection)、笛卡尔积等。基本操作:选择、投影、并、差、笛卡尔积。其他操作:可以用基本操作来定义和导出的。关系操作的特点是集合操作方式,即操作的对象和结果都是集合。这种操作方式也称称为一次一集合(set-at-a-time)的方式。相应地,非关系数据模型的数据操作方式则为一次一纪录(record-at-a-time)的方式。,3.1.2 关系操作,关系语言是一种高度非过程化的语言,用
9、户不必请求DBA为其建立特殊的存取路径,存取路径的选择由RDBMS的优化机制来完成。,关系数据语言的分类,关系数据语言分为三类:关系代数、元组关系演算和域关系演算。该三种语言在表达能力上是完全等价的。,3.2 关系模型的完整性规则,主要内容,3.2.1 关系的三类完整性约束3.2.2 实体完整性3.2.3 参照完整性3.2.4 用户定义完整性,关系模型的完整性规则,关系模型中有三类完整性约束:实体完整性、参照完整性和用户定义的完整性。实体完整性和参照完整性是关系模型必须满足的完整性约束条件,被称作是关系的两个不变性,应该由关系系统自动支持。用户定义的完整性是应用领域需要遵循的约束条件,体现了具
10、体领域中的语义约束。,规则3.1 实体完整性(Entity Integrity)规则:若属性(指一个或一组属性)A是基本关系R的主属性。则A不能取空值。例如:在关系S(SNO,SNAME,SEX,AGE,SDPET)中,SNO这个属性为主码,则SNO不能取空值。,3.2.1 关系的三类完整性约束,实体完整性要求关系中元组在组成主键的属性上不能有空值。如果出现空值,那么主键值就起不了惟一标织元组的作用。,对于实体完整性规则几点说明,实体完整性规则是针对基本关系而言的。一个基本关系通常对应现实世界的一个实体集。例如学生关系对应于学生的集合。现实世界中的实体是可区分的,即它们具有某种唯一性标识。例如
11、每个学生都是独立的个体,是不一样的。关系模型中以主码作为唯一性标识。主码中的属性即主属性不能取空值。如果主属性取空值,就说明存在某个不可标识的实体,即存在不可区分的实体,这与第点相矛盾,因此这个规则称为实体完整性。,定义2.3 参照完整性规则的形式定义如下:如果属性集K是关系模式R1的主键,K也是关系模式R2的外键,那么在R2的关系中,K的取值只允许两种可能,或者为空值,或者等于R1关系中某个主键值。这条规则的实质是“不允许引用不存在的实体”。在上述形式定义中,关系模式R1的关系称为“参照关系”,关系模式R2的关系称为“依赖关系”。,参照完整性规则,由参照完整性建立了多表之间的对应关系,参照完
12、整性规则举例,例2.1 下面各种情况说明了参照完整性规则在关系中如何实现的。在关系数据库中有下列两个关系模式:S(S#,SNAME,AGE,SEX)SC(S#,C#,GRADE)据规则要求,关系SC中的S#值应该在关系S中出现。如果关系SC中有一个元组(S7,C4,80),而学号S7却在关系S中找不到,那么我们就认为在关系SC中引用了一个不存在的学生实体,这就违反了参照完整性规则。另外,在关系SC中S#不仅是外键,也是主键的一部分,因此这里S#值不允许空。,设工厂数据库中有两个关系模式:DEPT(D#,DNAME)EMP(E#,ENAME,SALARY,D#)车间模式DEPT的属性为车间编号、
13、车间名,职工模式EMP的属性为工号、姓名、工资、所在车间的编号。每个模式的主键与外键已标出。在EMP中,由于D#不在主键中,因此D#值允许空。,参照完整性规则举例,参照完整性规则举例,设课程之间有先修、后继联系。模式如下:R(C#,CNAME,PC#)其属性表示课程号、课程名、先修课的课程号。如果规定,每门课程的直接先修课只有一门,那么模式R的主键是C#,外键是PC#.。这里参照完整性在一个模式中实现。即每门课程的直接先修课必须在关系中出现。,用户定义的完整性规则,在建立关系模式时,对属性定义了数据类型,即使这样可能还满足不了用户的需求。此时,用户可以针对具体的数据约束,设置完整性规则,由系统
14、来检验实施,以使用统一的方法处理它们,不再由应用程序承担这项工作。例如学生的年龄定义为两位整数,范围还太大,我们可以写如下规则把年龄限制在1530岁之间:CHECK(AGE BETWEEN 15 AND 30),3.3 关系代数的基本运算,主要内容,传统的集合运算专门的关系运算关系代数表达式及其应用实例,并(Union)设关系R和S具有相同的关系模式,R和S的并是由属于R或属于S的元组构成的集合,记为RS。形式定义如下:RSt|tR tS,t是元组变量,R和S的元数相同。差(Difference)设关系R和S具有相同的关系模式,R和S的差是由属于R但不属于S的元组构成的集合,记为RS。形式定义
15、如下:RS t|tR tS,R和S的元数相同。,传统的集合运算,举例,关系运算举例,交运算,交(intersection)关系R和S的交是由属于R又属于S的元组构成的集合,记为RS,这里要求R和S定义在相同的关系模式上。形式定义如下:RSttR tS,R和S的元数相同。,例,R,S,R S,笛卡儿积运算,若R有m个元组,S有n个元组,则RS有mn个元组。,笛卡儿积(Cartesian Product)设关系R和S的元数分别为r和s,定义R和S的一个(r+s)元的元组集合,每个元组的前r个分量来自R的一个元组,后s个分量来自S的一个元组,记为RS。RS t|t=trRtsS,专门的关系运算,选择
16、(Selection)选择操作是根据某些条件对关系做水平分割,即选取符合条件的元组。条件可用命题公式(即计算机语言中的条件表达式)F表示。F中的基本形式为:X1Y1:其中表示比较运算符:,。X1,Y1等是属性名,常量,或列序号。关系R关于公式F的选择操作用F(R)表示,形式定义为:F(R)t|tR F(t)=true 为选择运算符,F(R)表示从R中挑选满足公式F为真的元组所构成的关系。例如,23(R)表示从R中挑选第2个分量值大于3的元组所构成的关系。书写时,为了与属性序号区别起见,常量用引号括起来,而属性序号或属性名不要用引号括起来。,投影(Projection),这个操作是对一个关系进行
17、垂直分割,消去某些列,并重新安排列的顺序。设关系R是k元关系,R在其分量Ai1,Aim(mk i1,im,为1到k间的整数)上的投影用i1,.,im(R)表示,它是一个m元元组集合,形式定义为:i1,im(R)t|tti1,timt1,tkR 例如,3,1(R)表示关系R中取第1、3列,组成新的关系,新关系中第1列为R的第3列,新关系的第2列为R的第1列。如果R的每列标上属性名,那么操作符的下标处也可以用属性名表示。例如,关系R(A,B,C),那么C,A(R)与3,1(R)是等价的。,连接有两种:连接和F连接(这里是算术比较符,F是公式)。连接 R St t=trR tsS 表达式 表示元组t
18、r的第i个分量、元组ts的第j个分量满足操作。F连接 F连接是从关系R和S的笛卡儿积中选取属性间满足某一公式F的元组,这里F是形为F1F2Fn的公式,每个FP是形ij的式子,而i和j分别为关系R和S的第i、第j个分量的序号。,连接(join)运算,ij,例 连接和F连接的例子.,24(RS),连接运算举例,两个关系R和S的自然连接 操作具体计算过程如下:计算RS;设R和S的公共属性是A1,AK,挑选RS中满足R.A1=S.A1,R.AK=S.AK的那些元组;去掉S.A1,S.AK这些列。定义:中i1,im为R和S的全部属性,但公共属性只出现一次。,自然连接(natural join),关系R,
19、关系S,一般连接 R S,等值连接 R S,自然连接 R S,连接运算举例,两个关系R和S在做自然连接时,选择两个关系在公共属性上值相等的元组构成新的关系。此时,关系R中某些元组有可能在S中不存在公共属性上值相等的元组,从而造成R中这些元组在操作时被舍弃了,同样,S中某些元组也可能被舍弃。如果把舍弃的元组也保存在结果关系中,而在其他属性上填空值(Null),那么这种连接就叫做外连接(Outer join)。如果只把左边关系R中要舍弃的元组保留就叫做左外连接(Left outer join或Left join),如果只把右边关系S中要舍弃的元组保留就叫做右外连接(Right outer join
20、或Right join)。,专门的关系运算,关系R 关系S,外连接,左外连接,右外连接,外连接的例子,除法(division),设关系R和S的元数分别为r和s(设rs0),那么RS是一个(r-s)元的元组的集合。(RS)是满足下列条件的最大关系:其中每个元组t与S中每个元组u组成的新元组必在关系R中。RS1,2,r-s(R)-1,2,r-s(1,2,r-s(R)S)-R),除法举例,关系代数运算的应用实例(1),在关系代数运算中,把由五个基本操作经过有限次复合的式子称为关系代数表达式。这种表达式的运算结果仍是一个关系。例2.7 设教学数据库中有三个关系:学生关系 S(S#,SNAME,AGE,
21、SEX)选课关系 SC(S#,C#,GRADE)课程关系 C(C#,CNAME,TEACHER)用关系代数表达式表示查询语句。(1)检索学习课程号为C2的学生学号与成绩。S#,GRADE(C#=C2(SC)(2)检索学习课程号为C2的学生的学号与姓名。S#,SNAME(C#=C2(S SC)(3)检索选修课程名为MATHS的学生学号与姓名。S#,SNAME(CNAME=MATHS(S SC C),(4)检索选修课程号为C2或C4的学生学号。S#(C#=C2 C#=C4(SC)(5)检索至少选修课程号为C2和C4的学生学号。1(1=42=C2 5=C4(SCSC)(6)检索不学C2课的学生姓名与
22、年龄。SNAME,AGE(S)-SNAME,AGE(C#=C2(S SC)(7)检索学习全部课程的学生姓名。学生选课情况可用操作S#,C#(SC);全部课程可用操作C#(C)表示;学了全部课程的学生学号可用除法操作表示,操作结果是学号S#集;S#,C#(SC)C#(C)从S#求学生姓名SNAME,可以用自然连接和投影操作组合而成:SNAME(S(S#,C#(SC)C#(C)(8)检索所学课程包含学生S3所学课程的学生学号。学生选课情况可用操作S#,C#(SC)表示;学生S3所学课程可用操作C#(S#=S3(SC)表示;所学课程包含学生S3所学课程的学生学号,可以用除法操作求得:S#,C#(SC
23、)C#(S#=S3(SC),S(S#,SNAME,AGE,SEX)SC(S#,C#,GRADE)C(C#,CNAME,TEACHER),关系代数运算的应用实例(2),关系代数运算的应用实例(3),一般地有下列规律:(1)对于只涉及到选择、投影、连接的查询可用下列表达式表示:(RS)或者(R S)(2)对于否定的操作,一般要用差操作表示,例如“检索不学C2课的学生姓名”。用下列表达式表示:SNAME(S)-SNAME(CNO=C2(S SC)但不能用下式表示:SNAME(CNOC2(S SC)对于检索具有“全部”特征的操作,一般要用除法操作表示,例如“检索学习全部课程的学生学号”。用下列表达式表
24、示:要用SNO,CNO(SC)CNO(C)表示,而不能写成 SNO(SCCNO(C)形式。这是因为一个学生学的课程的成绩可能是不一样的。,3.5 查询优化,主要内容,查询优化的一般策略代数表达式的等价变换规则优化算法,例 设关系R和S都是二元关系,属性名分别为A,B和C,D。设有一个查询可用关系代数表达式表示:E1=A(B=CD=99(RS)也可以把选择条件D=99移到笛卡儿积中的关系S前面:E2=A(B=C(RD=99(S)还可以把选择条件BC与笛卡儿积结合成等值连接形式:E3=A(R D=99(S)这三个关系代数表达式是等价的,但执行的效率大不一样。显然,求El,E2,E3的大部分时间是花
25、在连接操作上的。,查询优化例子,可以分析出,在时空性能上,E3最优,其次是E2,最后是E1。此例还可以看出,如何安排选择、投影和连接的顺序是个很重要的问题。,查询优化的一般策略(1),在关系代数表达式中需要指出若干关系的操作步骤。那么,系统应该以什么样的操作顺序,才能做到既省时间,又省空间,而且效率也比较高呢?这个问题称为查询优化问题。查询优化是实现关系系统的关键技术,它大大减轻了用户选择存取路径的负担,用户使用关系系统时,只要提出“做什么”,不必指出“怎么做”。在关系代数运算中,笛卡儿积和连接运算是最费时间的。,查询优化的一般策略(2),查询优化采用的一般策略是:尽可能早地执行选择运算。在查
26、询中这种变换最为重要,因为它可以以元组为单位减小中间结果,从而使执行时间成数量级地减少。把先做笛卡儿积,后做选择结合起来。使之成为一个连接运算。连接运算(特别是等值连接)要比笛卡儿积运算效率高得很多。当对笛卡儿积RS的结果再做选择时,并且这个选择是对R和S的属性进行比较,在这样的条件下,这个笛卡儿积和选择运算等价于一个连接。一般对不含R的属性或不含S的属性的比较,可以移到笛卡儿积运算前去做,这样做比转换到连接更好。同时计算一串选择和一串投影运算,以免分开运算造成多次扫描文件,从而节省了操作时间。找出表达式里的公共子表达式。如果公共子表达式的结果不是很大,并且从外存读入比起计算它要节省许多时间,
27、那么,预先计算一下这个公共子表达式是有好处的。子表达式内涉及到连接,但又不能把限定条件向内移入的那类表达式,一般属于这一类。,连接和笛卡儿积的交换律 E1 E2E2 E1 E1 E2 E2 E1 E1E2 E1E2连接和笛卡儿积的结合律(E1 E2)E3E1(E2 E3)(E1 E2)E3E1(E2 E3)(E1E2)E3 E1(E2E3)投影的串接 设L1,设L2,Ln为属性集,并且,那么下式也成立.选择的串接,代数表达式的等价变换规则(1),选择和投影操作的交换,代数表达式的等价变换规则(2),选择对笛卡儿积的分配律,这里要求F只涉及到E1中的属性。如果F形为F1F2,且F1只涉及到E1的
28、属性,F2只涉及到E2的属性,则有,此外,如果F形为F1F2,且F1只涉及到E1的属性,F2只涉及到E1和E2的属性,则有:,选择对并的分配律 E1和E2具有相同的属性名,或者E1和E2表达的关系的属性有对应性,则有:,代数表达式的等价变换规则(3),选择对集合差的分配律 E1和E2的属性有对应性,则有:,选择对自然联接的分配律 F只涉及到表达式E1和E2的公共属性,则有:(E1 E2)(E1)(E2),投影对笛卡尔的分配律 L1是E1中的属性集,L2是E2中的属性集,则有:,投影对并的分配律 E1和E2的属性有对应性,则有:,代数表达式的等价变换规则(4),选择与联接操作的结合,(E1,并和
29、交的交换律 E1E2E2E1 E1E2E2E1,并和交的结合律(E1E2)E3E1(E2E3)(E1E2)E3E1(E2E3),优化算法(1),代数优化是利用上面的等价变换规则,对关系表达式进行优化,以减少执行时的开销。虽然不能保证最优,但在多数情况下能使表达式更好些。在关系代数表达式中,最花费时间和空间的运算是笛卡儿积和连接操作,为此,引出三条启发式规则,用于对表达式进行转换,以减少中间关系的大小。优先应用单项的选择和投影;优先应用一般选择和投影;对笛卡儿积、并运算、差运算,若它们前面加有选择和投影,则先做选择和投影。,优化算法(2),算法:关系代数表达式的优化。输入:一个关系代数表达式的语
30、法树 输出:计算表达式的一个优化序列 方法:把,对每个选择,尽可能地将选择向树的叶端移动。,对每个投影,尽可能地向树的叶端移动。说明:过程中可能使某些投影操作消失;也可能把一个投影分成两个,其中一个将 靠近叶端;也可能消去该投影操作。,把选择和投影合并成单个选择、单个投影或一个选择后跟一个投影。,将上述步骤得到的语法树的内结点分组。,产生一个程序,上述每一组是这程序的一步,且先执行后代结点组。,优化算法(3),例3.14 对于如下关系数据库:S(S#,SNAME,AGE,SEX)SC(S#,C#,GRADE)C(C#,CNAME,TEACHER)现有一个查询语句:检索至少学习LIU老师所授一门
31、课程的女生的学号和姓名。该查询语句的关系代数表达式如下:,SC,S),也可以得下式:,S.S#,SNAME,语法树,优化算法(4),(1)将每个选择操作分裂成两个选择运算:,(2)将四个选择操作尽可能向树的叶端靠拢,并把两个投影合并为一个投影。见图 2.23,过程中的语法树,(3)把投影和选择进行交换,并在前增加一个投影操作。,新增加的投影,优化算法(5),C,SC.S#=S.S#,S,做投影,做投影,再把该投影往叶端移,优化算法(6),SC.S#=S.S#,S.S#,SNAME,SEX=F,C.C#=SC.C#,(4)执行时从叶端以次向上进行,每组运算只对关系一次扫描。,优化的语法树及其分组,