理论课数据库chapter02

1、2.1 关系数据库的基本概念,2.2 关系模型及其描述,2.3 关系代数,2.4 关系演算,第二章 关系数据库,1,2.5 关系数据库查询优化,上一章回顾,什么是数据库？ 按一定结构组织，并长期存储在计算机内、可共享的大量数据的有机集合 常用的数据库管理系统有哪些？ Oracle、SQL Server、MySQL等 导师与研究生是什么对应关系？ 1：n,2,上一章回顾,E-R模型的四个组成部分？,3,实体名,属性名,矩形框表示实体型,椭圆形表示属性,菱形表示联系,连接实体型与联系类型，也可用于表示实体与属性的联系 并注明种类；对构成码的属性，在属性名下画一横线表示。,上一章回顾,三种基本数据模

2、型是？ 层次模型、网状模型、关系模型 关系模型采用什么结构表示实体及实体间联系？ 表结构 DBMS的三级模式与两级映象？ 外模式、模式、内模式 外模式/模式映象、模式/内模式映象,4,5,上一章回顾,模式、外模式、内模式分别是什么的描述？ 模式：数据库中全体数据的逻辑结构和特征的描述 外模式：数据库用户使用的局部数据的逻辑结构和特征的描述 内模式：数据物理结构和存储方式的描述 DBMS系统怎样确保了数据独立性？ 外模式/模式映象：实现数据逻辑独立性 模式/内模式映象：实现数据物理独立性,6,2.1基本概念,关系数据库之父 E.F.Codd（埃德加.科德）英国人，1923 在牛津的埃克塞特学院研

3、习数学与化学 作为英国皇家空军的飞行员参加了二战 1948年加入了IBM公司，成为数学程序员 1953年，出于对参议员约瑟夫麦卡锡的不满, 他迁往加拿大渥太华居住了十年 之后回到密歇根大学并取得了计算机科学博士学位 1981年, 科德因在关系型数据库方面的贡献获得了图灵奖 2003年4月18日, 科德因心脏病在佛罗里达威廉姆斯岛的家中去世, 享年79岁,7,1、关系及其性质 （1）域 定义2.1: 域是一组具有相同数据类型的值的集合。,在关系中用域来表示属性的取值范围 域中所包含的值的个数称域的基数(用m表示),例：D1=A , 2 , 3 , , Q , K M1= 13 D2=数据库原理，

4、面向对象数据库技术 M2= 2,2.1 关系数据库的基本概念,8,（2）笛卡尔积 定义2.2: 给定一组域 D1，Dn (可有相同的域)。 其笛卡尔积为： D1D2Dn=(d1，d2，dn) | diDi，i=1,2,n,n元组,di为分量,笛卡儿积也是一个集合,其中每一个元素(d1，d2，dn)叫作一个n元组(n-Tuple), 或简称为元组。元素中的每一个值di叫作一个分量（Component）。,若Di（i1，2，n）为有限集，其基数（Cardinal number）为mi（i1，2，n），则D1D2Dn的基数为：,2.1 关系数据库的基本概念,9,定义2.3 D1D2Dn的有意义的子集

5、称为在域D1，D2,Dn上的关系， 记为 R(D1,D2,Dn) 。,其中：R为关系的名；n为关系的度（目）；rR 表示 r 是 R 中的元组。,子集元素是关系中的元组； 关系中的元组个数是关系的基数; 同样可以把关系看作是一个二维表：,每一行对应一个元组； 表的每一列对应一个域，每个域起一个名字称为属性;,（3）关系,2.1 关系数据库的基本概念,10,例,例：设 D1=男人集合(MAN) = 王强、李东、张兵 D2 =女人集合(WOMAN) = 赵红、吴芳 D3=儿童集合(CHILD) = 王一、李一、李二 （1）求上面三个集合的笛卡儿积 （2）构造一个家庭关系，可表示为： FAMILY（

