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 传统的集
2、合运算 3.3.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、
3、B、C、表示单个属性,用后面的大写字母、W、X、Y、Z表示属性集,用小写字母表示属性值。,数据库技术的术语 关系模型的术语,关系具有的特点, 关系(表)可以看成是由行和列交叉组成的二维表格。它表示的是一个实体集合。 表中一行称为一个元组,可用来表示实体集中的一个实体。 表中的列称为属性,给每一列起一个名称即属性名,表中的属性名不能相同。 列的取值范围称为域,同列具有相同的域,不同的列可有相同的域。 例如,SEX的取值范围是M(男),F(女),AGE为整数域。 表中任意两行(元组)不能相同。能惟一标识表中不同行的属性或属性组称为主键。,关系的性质,属性值是原子的,不可分解。 没有重复元组。 没有
4、行序。 理论上没有列序,但一般使用时都有列序。,关键码和表之间的联系,超键:在一个关系中,能惟一标识元组的属性或属性集称为关系的超键。 候选键:如果一个属性集能惟一标识元组,且又不含有多余的属性,那么这个属性集称为关系的候选键。 主键:若一个关系中有多个候选键,则选其中的一个为关系的主键。 外键:若一个关系R中包含有另一个关系S的主键所对应的属性组F,则称F为R的外键。并称关系S为参照关系,关系R为依赖关系。,关系模式举例,例如,学生关系和系部关系分别为: 学生(SNO,SNAME,SEX,AGE,SDNO) 系部(SDNO,SDNAME,CHAIR) 学生关系的主键是SNO,系部关系的主键为
5、SDNO,在学生关系中,SDNO是它的外键。 更确切地说,SDNO是系部表的主键,将它作为外键放在学生表中,实现两个表之间的联系。 在关系数据库中,表与表之间的联系就是通过公共属性实现的。 我们约定,在主键的属性下面加下划线,在外键的属性下面加波浪线。,关系模式、关系子模式和存储模式,例3.1 下图是一个教学模型的实体联系图。实体类型“学生”的属性SNO、SNAME、SEX、AGE、SDEPT分别表示学生的学号、姓名、性别、年龄和学生所在系部;实体类型“课程”的属性CNO、CNAME、CDEPT、TNAME分别表示课程号、课程名、课程所属系和任课教师。学生用S表示,课程用C表示。S和C之间有M
6、:N的联系(一个学生可选多门课程,一门课程可以被多个学生选修),联系类型SC的属性成绩用GRADE表示。右图表示的实体联系图(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以内),那么也可以用堆文件方式实现。此外,还可以对任意的属性集
8、建立辅助索引。,存储模式,关系模型中常用的关系操作包括查询(Query)操作和插入(Insert)、删除(Delete)、修改(Update)操作。 查询操作又可以分为:选择(Select)、投影(Project)、连接(Join)、除(Divide)、并(Union)、差(Except)、交(Intersection)、笛卡尔积等。 基本操作:选择、投影、并、差、笛卡尔积。 其他操作:可以用基本操作来定义和导出的。 关系操作的特点是集合操作方式,即操作的对象和结果都是集合。这种操作方式也称称为一次一集合(set-at-a-time)的方式。相应地,非关系数据模型的数据操作方式则为一次一纪录(
9、record-at-a-time)的方式。,3.1.2 关系操作,关系语言是一种高度非过程化的语言,用户不必请求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关系中某个主键值。这条规则的实质是“不允许引用不存在的实体”。在上述形式定义中,关系模式
12、R1的关系称为“参照关系”,关系模式R2的关系称为“依赖关系”。,参照完整性规则,由参照完整性建立了多表之间的对应关系,参照完整性规则举例,例2.1 下面各种情况说明了参照完整性规则在关系中如何实现的。 在关系数据库中有下列两个关系模式:S(S#,SNAME,AGE,SEX)SC(S#,C#,GRADE) 据规则要求,关系SC中的S# 值应该在关系S中出现。如果关系SC中有一个元组(S7,C4,80),而学号S7却在关系S中找不到,那么我们就认为在关系SC中引用了一个不存在的学生实体,这就违反了参照完整性规则。 另外,在关系SC中S#不仅是外键,也是主键的一部分,因此这里S# 值不允许空。,
13、设工厂数据库中有两个关系模式:DEPT(D#,DNAME)EMP(E#,ENAME,SALARY,D# ) 车间模式DEPT的属性为车间编号、车间名,职工模式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 | t
15、R tS,t是元组变量,R和S的元数相同。 差(Difference) 设关系R和S具有相同的关系模式,R和S的差是由属于R但不属于S的元组构成的集合,记为RS。形式定义如下: 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的元
16、数分别为r和s,定义R和S的一个(r+s)元的元组集合,每个元组的前r个分量来自R的一个元组,后s个分量来自S的一个元组,记为RS。 RS t|t=trRtsS,专门的关系运算,选择(Selection) 选择操作是根据某些条件对关系做水平分割,即选取符合条件的元组。条件可用命题公式(即计算机语言中的条件表达式)F表示。 F中的基本形式为:X1Y1: 其中表示比较运算符:,。 X1,Y1等是属性名,常量,或列序号。 关系R关于公式F的选择操作用F(R)表示,形式定义为:F(R) t | tR F(t)= true 为选择运算符,F(R)表示从R中挑选满足公式F为真的元组所构成的关系。 例如,2
17、3(R)表示从R中挑选第2个分量值大于3的 元组所构成的关系。书写时,为了与属性序号区别起见,常量用引号括起来,而属性序号或属性名不要用引号括起来。,投影(Projection),这个操作是对一个关系进行垂直分割,消去某些列,并重新安排列的顺序。设关系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的每列标上属性名,那么操
18、作符的下标处也可以用属性名表示。例如,关系R(A,B,C),那么C,A(R)与3,1(R)是等价的。,连接有两种:连接和F连接(这里是算术比较符,F是公式)。 连接 R St t= trR tsS 表达式 表示元组tr的第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的
19、公共属性是A1,AK,挑选RS中满足R.A1=S.A1,R.AK=S.AK的那些元组;去掉S.A1,S.AK这些列。 定义: 中i1,im为R和S的全部属性,但公共属性只出现一次。,自然连接(natural join),关系R,关系S,一般连接 R S,等值连接 R S,自然连接 R S,连接运算举例,两个关系R和S在做自然连接时,选择两个关系在公共属性上值相等的元组构成新的关系。此时,关系R中某些元组有可能在S中不存在公共属性上值相等的元组,从而造成R中这些元组在操作时被舍弃了,同样,S中某些元组也可能被舍弃。 如果把舍弃的元组也保存在结果关系中,而在其他属性上填空值(Null),那么这种连
20、接就叫做外连接(Outer join)。如果只把左边关系R中要舍弃的元组保留就叫做左外连接(Left outer join或Left join),如果只把右边关系S中要舍弃的元组保留就叫做右外连接(Right outer join或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)
21、S)-R),除法举例,关系代数运算的应用实例(1),在关系代数运算中,把由五个基本操作经过有限次复合的式子称为关系代数表达式。这种表达式的运算结果仍是一个关系。 例2.7 设教学数据库中有三个关系:学生关系 S(S#,SNAME,AGE,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#,S
22、NAME(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课的学生姓名与年龄。SNAME,AGE ( S)-SNAME,AGE (C#=C2 (S SC)(7) 检索学习全部课程的学生姓名。 学生选课情况可用操作S#,C#(SC); 全部课程可用操作C#(C)表示; 学了全部课程的学生学号可用除法操作表示,操作结果是学号S#集;S#,C# (SC) C# (C) 从S#求学生姓名SNAME,可以用自然连接和投影
23、操作组合而成:SNAME(S (S#,C# (SC) C# (C)(8)检索所学课程包含学生S3所学课程的学生学号。 学生选课情况可用操作S#,C# (SC)表示; 学生S3所学课程可用操作C#(S#=S3(SC)表示; 所学课程包含学生S3所学课程的学生学号,可以用除法操作求得:S#,C# (SC) C#(S#=S3(SC),S(S#,SNAME,AGE,SEX) SC(S#,C#,GRADE) C(C#,CNAME,TEACHER),关系代数运算的应用实例(2),关系代数运算的应用实例(3),一般地有下列规律: (1) 对于只涉及到选择、投影、连接的查询可用下列表达式表示: (RS) 或者
24、(R S) (2) 对于否定的操作,一般要用差操作表示,例如“检索不学C2课的学生姓名”。用下列表达式表示:SNAME(S)-SNAME(CNO=C2(S SC)但不能用下式表示: SNAME(CNOC2(S SC) 对于检索具有“全部”特征的操作,一般要用除法操作表示,例如“检索学习全部课程的学生学号”。用下列表达式表示: 要用SNO,CNO(SC)CNO(C)表示,而不能写成SNO (SCCNO(C)形式。这是因为一个学生学的课程的成绩可能是不一样的。,3.5 查询优化,主要内容,查询优化的一般策略 代数表达式的等价变换规则 优化算法,例 设关系R和S都是二元关系,属性名分别为A,B和C,
25、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的大部分时间是花在连接操作上的。,查询优化例子,可以分析出,在时空性能上,E3最优,其次是E2,最后是E1。此例还可以看出,如何安排选择、投影和连接的顺序是个很重要的问题。,查询优化的一般策略 (1),在关系代数表达式中需要指出若干关系的操作步骤。那么,系统应该以什么样的操作顺序,才能做
26、到既省时间,又省空间,而且效率也比较高呢?这个问题称为查询优化问题。 查询优化是实现关系系统的关键技术,它大大减轻了用户选择存取路径的负担,用户使用关系系统时,只要提出“做什么”,不必指出“怎么做”。 在关系代数运算中,笛卡儿积和连接运算是最费时间的。,查询优化的一般策略 (2),查询优化采用的一般策略是: 尽可能早地执行选择运算。在查询中这种变换最为重要,因为它可以以元组为单位减小中间结果,从而使执行时间成数量级地减少。 把先做笛卡儿积,后做选择结合起来。使之成为一个连接运算。连接运算(特别是等值连接)要比笛卡儿积运算效率高得很多。当对笛卡儿积RS的结果再做选择时,并且这个选择是对R和S的属
27、性进行比较,在这样的条件下,这个笛卡儿积和选择运算等价于一个连接。 一般对不含R的属性或不含S的属性的比较,可以移到笛卡儿积运算前去做,这样做比转换到连接更好。 同时计算一串选择和一串投影运算,以免分开运算造成多次扫描文件,从而节省了操作时间。 找出表达式里的公共子表达式。如果公共子表达式的结果不是很大,并且从外存读入比起计算它要节省许多时间,那么,预先计算一下这个公共子表达式是有好处的。 子表达式内涉及到连接,但又不能把限定条件向内移入的那类表达式,一般属于这一类。,连接和笛卡儿积的交换律 E1 E2E2 E1 E1 E2 E2 E1 E1E2 E1E2 连接和笛卡儿积的结合律 (E1 E2
28、) E3E1 (E2 E3)(E1 E2) E3E1 (E2 E3)(E1E2)E3 E1(E2E3) 投影的串接设L1,设L2,Ln为属性集,并且 ,那么下式也成立. 选择的串接,代数表达式的等价变换规则 (1),选择和投影操作的交换,代数表达式的等价变换规则 (2),选择对笛卡儿积的分配律,这里要求F只涉及到E1中的属性。 如果F形为F1F2,且F1只涉及到E1的属性,F2只涉及到E2的属性,则有,此外,如果F形为F1F2,且F1只涉及到E1的属性,F2只涉及到E1和E2的属性,则有:,选择对并的分配律E1和E2具有相同的属性名,或者E1和E2表达的关系的属性有对应性,则有:,代数表达式的
29、等价变换规则(3),选择对集合差的分配律E1和E2的属性有对应性,则有:,选择对自然联接的分配律F只涉及到表达式E1和E2的公共属性,则有:(E1 E2) (E1) (E2),投影对笛卡尔的分配律L1是E1中的属性集,L2是E2中的属性集,则有:,投影对并的分配律E1和E2的属性有对应性,则有:,代数表达式的等价变换规则 (4),选择与联接操作的结合,(E1,并和交的交换律E1E2E2E1E1E2E2E1,并和交的结合律(E1E2)E3E1(E2E3)(E1E2)E3E1(E2E3),优化算法 (1),代数优化是利用上面的等价变换规则,对关系表达式进行优化,以减少执行时的开销。虽然不能保证最优
30、,但在多数情况下能使表达式更好些。在关系代数表达式中,最花费时间和空间的运算是笛卡儿积和连接操作,为此,引出三条启发式规则,用于对表达式进行转换,以减少中间关系的大小。 优先应用单项的选择和投影; 优先应用一般选择和投影; 对笛卡儿积、并运算、差运算,若它们前面加有选择和投影,则先做选择和投影。,优化算法 (2),算法:关系代数表达式的优化。输入:一个关系代数表达式的语法树输出:计算表达式的一个优化序列方法: 把, 对每个选择,尽可能地将选择向树的叶端移动。, 对每个投影,尽可能地向树的叶端移动。说明:过程中可能使某些投影操作消失;也可能把一个投影分成两个,其中一个将 靠近叶端;也可能消去该投
31、影操作。, 把选择和投影合并成单个选择、单个投影或一个选择后跟一个投影。, 将上述步骤得到的语法树的内结点分组。,产生一个程序,上述每一组是这程序的一步,且先执行后代结点组。,优化算法(3),例3.14 对于如下关系数据库:S(S#,SNAME,AGE,SEX)SC(S#,C#,GRADE)C(C#,CNAME,TEACHER)现有一个查询语句:检索至少学习LIU老师所授一门课程的女生的学号和姓名。该查询语句的关系代数表达式如下:,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) 执行时从叶端以次向上进行,每组运算只对关系一次扫描。,优化的语法树及其分组,
copyright@ 2008-2019 麦多课文库(www.mydoc123.com)网站版权所有
备案/许可证编号:苏ICP备17064731号-1