第3章关系数据库的基本理论.ppt

第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 专门的关系运算 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表示属性集，用小写字母表示属性值。,数据库技术的术语 关系模型的术语,关系具有的特点, 关系（表）可以看成是由行和列交叉组成的二维表格。它表示的是一个实体集合。 表中一行称为一个元组，可用来表示实体集中的一个实体。 表中的列称为属性，给每一列起一个名称即属性名，表中的属性名不能相同。 列的取值范围称为域，同列具有相同的域，不同的列可有相同的域。 例如，SEX的取值范围是M（男），F（女），AGE为整数域。 表中任意两行（元组）不能相同。能惟一标识表中不同行的属性或属性组称为主键。,关系的性质,属性值是原子的，不可分解。 没有重复元组。 没有行序。 理论上没有列序，但一般使用时都有列序。,关键码和表之间的联系,超键：在一个关系中，能惟一标识元组的属性或属性集称为关系的超键。 候选键：如果一个属性集能惟一标识元组，且又不含有多余的属性，那么这个属性集称为关系的候选键。 主键：若一个关系中有多个候选键，则选其中的一个为关系的主键。 外键：若一个关系R中包含有另一个关系S的主键所对应的属性组F，则称F为R的外键。并称关系S为参照关系，关系R为依赖关系。,关系模式举例,例如，学生关系和系部关系分别为： 学生（SNO，SNAME，SEX，AGE，SDNO） 系部（SDNO，SDNAME，CHAIR） 学生关系的主键是SNO，系部关系的主键为SDNO，在学生关系中，SDNO是它的外键。 更确切地说，SDNO是系部表的主键，将它作为外键放在学生表中，实现两个表之间的联系。 在关系数据库中，表与表之间的联系就是通过公共属性实现的。 我们约定，在主键的属性下面加下划线，在外键的属性下面加波浪线。,关系模式、关系子模式和存储模式,例3.1 下图是一个教学模型的实体联系图。实体类型“学生”的属性SNO、SNAME、SEX、AGE、SDEPT分别表示学生的学号、姓名、性别、年龄和学生所在系部；实体类型“课程”的属性CNO、CNAME、CDEPT、TNAME分别表示课程号、课程名、课程所属系和任课教师。学生用S表示，课程用C表示。S和C之间有M:N的联系（一个学生可选多门课程，一门课程可以被多个学生选修），联系类型SC的属性成绩用GRADE表示。右图表示的实体联系图（ER图）。,关系模式是对关系的描述，它包括模式名，组成该关系的诸属性名、值域名和模式的集合。具体的关系称为实例。,关系模式,该图表示的学生情况的部分转换成相应的关系模式为： S(SNO,SNAME,SEX,AGE,SDPET)关系模式S描述了学生的数据结构，它是下表中学生实体的关系模式。其中SNO，CNO为关系SC的主键，SNO、CNO又分别为关系SC的两个外键。,学生关系实例如下表；选修关系实例如右表。,关系模式(9),课程关系实例如下表：,关系子模式,用户使用的数据不直接来自关系模式中的数据，而是从若干关系模式中抽取满足一定条件的数据构成关系子模式。关系子模式是用户所需数据结构的描述，其中包括这些数据来自哪些模式和应满足哪些条件。 例3.2 用户需要用到成绩子模式G(SNO,SNAME,CNO,GRADE)。子模式G对应的数据来源于表S和表SC，构造时应满足它们的SNO值相等。子模式G的构造过程如下图所示。,关系子模式,一 一对应,描述关系是如何在物理存储设备上存储的。关系存储时的基本组织方式是文件。由于关系模式有键，因此存储一个关系可以用散列方法或索引方法实现。如果关系中元组数目较少（100以内），那么也可以用堆文件方式实现。此外，还可以对任意的属性集建立辅助索引。,存储模式,关系模型中常用的关系操作包括查询（Query）操作和插入（Insert）、删除（Delete）、修改（Update）操作。 查询操作又可以分为：选择（Select）、投影（Project）、连接（Join）、除（Divide）、并（Union）、差（Except）、交（Intersection）、笛卡尔积等。 基本操作：选择、投影、并、差、笛卡尔积。 其他操作：可以用基本操作来定义和导出的。 关系操作的特点是集合操作方式，即操作的对象和结果都是集合。这种操作方式也称称为一次一集合（set-at-a-time）的方式。相应地，非关系数据模型的数据操作方式则为一次一纪录（record-at-a-time）的方式。,3.1.2 关系操作,关系语言是一种高度非过程化的语言，用户不必请求DBA为其建立特殊的存取路径，存取路径的选择由RDBMS的优化机制来完成。,关系数据语言的分类,关系数据语言分为三类：关系代数、元组关系演算和域关系演算。该三种语言在表达能力上是完全等价的。,3.2 关系模型的完整性规则,主要内容,3.2.1 关系的三类完整性约束 3.2.2 实体完整性 3.2.3 参照完整性 3.2.4 用户定义完整性,关系模型的完整性规则,关系模型中有三类完整性约束：实体完整性、参照完整性和用户定义的完整性。 实体完整性和参照完整性是关系模型必须满足的完整性约束条件，被称作是关系的两个不变性，应该由关系系统自动支持。 用户定义的完整性是应用领域需要遵循的约束条件，体现了具体领域中的语义约束。,规则3.1 实体完整性（Entity Integrity）规则：若属性（指一个或一组属性）A是基本关系R的主属性。则A不能取空值。 例如: 在关系S(SNO,SNAME,SEX,AGE,SDPET)中，SNO这个属性为主码，则SNO不能取空值。,3.2.1 关系的三类完整性约束,实体完整性要求关系中元组在组成主键的属性上不能有空值。如果出现空值，那么主键值就起不了惟一标织元组的作用。,对于实体完整性规则几点说明, 实体完整性规则是针对基本关系而言的。一个基本关系通常对应现实世界的一个实体集。例如学生关系对应于学生的集合。 现实世界中的实体是可区分的，即它们具有某种唯一性标识。例如每个学生都是独立的个体，是不一样的。 关系模型中以主码作为唯一性标识。 主码中的属性即主属性不能取空值。如果主属性取空值，就说明存在某个不可标识的实体，即存在不可区分的实体，这与第点相矛盾，因此这个规则称为实体完整性。,定义2.3 参照完整性规则的形式定义如下： 如果属性集K是关系模式R1的主键，K也是关系模式R2的外键，那么在R2的关系中，K的取值只允许两种可能，或者为空值，或者等于R1关系中某个主键值。 这条规则的实质是“不允许引用不存在的实体”。 在上述形式定义中，关系模式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# 值不允许空。, 设工厂数据库中有两个关系模式： DEPT(D#，DNAME) EMP(E#，ENAME，SALARY，D# ) 车间模式DEPT的属性为车间编号、车间名，职工模式EMP的属性为工号、姓名、工资、所在车间的编号。每个模式的主键与外键已标出。在EMP中，由于D#不在主键中，因此D# 值允许空。,参照完整性规则举例,参照完整性规则举例, 设课程之间有先修、后继联系。模式如下： R(C# ，CNAME，PC# ) 其属性表示课程号、课程名、先修课的课程号。如果规定，每门课程的直接先修课只有一门，那么模式R的主键是C#，外键是PC#.。这里参照完整性在一个模式中实现。即每门课程的直接先修课必须在关系中出现。,用户定义的完整性规则,在建立关系模式时，对属性定义了数据类型，即使这样可能还满足不了用户的需求。此时，用户可以针对具体的数据约束，设置完整性规则，由系统来检验实施，以使用统一的方法处理它们，不再由应用程序承担这项工作。例如学生的年龄定义为两位整数，范围还太大，我们可以写如下规则把年龄限制在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。形式定义如下： 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个元组，则R×S有m×n个元组。,笛卡儿积(Cartesian Product) 设关系R和S的元数分别为r和s,定义R和S的一个(r+s)元的元组集合，每个元组的前r个分量来自R的一个元组，后s个分量来自S的一个元组，记为R×S。 R×S t|t=trRtsS,专门的关系运算,选择（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),这个操作是对一个关系进行垂直分割，消去某些列，并重新安排列的顺序。 设关系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 表达式 表示元组tr的第i个分量、元组ts的第j个分量满足操作。 F连接 F连接是从关系R和S的笛卡儿积中选取属性间满足某一公式F的元组, 这里F是形为F1F2Fn的公式，每个FP是形ij的式子，而i和j分别为关系R和S的第i、第j个分量的序号。,连接（join）运算,ij,例 连接和F连接的例子.,24（R×S),连接运算举例,两个关系R和S的自然连接 操作具体计算过程如下： 计算R×S ； 设R和S的公共属性是A1,AK，挑选R×S中满足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），那么这种连接就叫做外连接(Outer join)。如果只把左边关系R中要舍弃的元组保留就叫做左外连接（Left outer join或Left join），如果只把右边关系S中要舍弃的元组保留就叫做右外连接（Right outer join或Right join）。,专门的关系运算,关系R 关系S,外连接,左外连接,右外连接,外连接的例子,除法（division）,设关系R和S的元数分别为r和s（设rs0），那么R÷S是一个（r-s）元的元组的集合。（R÷S）是满足下列条件的最大关系：其中每个元组t与S中每个元组u组成的新元组必在关系R中。 R÷S1,2,r-s（R）- 1,2,r-s (1,2,r-s(R)×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#,SNAME(CNAME=MATHS (S SC C),(4) 检索选修课程号为C2或C4的学生学号。 S#(C#=C2 C#=C4(SC) (5) 检索至少选修课程号为C2和C4的学生学号。 1(1=42=C2 5=C4 (SC×SC) (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,可以用自然连接和投影操作组合而成: 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) 对于只涉及到选择、投影、连接的查询可用下列表达式表示： (R×S) 或者(R S) (2) 对于否定的操作，一般要用差操作表示，例如“检索不学C2课的学生姓名”。用下列表达式表示： SNAME(S)-SNAME(CNO='C2'(S SC)但不能用下式表示： SNAME(CNO'C2'(S SC) 对于检索具有“全部”特征的操作，一般要用除法操作表示，例如“检索学习全部课程的学生学号”。用下列表达式表示： 要用SNO,CNO(SC)÷CNO(C)表示，而不能写成 SNO (SC÷CNO(C)形式。 这是因为一个学生学的课程的成绩可能是不一样的。,3.5 查询优化,主要内容,查询优化的一般策略 代数表达式的等价变换规则 优化算法,例 设关系R和S都是二元关系，属性名分别为A，B和C，D。 设有一个查询可用关系代数表达式表示： E1=A（B=CD=99（R×S） 也可以把选择条件D=99移到笛卡儿积中的关系S前面： E2=A（B=C（R×D=99（S） 还可以把选择条件BC与笛卡儿积结合成等值连接形式： E3=A（R D='99'（S） 这三个关系代数表达式是等价的，但执行的效率大不一样。显然，求El，E2，E3的大部分时间是花在连接操作上的。,查询优化例子,可以分析出，在时空性能上，E3最优，其次是E2，最后是E1。此例还可以看出，如何安排选择、投影和连接的顺序是个很重要的问题。,查询优化的一般策略 (1),在关系代数表达式中需要指出若干关系的操作步骤。那么，系统应该以什么样的操作顺序，才能做到既省时间，又省空间，而且效率也比较高呢？这个问题称为查询优化问题。 查询优化是实现关系系统的关键技术,它大大减轻了用户选择存取路径的负担,用户使用关系系统时,只要提出“做什么”,不必指出“怎么做”。 在关系代数运算中，笛卡儿积和连接运算是最费时间的。,查询优化的一般策略 (2),查询优化采用的一般策略是： 尽可能早地执行选择运算。在查询中这种变换最为重要，因为它可以以元组为单位减小中间结果，从而使执行时间成数量级地减少。 把先做笛卡儿积，后做选择结合起来。使之成为一个连接运算。连接运算（特别是等值连接）要比笛卡儿积运算效率高得很多。当对笛卡儿积R×S的结果再做选择时，并且这个选择是对R和S的属性进行比较，在这样的条件下，这个笛卡儿积和选择运算等价于一个连接。 一般对不含R的属性或不含S的属性的比较，可以移到笛卡儿积运算前去做，这样做比转换到连接更好。 同时计算一串选择和一串投影运算，以免分开运算造成多次扫描文件，从而节省了操作时间。 找出表达式里的公共子表达式。如果公共子表达式的结果不是很大，并且从外存读入比起计算它要节省许多时间，那么，预先计算一下这个公共子表达式是有好处的。 子表达式内涉及到连接，但又不能把限定条件向内移入的那类表达式，一般属于这一类。,连接和笛卡儿积的交换律 E1 E2E2 E1 E1 E2 E2 E1 E1×E2 E1×E2 连接和笛卡儿积的结合律 (E1 E2） E3E1 (E2 E3) (E1 E2) E3E1 (E2 E3) (E1×E2)×E3 E1×(E2×E3) 投影的串接 设L1,设L2,Ln为属性集，并且 ,那么下式也成立. 选择的串接,代数表达式的等价变换规则 (1),选择和投影操作的交换,代数表达式的等价变换规则 (2),选择对笛卡儿积的分配律,这里要求F只涉及到E1中的属性。 如果F形为F1F2，且F1只涉及到E1的属性，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,并和交的交换律 E1E2E2E1 E1E2E2E1,并和交的结合律 （E1E2）E3E1（E2E3） （E1E2）E3E1（E2E3）,优化算法 (1),代数优化是利用上面的等价变换规则，对关系表达式进行优化，以减少执行时的开销。虽然不能保证最优，但在多数情况下能使表达式更好些。在关系代数表达式中，最花费时间和空间的运算是笛卡儿积和连接操作，为此，引出三条启发式规则，用于对表达式进行转换，以减少中间关系的大小。 优先应用单项的选择和投影； 优先应用一般选择和投影； 对笛卡儿积、并运算、差运算，若它们前面加有选择和投影，则先做选择和投影。,优化算法 (2),算法：关系代数表达式的优化。 输入：一个关系代数表达式的语法树 输出：计算表达式的一个优化序列 方法： 把, 对每个选择，尽可能地将选择向树的叶端移动。, 对每个投影，尽可能地向树的叶端移动。 说明：过程中可能使某些投影操作消失；也可能把一个投影分成两个，其中一个将 靠近叶端；也可能消去该投影操作。, 把选择和投影合并成单个选择、单个投影或一个选择后跟一个投影。, 将上述步骤得到的语法树的内结点分组。,产生一个程序，上述每一组是这程序的一步，且先执行后代结点组。,优化算法(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) 执行时从叶端以次向上进行，每组运算只对关系一次扫描。,优化的语法树及其分组,