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

2019/4/22,1,第3章 关系数据库的基本理论,主要内容 关系数据模型 关系模型的完整性规则 关系代数的基本运算 查询优化,2019/4/22,2,本章重要概念,(1) 基本概念 关系数据模型，关键码（主键和外键），关系的定义和性质，三类完整性规则，ER模型到关系模型的转换规则，过程性语言与非过程性语言。 (2 ) 关系代数 五个基本操作，四个组合操作，七个扩充操作。,(3) 关系代数表达式的优化 关系代数表达式的等价及等价转换规则，启化式优化算法。,2019/4/22,3,本章概要,本章先介绍关系模型的基本概念；然后主要介绍关系运算的三种理论之一：关系代数。,2019/4/22,4,3.1 关系数据模型,主要内容 关系模式 关系操作,2019/4/22,5,关系模式(1),每个关系都有一个模式，称为关系模式(Relation Schema)，由一个关系名及它的所有属性名构成。在关系模式中，字段称为属性，字段值称为属性值，记录类型称为关系模式。在图3.1中，关系模式名是R。记录称为元组（tuple），元组的集合称为关系（relation）或实例（instance）。一般用前面的大写英语字母A、B、C、表示单个属性，用后面的大写字母、W、X、Y、Z表示属性集，用小写字母表示属性值。 关系R,2019/4/22,6,关系模式(2),关系具有的特点： 关系（表）可以看成是由行和列交叉组成的二维表格。它表示的是一个实体集合。 表中一行称为一个元组，可用来表示实体集中的一个实体。 表中的列称为属性，给每一列起一个名称即属性名，表中的属性名不能相同。 列的取值范围称为域，同列具有相同的域，不同的列可有相同的域。例如，SEX的取值范围是M（男），F（女），AGE为整数域。 表中任意两行（元组）不能相同。能惟一标识表中不同行的属性或属性组称为主键。,2019/4/22,7,关系模式(3),关系是一种规范化了的二维表格，具有如下性质： 属性值是原子的，不可分解。 没有重复元组。 没有行序。 理论上没有列序，但一般使用时都有列序。,关键码和表之间的联系 超键：在一个关系中，能惟一标识元组的属性或属性集称为关系的超键。 候选键：如果一个属性集能惟一标识元组，且又不含有多余的属性，那么这个属性集称为关系的候选键。 主键：若一个关系中有多个候选键，则选其中的一个为关系的主键。 外键：若一个关系R中包含有另一个关系S的主键所对应的属性组F，则称F为R的外键。并称关系S为参照关系，关系R为依赖关系。,2019/4/22,8,关系模式(4),例如，学生关系和系部关系分别为： 学生（SNO，SNAME，SEX，AGE，SDNO） 系部（SDNO，SDNAME，CHAIR） 学生关系的主键是SNO，系部关系的主键为SDNO，在学生关系中，SDNO是它的外键。更确切地说，SDNO是系部表的主键，将它作为外键放在学生表中，实现两个表之间的联系。在关系数据库中，表与表之间的联系就是通过公共属性实现的。我们约定，在主键的属性下面加下划线，在外键的属性下面加波浪线。,2019/4/22,9,关系模式(5),关系模式是对关系的描述，它包括模式名，组成该关系的诸属性名、值域名和模式的主键。,例3.1 下图是一个教学模型的实体联系图。实体类型“学生”的属性SNO、SNAME、SEX、AGE、SDEPT分别表示学生的学号、姓名、性别、年龄和学生所在系部；实体类型“课程”的属性CNO、CNAME、CDEPT、TNAME分别表示课程号、课程名、课程所属系和任课教师。学生用S表示，课程用C表示。S和C之间有M:N的联系（一个学生可选多门课程，一门课程可以被多个学生选修），联系类型SC的属性成绩用GRADE表示。右图表示的实体联系图（ER图）。,2019/4/22,10,关系模式(6),该图表示的学生情况的部分转换成相应的关系模式为： S(SNO,SNAME,SEX,AGE,SDPET)关系模式S描述了学生的数据结构，它是下表中学生实体的关系模式。其中SNO，CNO为关系SC的主键，SNO、CNO又分别为关系SC的两个外键。,学生关系实例如下表；选修关系实例如右表。,2019/4/22,11,关系模式(7),课程关系实例如下表：,关系子模式 用户使用的数据不直接来自关系模式中的数据，而是从若干关系模式中抽取满足一定条件的数据构成关系子模式。关系子模式是用户所需数据结构的描述，其中包括这些数据来自哪些模式和应满足哪些条件。 例3.2 用户需要用到成绩子模式G(SNO,SNAME,CNO,GRADE)。子模式G对应的数据来源于表S和表SC，构造时应满足它们的SNO值相等。子模式G的构造过程如下图所示。,2019/4/22,12,关系模式(7),一 一对应,2019/4/22,13,关系模式(8),存储模式 描述关系是如何在物理存储设备上存储的。关系存储时的基本组织方式是文件。由于关系模式有键，因此存储一个关系可以用散列方法或索引方法实现。如果关系中元组数目较少（100以内），那么也可以用堆文件方式实现。此外，还可以对任意的属性集建立辅助索引。,2019/4/22,14,关系操作(1),基本的关系操作 关系模型中常用的关系操作包括查询（Query）操作和插入（Insert）、删除（Delete）、修改（Update）操作。 查询操作又可以分为：选择（Select）、投影（Project）、连接（Join）、除（Divide）、并（Union）、差（Except）、交（Intersection）、笛卡尔积等。其中选择、投影、并、差、笛卡尔积是5种基本操作。 其他操作是可以用基本操作来定义和导出的。就像乘法可以用加法来定义和导出一样。 关系操作的特点是集合操作方式，即操作的对象和结果都是集合。这种操作方式也称称为一次一集合（set-at-a-time）的方式。相应地，非关系数据模型的数据操作方式则为一次一纪录（record-at-a-time）的方式。,2019/4/22,15,关系操作(2),关系数据语言可以分为三类 ：关系代数、元组关系演算和域关系演算。该三种语言在表达能力上是完全等价的。,关系语言是一种高度非过程化的语言，用户不必请求DBA为其建立特殊的存取路径，存取路径的选择由RDBMS的优化机制来完成。,2019/4/22,16,3.2 关系模型的完整性规则,主要内容 关系的三类完整性约束 实体完整性 参照完整性 用户定义完整性,2019/4/22,17,三类完整性约束(1),关系模型中有三类完整性约束：实体完整性、参照完整性和用户定义的完整性。其中实体完整性和参照完整性是关系模型必须满足的完整性约束条件，被称作是关系的两个不变性，应该由关系系统自动支持。用户定义的完整性是应用领域需要遵循的约束条件，体现了具体领域中的语义约束。,规则3.1 实体完整性（Entity Integrity）规则：若属性（指一个或一组属性）A是基本关系R的主属性。则A不能取空值。 例如，在关系S(SNO,SNAME,SEX,AGE,SDPET)中，SNO这个属性为主码，则SNO不能取空值。,实体完整性要求关系中元组在组成主键的属性上不能有空值。如果出现空值，那么主键值就起不了惟一标织元组的作用。,2019/4/22,18,三类完整性约束(2),对于实体完整性规则说明如下几点： 实体完整性规则是针对基本关系而言的。一个基本关系通常对应现实世界的一个实体集。例如学生关系对应于学生的集合。 现实世界中的实体是可区分的，即它们具有某种唯一性标识。例如每个学生都是独立的个体，是不一样的。 关系模型中以主码作为唯一性标识。 主码中的属性即主属性不能取空值。如果主属性取空值，就说明存在某个不可标识的实体，即存在不可区分的实体，这与第点相矛盾，因此这个规则称为实体完整性。,2019/4/22,19,三类完整性约束(3),参照完整性规则（reference integrity rule） 定义2.3 参照完整性规则的形式定义如下： 如果属性集K是关系模式R1的主键，K也是关系模式R2的外键，那么在R2的关系中，K的取值只允许两种可能，或者为空值，或者等于R1关系中某个主键值。 这条规则的实质是“不允许引用不存在的实体”。 在上述形式定义中，关系模式R1的关系称为“参照关系”，关系模式R2的关系称为“依赖关系”。,由参照完整性建立了多表之间的对应关系,2019/4/22,20,三类完整性约束(4),例2.1 下面各种情况说明了参照完整性规则在关系中如何实现的。 在关系数据库中有下列两个关系模式： S（S#，SNAME，AGE，SEX） SC（S#，C#，GRADE） 这里带下划线者为主键，带红虚线者为外键。据规则要求，关系SC中的S# 值应该在关系S中出现。如果关系SC中有一个元组（S7,C4,80），而学号S7却在关系S中找不到，那么我们就认为在关系SC中引用了一个不存在的学生实体，这就违反了参照完整性规则。 另外，在关系SC中S#不仅是外键，也是主键的一部分，因此这里S# 值不允许空。,2019/4/22,21,三类完整性约束(5), 设工厂数据库中有两个关系模式： DEPT(D#，DNAME) EMP(E#，ENAME，SALARY，D# ) 车间模式DEPT的属性为车间编号、车间名，职工模式EMP的属性为工号、姓名、工资、所在车间的编号。每个模式的主键与外键已标出。在EMP中，由于D#不在主键中，因此D# 值允许空。, 设课程之间有先修、后继联系。模式如下： R(C# ，CNAME，PC# ),2019/4/22,22,三类完整性约束(6),其属性表示课程号、课程名、先修课的课程号。如果规定，每门课程的直接先修课只有一门，那么模式R的主键是C#，外键是PC#.。这里参照完整性在一个模式中实现。即每门课程的直接先修课必须在关系中出现。 用户定义的完整性规则 在建立关系模式时，对属性定义了数据类型，即使这样可能还满足不了用户的需求。此时，用户可以针对具体的数据约束，设置完整性规则，由系统来检验实施，以使用统一的方法处理它们，不再由应用程序承担这项工作。例如学生的年龄定义为两位整数，范围还太大，我们可以写如下规则把年龄限制在1530岁之间： CHECK（AGE BETWEEN 15 AND 30）,2019/4/22,23,3.3 关系代数的基本运算,主要内容 传统的集合运算 专门的关系运算 关系代数表达式及其应用实例,2019/4/22,24,传统的集合运算(1),并（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的元数相同。,例子,2019/4/22,25,传统的集合运算(2),交（intersection） 关系R和S的交是由属于R又属于S的元组构成的集合，记为 RS，这里要求R和S定义在相同的关系模式上。形式定义如 下： RSttR tS，R和S的元数相同。 由于RS = R-(R-S)，或RS = S-(S-R)，因此交操作不是一个独立的操作。,例,R,S,R S,2019/4/22,26,传统的集合运算(3),笛卡儿积(Cartesian Product) 设关系R和S的元数分别为r和s,定义R和S的一个(r+s)元的元 组集合，每个元组的前r个分量来自R的一个元组，后s个分量来自S的一个元组，记为RS。 RS t|t=trRtsS,若R有m个元组，S有n个元组，则RS有mn个元组。,2019/4/22,27,专门的关系运算 (1),选择（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的 元组所构成的关系。书写时，为了与属性序号区别起见，常量 用引号括起来，而属性序号或属性名不要用引号括起来。,2019/4/22,28,专门的关系运算 (2),投影（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）是等价的。,2019/4/22,29,专门的关系运算 (3),连接（join） 连接有两种：连接和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个分量的序号。,ij,2019/4/22,30,例 连接和F连接的例子.,24（RS),专门的关系运算 (4),2019/4/22,31,自然连接（natural join） 两个关系R和S的自然连接 操作具体计算过程如下： 计算RS ； 设R和S的公共属性是A1,AK，挑选RS中满足R.A1=S.A1，R.AK=S.AK 的那些元组； 去掉S.A1，S.AK这些列。 定义： 其中i1,im为R和S的全部属性，但公共属性只出现一次。,专门的关系运算 (5),2019/4/22,32,专门的关系运算 (6),关系R,关系S,一般连接 R S,等值连接 R S,自然连接 R S,连接运算举例,2019/4/22,33,两个关系R和S在做自然连接时，选择两个关系在公共属性上值相等的元组构成新的关系。此时，关系R中某些元组有可能在S中不存在公共属性上值相等的元组，从而造成R中这些元组在操作时被舍弃了，同样，S中某些元组也可能被舍弃。 如果把舍弃的元组也保存在结果关系中，而在其他属性上填空值（Null），那么这种连接就叫做外连接(Outer join)。如果只把左边关系R中要舍弃的元组保留就叫做左外连接（Left outer join或Left join），如果只把右边关系S中要舍弃的元组保留就叫做右外连接（Right outer join或Right join）。,专门的关系运算 (7),2019/4/22,34,专门的关系运算 (8),外连接的例子:,关系R 关系S,外连接,左外连接,右外连接,2019/4/22,35,除法（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),专门的关系运算 (9),2019/4/22,36,例 关系做除法的例子。,专门的关系运算 (10),2019/4/22,37,关系代数运算的应用实例(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),2019/4/22,38,(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,可以用自然连接和投影操作组合而成: 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),2019/4/22,39,关系代数运算的应用实例(3),一般地有下列规律： (1) 对于只涉及到选择、投影、连接的查询可用下列表达式表示： (RS) 或者(R S) (2) 对于否定的操作，一般要用差操作表示，例如“检索不学C2课的学生姓名”。用下列表达式表示： SNAME(S)-SNAME(CNO=C2(S SC)但不能用下式表示： SNAME(CNOC2(S SC) 对于检索具有“全部”特征的操作，一般要用除法操作表示，例如“检索学习全部课程的学生学号”。用下列表达式表示： 要用SNO,CNO(SC)CNO(C)表示，而不能写成 SNO (SCCNO(C)形式。 这是因为一个学生学的课程的成绩可能是不一样的。,2019/4/22,40,3.5 查询优化,主要内容 查询优化的一般策略 代数表达式的等价变换规则 优化算法,2019/4/22,41,查询优化例子,例 设关系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的大部分时间是花在连接操作上的。,可以分析出，在时空性能上，E3最优，其次是E2，最后是E1。此例还可以看出，如何安排选择、投影和连接的顺序是个很重要的问题。,2019/4/22,42,查询优化的一般策略 (1),在关系代数表达式中需要指出若干关系的操作步骤。那么，系统应该以什么样的操作顺序，才能做到既省时间，又省空间，而且效率也比较高呢？这个问题称为查询优化问题。 查询优化是实现关系系统的关键技术,它大大减轻了用户选择存取路径的负担,用户使用关系系统时,只要提出“做什么”,不必指出“怎么做”。 在关系代数运算中，笛卡儿积和连接运算是最费时间的。,2019/4/22,43,查询优化的一般策略 (2),查询优化采用的一般策略是： 尽可能早地执行选择运算。在查询中这种变换最为重要，因为它可以以元组为单位减小中间结果，从而使执行时间成数量级地减少。 把先做笛卡儿积，后做选择结合起来。使之成为一个连接运算。连接运算（特别是等值连接）要比笛卡儿积运算效率高得很多。当对笛卡儿积RS的结果再做选择时，并且这个选择是对R和S的属性进行比较，在这样的条件下，这个笛卡儿积和选择运算等价于一个连接。 一般对不含R的属性或不含S的属性的比较，可以移到笛卡儿积运算前去做，这样做比转换到连接更好。 同时计算一串选择和一串投影运算，以免分开运算造成多次扫描文件，从而节省了操作时间。 找出表达式里的公共子表达式。如果公共子表达式的结果不是很大，并且从外存读入比起计算它要节省许多时间，那么，预先计算一下这个公共子表达式是有好处的。 子表达式内涉及到连接，但又不能把限定条件向内移入的那类表达式，一般属于这一类。,2019/4/22,44,代数表达式的等价变换规则 (1),连接和笛卡儿积的交换律 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为属性集，并且 ,那么下式也成立. 选择的串接,2019/4/22,45,选择和投影操作的交换,代数表达式的等价变换规则 (2),选择对笛卡儿积的分配律,这里要求F只涉及到E1中的属性。 如果F形为F1F2，且F1只涉及到E1的属性，F2只涉及到E2的属性，则有,此外，如果F形为F1F2，且F1只涉及到E1的属性，F2只涉及到E1和E2的属性，则有：,2019/4/22,46,选择对并的分配律 E1和E2具有相同的属性名，或者E1和E2表达的关系的属性有对应性，则有：,代数表达式的等价变换规则(3),选择对集合差的分配律 E1和E2的属性有对应性，则有：,选择对自然联接的分配律 F只涉及到表达式E1和E2的公共属性，则有： （E1 E2） （E1） （E2）,投影对笛卡尔的分配律 L1是E1中的属性集，L2是E2中的属性集，则有：,投影对并的分配律 E1和E2的属性有对应性，则有：,2019/4/22,47,代数