6、MAN，WOMAN，CHILD）,2.1 关系数据库的基本概念,11,（4）关系中常用术语 候选码 主码 外码 全码,2.1 关系数据库的基本概念,12,S(Sno, Cardno, Dno, Sname, Sage, ) D(Dno, Dname, Location),主码,主码,外码,PUR(Cno，Pno，Sno),全码,参照关系,被参照关系,2.1 关系数据库的基本概念,13,（5）关系的性质 每列的值为同一类型。 每列具有不同的属性名(可同域) 任意两元组不能完全相同。 行的次序可以互换。 列的次序可以互换。 分量值是原子的。,+5,学号 姓名 年龄,、网虫,不允许,元组,分量值,属

7、性名,关系的类型 ： 基本关系（基表） 查询表 视图表,2.1 关系数据库的基本概念,14,2、关系模式与关系数据库 定义2.4： 关系的描述称关系模式，其表示为：R(U，D，Dom，F),关系模式可简记为关系的属性名表。 R(U)=R(A1 ，A2，A3，.An) 例：学生（学号，姓名，总成绩）,域名集,属性名集,属性间的依赖关系集,属性向域的映像集,关系模式就是关系的框架（表框架） 它是对关系结构的描述,2.1 关系数据库的基本概念,15,在关系模型中，实体以及实体间的联系都是用关系来表示。在一个给定的现实世界领域中，相应于所有实体及实体之间的联系的关系的集合构成一个关系数据库。 关系数据

8、库也有型和值之分。关系数据库的型也称为关系数据库模式，是对关系数据库的描述，是关系模式的集合。关系数据库的值也称为关系数据库，是关系的集合。关系数据库模式与关系数据库通常统称为关系数据库。,关系数据库,2.1 关系数据库的基本概念,16,术语间的联系,一个关系只能对应一个关系模式 一个关系模式可对应多个关系 关系模式是关系的型，按其型装入数据值后即形成关系 关系模式是相对静态的、稳定的，而关系是动态的、随时间变化的 一个具体的关系数据库是若干相关关系的集合,17,1.关系模型的特点及组成 关系模型的特点： 结构简单，表达力强 语言的一体化 非过程化的操作 坚实的数学基础 操作效率较低 关系模型

9、的组成： 关系数据结构 关系数据操作 关系完整性约束,2. 关系模型的数据操作 (1)数据查询 (2)数据插入 (3)数据删除 (4)数据修改,2.2 关系模型及其描述,18,3. 关系的完整性 三类完整性约束： 实体完整性 参照完整性 用户定义的完整性,说明： 实体完整性规则是对基本关系的约束和限定。 实体具有唯一性标识主码。 主码属性不能取空值。,(1) 实体完整性 规则2.1 实体完整性规则 : 若属性A是基本关系R的主码属性，则属性A不能取空值。,不变性 由关系系统自动支持,2.2 关系模型及其描述,是应用领域需要遵循的约束条件,19,(2) 参照完整性 引用关系： 关系中的某属性的值

10、需要参照另一关系的属性来取值。 例1：学生(学号，姓名，性别，专业号，年龄) 专业(专业号，专业名),例2: 学生(学号，姓名，性别，专业号，年龄，班长),引用,引用,2.2 关系模型及其描述,20,定义2.5 ： 设：基本关系R、S(可为同一关系)。 若F是R的一个(组)属性，但不是R的码。 如果F与S的主码 K相对应，则称F是R的外码。 并称R为参照关系，S为被参照关系（目标关系）。 说明：S的主码K和R的外码F必须定义在同一个(或一组)域上。,例1：学生(学号，姓名，性别，专业号，年龄) 专业(专业号，专业名),被参照关系,参照关系,外码,参照完整性规则定义了外码与主码之间的引用规则。,

11、2.2 关系模型及其描述,21,规则2.2 参照完整性规则 若属性(组) F是R的外码且它与S的主码K相对应，则对于R中每个元组在F上的值必须为： 或者取空值(F的每个属性值均为空值)； 或者等于S中某个元组的主码值。 例1：学生(学号，姓名，性别，专业号，年龄) 关系中每个元组的专业号取值： 空值(未给该学生分配专业)； 非空值(是专业关系中某个元组的专业号值)。,2.2 关系模型及其描述,22,例2：职工EMP(EMP#,ENAME,JOB,DEPT#) 部门DEPT(DEPT#,DNAME,LOC) 则：EMP中的DEPT#为空或为DEPT中的DEPT#的值,(3) 用户定义的完整性,用

12、户自定义完整性是针对某一具体数据的约束条件，反映某一具体应用所涉及的数据必须满足的语义要求，由应用环境决定。,例： 属性的取值范围 属性的非空限制,2.2 关系模型及其描述,23,关系数据语言的分类 （1）关系代数语言 用对关系的运算来表达查询要求方式的语言。 （2）关系演算语言 用谓词来表达查询要求方式的语言。 元组关系演算语言 域关系演算语言 （3）结构化查询语言 （SQL) 具有关系代数和关系演算双重特点的语言,2.3 关系代数,24,关系查询语言,关系代数语言：查询操作是以集合操作作为基础的语言 关系演算语言：查询操作是以谓词演算作为基础的语言,关系查询语言是一种比Pascal、C等程

13、序设计语言更高级的语言。 Pascal、C、关系代数语言属于过程性语言，在编程时必须给出获得结果的操作步骤。 而关系演算语言属于非过程性语言，编程时只需要指出需要什么信息，不必给出具体的操作步骤。,干什么？ 怎么干？,干什么？,2.3 关系代数,25,2.3 关系代数,关系代数、元组关系演算和域关系演算三种语言在表达能力上是完全等价的。 关系代数、元组关系演算和域关系演算都是抽象的查询语言，与实际DBMS中实现的语言（SQL）不完全一样，可以用来评估实际系统中查询语言的能力 关系数据语言表达能力完全相同、非过程化、功能强且可嵌入使用,26,关系代数语言的组成,关系代数语言是通过对关系的运算来表

14、达查询，通过对关系进行“分割”或者“重组”，得到新的关系 关系代数以元组的集合为运算对象，通过各种运算形成新的元组集合 关系运算分为： 集合运算 关系运算 扩充的关系运算,27,1.集合运算 关系代数是一种抽象的查询语言。它以关系为运算对象，通过对关系进行“组合”或“分割”，得到所需的数据集合关系。 分类： 集合运算（并、交、差；广义笛卡尔积） 关系运算 （投影、选择、连接和除运算）,设：t 为元组变量；R、S为同类关系(同元、相应属性同域）； 下列运算结果为同类关系： (1)并运算: RUS =t |（tR）（t S） (2)差运算: R-S=t |（tR）（t S） (3)交运算: RS=

15、t |（tR）（t S）,R,S,2.3 关系代数,28,关系的集合运算实例,29,(4)广义笛卡尔积: R、S可为不同类关系，则结果为不同类关系： RS=tr ts|（trR）（ts S）,连接为 m+n目关系,m目关系,n目关系,2.3 关系代数,30,元组的前n列是关系R的一个元组 后m列是关系S的一个元组,2.3 关系代数,31,记号 设t为R的元组变量，设：R（A1，A2，An) = R(U) tAi (Ai为属性)： R在属性Ai上的所有值。 tA (A为属性集)，R在属性集A上的所有值。 例：t学号 -R中学号上的值 t 学号，姓名,学号 姓名 年龄,t,2.3 关系代数,32,

16、2.专门的关系运算 （1）选择 是行上的选择，产生同类关系。 F(R)=t|(tR)F(t)=true 含义：由R中满足F条件的元组组成。 其中：F由属性名（值）、比较符、逻辑运算符组成。 例： A25 A3 “f”(R) 或： 25 3 “f”(R) 选择运算是从行的角度进行的运算, 25 3 “f”(R),2.3 关系代数,33,（2）投影运算 是列上的选择，产生不同类关系。 A(R)=tA |(tR) 含义：R中取属性名表A中指定的列，消除重复元组。 例： A3，A2(R),2.3 关系代数,34,投影操作主要是从列的角度进行运算,用关系代数表示查询： 例：查选2号课程的学生记录。 例:

17、 成绩在90分以上的学生号。,解： Cno=2(SC),解: Sno(Grade90(SC),2.3 关系代数,35,（3）连接运算： 一般连接 它从两个关系的笛卡尔积中选取属性间满足一定条件的元组。 R S=tr ts|(trR)(tsS)trA tsB,比较运算符,含义： 从R X S中选取R关系在A属性组上的值与S关系在B属性组上值满足关系的元组。,2.3 关系代数,36,A B,= R. A S. B(RS),连接举例,R S,CE,37,X,连接 = 笛卡尔积 + 选择, 等值连接：为“=”的连接。 为“”的连接运算称为等值连接 等值连接的含义 从关系R与S的广义笛卡尔积中选取A、B

18、属性值相等的那些元组，即等值连接为： R S = | tr Rts StrA = tsB ,2.3 关系代数,38,R S,R.B=S.B,等值连接举例,39, 自然连接 设R、S有同名属性集B R S= tr ts|(trR)(tsS)trB = tsB,其中B是R和S的公共属性（同名属性组），并且在形成的新关系中要去掉重复的属性。 特殊的等值连接，要求两个关系中进行比较的分量必须是同名属性组,2.3 关系代数,40,R S,自然连接举例,R S,R.B=S.B,41,等值连接与自然连接的区别： （1）自然连接一定是等值连接，但等值连接不一定是自然连接。因为自然连接要求相等的分量必须是公共属

19、性，而等值连接相等的分量不一定是公共属性。 （2）等值连接不把重复的属性去掉，而自然连接要把重复属性去掉。,注意,若R、S无公共属性，R S=？,2.3 关系代数连接,42,R S= tr ts|(trR)(tsS)trB = tsB,回忆：关系的“乘”运算 广义笛卡尔积 R(X)乘以S(Y)：把X属性组上的每一种取值都与Y属性组上的每一种取值组合在一起,（4）除运算,2.3 关系代数,43,被除数,商(X),除数(Y),关系的除运算可以看成是“乘”运算的逆运算,（4）除运算,2.3 关系代数,44,余数？,象集（Image Set） 关系R(X , Z), X, Z是属性组，x是X上的取值，

20、定义x在R中的象集为 Zx=tZ|tRtX=x 从R中选出在X上取值为x的元组，去掉X上的分量，只留Z上的分量,X Z,张军同学所选修的全部课程,x=张军,Zx,（4）除运算,2.3 关系代数,45,选择 + 投影,做法：逐个考虑选课关系SC中的元组r，求r在姓名SN上的分量x，再求x在选课关系中的象集课程Cx，若Cx包含了所有的课程C，则x是满足条件的一个元组, x | x=rSN rSC CxC ,选修全部课 程的学生,全部课程,x同学所选修 的全部课程,除定义: R(X,Y) S(Y) = trX | trRY(S)Yx 其中Yx为x在R中的象集, x=trX,除运算,如何得到选修了全部

21、课程的学生？,2.3 关系代数,46,2.3 关系代数,设关系R(X，Y)和S(Y，Z)，X，Y，Z为属性组 RS=tX|tR y(S)Yx , X(R) Yx为x在R中的象集: 对于每个值x， xX(R) 求：y (X=x(R) 结果为：象集Yx包含了y(S)的x。,关系代数定义了除运算。但实际应用中，当关系R真包含了关系S时，RS才有意义。 R能被S除尽的充分必要条件是： R中的属性包含S中的所有属性；R中有一些属性不出现在S中。 设R为r元、S为s元关系(rs0)，当关系R真包含了关系S时，RS可用下式计算： RS =1,2,r-s(R)-1,2,r-s(1,2,r-s(R)S)-R)

22、【例2.8】设R(S#,P#)、W1(P#)、W2(P#)、W3(P#)。 则RW1可表示为： S#(R)-S#(S#(R)W1)-R) 同理可列出另外两式。,R,S,2.3 关系代数,（4）除运算,例RWi的运算结果可理解为： R中包含Wi属性值的那些元组在R与Wi的属性名之差（即S#）上的投影。,2.3 关系代数,示例 求同时选修了001和002号课程的学生号 方案1： S#，C#(SC) C# = 001 C# = 002 (C) 方案2： S#(SC C# = 001 C# = 002 (C) 哪一个正确？,2.3 关系代数,50,S#，C#(SC) C# = 001 C# = 002

23、 (C),2.3 关系代数,51,S#(SC C# = 001 C# = 002 (C),2.3 关系代数,52,X = S#, Grade,=,R,AB (R),S,AB (R) CD (S),AB (R) CD (S)-R,R S=,-,=,2.3 关系代数,53,R(X,Y) S(Y)=X(R) X(X(R) Y (S) - R ),Student,2.3 关系代数(综合举例）,54,Course,2.3 关系代数(综合举例）,55,SC,2.3 关系代数(综合举例）,56,2.2 关系代数,例: 查询至少选修了一门其直接先行课为005号课程的学生名。,学生-课程数据库表见教材: S(s

24、no，sname，sex，age，dept) C(cno，cname， credit ， pcno) SC(sno，cno，grade),sname(pcno=005 (C SC S),A(F (R),例：查选修002号课程的学生姓名与年龄。 sname,age(S cno=002 (SC),例1：查不选002号课程的学生姓名与年龄。,Cno002 ?,sname,age(S)- sname,age(S cno=002 (SC),2.3 关系代数(综合举例）,sname,age(S cno 002 (SC),58,例2：查询至少选修了两门课程的学生学号。,sno(1=425(SCSC),2.3

25、 关系代数(综合举例）,59,例3：查所选课程包含了学生210101所选全部课程的学生号和姓名。,sno,sname(S) (sno，cno(SC) cno (sno=210101 (SC),例4：查询选修了全部课程的学生学号与姓名。,sno,sname(S) (sno，cno(SC) cno(C),2.3 关系代数(综合举例）,60,例9查询至少选修了一门其直接先行课为5号课程的课程的学生姓名。 Sname(Cpno=5(Course SC Student) 或 Sname(Cpno=5(Course)SCSno，Sname(Student) 或 Sname(Sno(Cpno=5(Cours

26、e)SC)Sno，Sname (Student),2.3 关系代数(综合举例）,61,2.3 关系代数,关系代数五种基本运算： 投影,选择,并,差,笛卡尔积 5种基本运算的作用： 1)关系的属性指定 A1 , A2 , , An (R) 2)关系的元组选择 F (R),3)两个关系的归并 R1R2 4)关系中元组的插入 R1R2 5)关系中元组的删除 R1R2,3.扩充的关系运算 （1）广义投影 F1,Fn(R)，其中，F1,Fn是涉及R中常量和属性的算术表达式。 例：sno,sname,sex,age=20(sno=200101(Student) （2）赋值 RS: 将关系S赋予R。 例：C

27、ourse Course099，电子商务，2，003（并） Student Student-(sno=200108(Student) （删除）,2.3 关系代数,63,(3) 外连接 为避免自然连接时因失配而发生的信息丢失，可以假定往参与连接的一方表中附加一个取值全为空值的行，它和参与连接的另一方表中的任何一个未匹配上的元组都能匹配，称之为外连接 外连接 = 自然连接 + 失配的元组 外连接的形式：左外连接、右外连接、全外连接 左外连接 = 自然连接 + 左侧表中失配的元组 右外连接 = 自然连接 + 右侧表中失配的元组 全外连接 = 自然连接 + 两侧表中失配的元组,2.3 关系代数,64,

28、外连接例子,65,（4）半连接 R和S的自然连接只在关系R或关系S的属性集上的投影， 称为半连接。 R和S的半连接记为R S。 S和R的半连接记为S R。 （5）聚集 根据关系中的一组值做统计、计算得到一个值作为结果。 常用聚集函数：max、min、avg、sum、count。 形式：G 聚集函数名(属性)(关系),2.3 关系代数,66,例：求男同学的平均年龄。 G avg(age)(sex=男(Student) 例：计算年龄不小于20岁的同学人数。 G count(sno)(age20(Student) 例：数据库课程的平均分数。 G avg(grade)(cno(cname=数据库(Co

29、urse) SC) （6）外部并 由R和S中的所有属性组成(公共属性只取一次)，其元组由属于R或属于S的元组组成，且元组在新增加的属性填上空值。,2.3 关系代数,67,外部并例子,68,（7）重命名 x(E)：其含义为给一个关系表达式赋予名字。它返回表达式E的结果，并把名字x赋给E。 x(A1，A2，An)(E):其含义为返回表达式E的结果，并把名字x赋给E，同时将各属性更名为A1，A2，An。 例：设关系R(姓名，课程，成绩)，求数学成绩比王红同学高的学生。 S.姓名(课程=数学姓名=王红(R)(课程=数学S(R) R.成绩S.成绩,2.3 关系代数,69,关系演算：以谓词演算为基础表示的

30、关系运算。 关系演算分类 元组关系演算 域关系演算 1. 元组关系演算 用 t|(t) 表示关系。,命题公式,元组变量,表示所有使得为真的元组组成的集合。,2.4 关系演算,70,（1）元组关系演算中的原子公式 R(t) t元组变量 R关系名 R(t)表示：t是关系R的一个元组。 关系R可表示为：t|R(t) tiC 或 Cti C常量 表示：元组t的第i个分量与常量C之间满足关系。 tiuj 其中：t，u元组变量 算术比较符 tit的第i个分量 uju的第j个分量 tiuj表示：元组t的第i个分量与元组u的第j个分量之间满足关系。,2.4 关系演算-元组演算,71,（2）公式的递归定义 每个

31、原子公式是公式。 若1和2是公式，则1、12、12也是公式。 若是公式，则(t)()、(t)()也是公式。 有限次使用上述3条规则得到的公式都是元组关系演算表达式。 公式中各种运算符的优先级： 算术运算符、量词()、逻辑运算符( ),高,低,括号优先,2.4 关系演算-元组演算,72,关系代数表达式,关系演算表达式, 用关系演算表达式表达五种基本运算：,RS= t | R(t)S(t) ,RS= t | R(t) S(t) ,RS = t(n+m) | ( u(n) ) ( v(m) ) ( R(u) S(v) t1=u1 tn=un tn+1=v1 tn+m=vm ) ,F (R) = t

32、| R (t) F ,i1, i2, , ik (R) = t(k) | ( u) (R(u) t1=ui1 tk=uik ),2.4 关系演算关系代数,73,例1 查询信息系（IS）全体学生,F (R) = t | R (t) F ,SIS= t | Student(t) t5=IS ,例2 查询年龄小于20岁的学生,S20= t | Student(t) t420 ,2.4 关系演算关系代数,74,例3 查询学生的姓名和所在系,S1= t(2) | ( u) （Student(u) t1=u2 t2=u5）,i1, i2, , ik (R) = t(k) | ( u) (R(u) t1=u

33、i1 tk=uik ),2.4 关系演算关系代数,75,例2：设R和S都是二元关系，将1,4(2=3(RS)转换成元组演算表达式。,t|(u)(v)(R(u)S(v)u2=v1t1=u1t2=v2),2.4 关系演算-元组演算,76,例1：设有关系R和S，请写出下列元组演算表达式的结果。,R,S,R1=t|S(t)t12 R2=t|R(t) S(t) R3=t|(u)(S(t)R(u)t3u1),2.4 关系演算-元组演算,2.4 关系演算-域演算,78,2.域关系演算 以域变量作为谓词变元的基本对象。 用t1,t2,tk|(t1,t2,tk)表示关系。 t1,t2,tk是元组变量t的各个域分

34、量。 （1）域演算中的原子公式 R（ t1,t2,tk) 表示：由分量t1,t2,tk组成的元组属于R。 tiuj 表示：元组变量t的第i个分量与元组u的第j个分量间满足关系。 tiC 或 Cti 表示：元组变量t的第i个分量与常量C间满足关系。 （2）公式的递归定义 与元组演算定义类似。,例：设有关系R、S、W，试写出下列域演算表达式的结果。,R,W,S,R1=xyz|R(xyz)x3 R2=xyz|R(xyz)S(xyz)y=8 R3=xyz|(u)(v)(R(zxu)W(yv)uv),2.4 关系演算-域演算,79,2.4 关系演算-域演算,用域演算表达式表示下列查询： （1）查询女学生

35、的情况。 R1=t1t2t3t4t5|Student(t1t2t3t4t5)t3=女 （2）查询学号为220101的学生选修的课程在85分以上的课程号。 R2=t2| (t1) (t3) (SC(t1t2t3) t1=220101 t385 ) （3）查询选修课程号为003的所有学生的学号和姓名。 R3=t1t2| (t1) (u2) (Student(t1t2t3t4t5) SC(u1u2u3) t1=u1 u2=003 ),安全运算 不产生无限关系和无穷验证的运算。 安全表达式 安全运算的表达式。 安全限制 安全运算所采取的措施。,关系代数运算总是安全的。关系演算则可能出现无限关系和无穷验

36、证问题,3.关系演算的安全性,例：t|R(t),这是一个无限关系。,要使关系演算是安全的，只要定义一个安全约束有限集合，该有限集是表达式中涉及到的关系中的值的集合。经过安全限制后的表达式其运算是安全的。,关系代数和关系演算所依据的基础理论是相同的，故可进行相互转换。已证明，关系代数、安全的元组演算、安全的域演算在关系的表达能力上是等价的。,2.4 关系演算,81,2.5 查询优化,数据查询是DBS中最基本、最常用和最复杂的数据操作，查询优化是影响关系DBMS性能的关键因素。 关系数据理论基于关系代数，同一个查询要求可以对应多个不同形式却相互等价的表达式。 关系数据查询语言是非过程化的，由DBM

37、S自动生成若干候选的查询计划并择优使用。,82,2.5 查询优化,1.关系DB的查询优化及其目标 查询优化：从查询的多个执行策略中进行合理选择的过程。 目标：选择有效的策略，求得关系式的值，以提高其查询效率。 基本途径可以分为两种：用户处理和机器自动处理 查询优化器： 由DBMS自动生成并从中选取较优查询计划的程序。 查询的开销主要包括： 在单机数据库中：总代价 = I/O代价 + CPU代价 在多用户环境下：总代价 = I/O代价 + CPU代价 + 内存代价 在网络环境下： 总代价 = + 网络代价 查询的执行开销与多个因素有关： 软件环境、硬件环境、数据量、方法。,2.5 查询优化,关系

38、数据库查询过程：,为什么要查询优化？,例: Student表有l03个学生记录，每人平均选10门课， SC表共有1000*10=l04个选课记录。要求: 查学生“王林”选课成绩在85分以上的课程号。 SELECT cno FROM S，SC WHERE S.sno=SC.sno AND sname=王林 AND grade 85 ；,等价的关系代数表示： cno( F1 F2 F3 ( SSC ) ) cno( F2 F3 ( S SC ) ) cno(F2 (S) F3 (SC) ),哪种效率高？,连接时间复杂度为： 103104=O(107) 10310=O(104) 110=O(101)

39、,对执行基本运算(关系扫描与连接)的次数进行分析：, cno( F1 F2 F3 ( SSC ) ) cno( F2 F3 ( S SC ) ) cno( F2 (S) F3 (SC) ) 先在两表上做 ，产生1000*10000=107个连接记录，再在其上进行先后操作。其基本运算的次数为：3*107。 先在两个表上做 ，产生1000*10=104个连接记录，再在其上进行先后操作。其基本运算的次数为：107+2*104。 先分别在两个表上做,再做 ，产生1*10=10个连接记录，再在其上进行 。其基本运算的次数为：104+103+2*101。,连接时间复杂度为： O(107) O(104) O

40、(101),2.5 查询优化,查询处理包括三个基本步骤： 解析和翻译 优化 实现（求值）,解析和翻译 解析：检查语法、验证关系 翻译：将查询转化为内部形式，并进一步翻译为关系代数 实现 执行引擎选取一个查询计划并执行，而后将结果返回给查询.,87,2.5 查询优化,查询优化技术的分类： 规则优化：根据某些启发式规则，如“先选择，后投影”来完成优化。特点是对查询的关系代数表达式进行等价变换，以减少执行开销，也称为代数优化 物理优化：根据数据的物理组织和访问路径进行优化，如用索引进行优化，也称物理优化 代价估算优化：对于多个候选策略逐个进行执行代价估算，从中选择代价最小的作为执行策略，称为代价估算

41、优化,88,2.查询优化的一般策略 当前一般都采用先代数优化、后物理优化的方法。 代数优化的基本原理是对关系代数表达式进行等价变换，选择其中代价最小的。 基本原则就是尽量减少查询过程中产生的中间结果，从而换取较小的时空开销。,89,2.5 查询优化,(1)尽可能先做选择运算、投影运算 这是优化策略中最重要、最基本的一条。 可以有效降低中间结果的数量，常常可使执行时间节约几个数量级。,90,2.5 查询优化,(2)合并笛卡尔积与其后的选择为连接运算 把要执行的笛卡尔积与在它后面要执行的选择结合起来成为一个连接运算，连接特别是等值连接要比笛卡尔积节省很多时间。 R.AS.C(RS)=R S AC,

42、91,2.5 查询优化,(3)把投影运算和选择运算同时进行 如果有若干投影和选择运算，且是对同一个关系执行，则可以在扫描关系的同时进行投影和选择运算，避免重复扫描关系 sno(grade=90(SC),92,2.5 查询优化,(4)让投影运算和其前后的其他运算同时进行 把投影同其前后的双目运算结合起来，不必为了去掉某些列而专门扫描关系 sno(S1-S2) S1 sno(S2),93,2.5 查询优化,(5)在执行连接前对关系适当的预处理 预处理主要有两种：索引连接、归并连接 如：经过排序后的R和S进行连接时，时间复杂度大大降低，从O(m*n)到O(m+n) (6)寻找公共子表达式 如果某个子

43、表达式常常出现，并且将其结果放在外存中的代价小于计算它的代价，则将其计算一次，并放入中间文件中。,94,2.5 查询优化,2.5 查询优化,3. 关系代数表达式的转换 如果在每个合法的数据库实例上, 两个关系代数表达式都生成同样的元组集合, 则这两个关系代数表达式称为等价的 注意: 元组次序是无关的 等价规则说明了两种形式的表达式是等价的 可以用一个表达式替换另一个 12条等价规则,95,1.连接、笛卡尔积交换律 E1E2 E2E1 E1 E2 E2 E1 E1 E2 E2 E1 F F 2.连接、笛卡尔积的结合律 (E1E2) E3 E1(E2E3) (E1 E2) E3 E1 (E2 E3

44、) (E1 E2) E3 E1 (E2 E3) F1 F2 F1 F2,96,2.5 查询优化,3.投影的串接律 条件：t1是t2、 tn的子集 说明：多个投影中，只有最后一个运算是必须的 4.选择的串接律 说明：多个连续的条件可以合并成一个，这样可以一次检查所有条件；同样，合取选择运算可以分解为多个选择运算，便于和其他运算重新组合,97,2.5 查询优化,5.选择与投影的交换律 形式（1） 说明：其中选择条件F只涉及属性A1,A2,An 形式（2） 意义：将条件F中涉及的属性的投影前移，以便投影和其他运算合并 6.选择与笛卡尔积的交换律 如果F中涉及的属性都是E1中的属性：,98,2.5 查

45、询优化,如果F=F1F2，F1只涉及E1中的属性，F2只涉及E2中的属性： 如果F1只涉及E1中的属性，F2涉及E1和E2中的属性： 该规则使得选择尽量能在笛卡尔积之前先做，减小中间结果集。 7.选择与并的交换律 设E1、E2有相同的属性名：,99,2.5 查询优化,8.选择与差的交换律 设E1、E2有相同的属性名： 9.投影与笛卡尔积的交换 设A1,An是E1的属性，B1,Bm是E2的属性： 这个策略使投影在笛卡尔积之前先做 10.投影与并的交换 设E1和E2有相同的属性名,100,2.5 查询优化,11.选择对自然连接的分配律 如果F中涉及的都是E1的属性： （1）F (E1 E2) F (E1 ) E2 如果F=F1F2，F1只涉及E1中的属性，F2只涉及E2中的属性： （2）F (E1 E2) F1 (E1 )