1、台州学院计算机系数据库原理与应用11 1 关系模型的基本概念关系模型的基本概念2 2 关系代数关系代数3 3 关系演算关系演算4 4 查查询优化询优化台州学院计算机系数据库原理与应用21.1 1.1 关系模型概述关系模型概述1.2 1.2 关系数据结构关系数据结构1.3 1.3 完整性规则完整性规则台州学院计算机系数据库原理与应用31.关系模型的数据结构：关系关系(元组的集合元组的集合)。在用户看在用户看来，一个关系就是一张二维表。来，一个关系就是一张二维表。2.关系模型的数据操作：对关系进行操作，且其操作：对关系进行操作，且其操作的对象和结果都是关系的对象和结果都是关系(集合集合)。主要有选
2、择。主要有选择(Select)、投影投影(Project)、连接连接(Join)、除除(Division)、并并(Union)、交交(Intersection)、差差(Difference)等查询等查询(Query)和增加和增加(Insert)、删除删除(Delete)、修改修改(Update)等更新操作。等更新操作。台州学院计算机系数据库原理与应用43.关系操作的表示方式：代数方式、逻辑方式以及结合两者特代数方式、逻辑方式以及结合两者特点的方式。每一种表达方式称为一种关系查询语言或关系数据点的方式。每一种表达方式称为一种关系查询语言或关系数据语言。语言。代数方式：用代数运算来表达关系的查询要
3、求和条件，也称用代数运算来表达关系的查询要求和条件，也称为关系代数方式。为关系代数方式。逻辑方式(关系演算关系演算)：用谓词来表达关系的查询要求和条件用谓词来表达关系的查询要求和条件。元组关系演算：谓词变元为元组元组关系演算：谓词变元为元组 域关系演算：域关系演算：谓词变元为域谓词变元为域 说明：关系代数、元组关系演算和域关系演算均是抽象的说明：关系代数、元组关系演算和域关系演算均是抽象的关系查询语言，且在表达能力上是等价。关系查询语言，且在表达能力上是等价。(3)结合两者的方式：SQL(Structure Query Language)SQL(Structure Query Language
4、)，是介于，是介于关系代数和关系演算之间的关系数据语言。关系代数和关系演算之间的关系数据语言。台州学院计算机系数据库原理与应用54.4.关系语言可以分三类关系语言可以分三类 关系代数语言关系代数语言 例如例如 ISBL 元组关系演算语言元组关系演算语言 例如例如 ALPHA,QUEL关系数据语言关系数据语言 关系演算语言关系演算语言 域关系演算语言域关系演算语言 例如例如 QBE 具有关系代数和关系演算双重特点的语言具有关系代数和关系演算双重特点的语言 例如例如SQL5.完整性约束：关系模型允许定义三类完整性约束，即关系模型允许定义三类完整性约束，即 实体完整性；实体完整性；参照完整性；参照完
5、整性；用户定义的完整性。用户定义的完整性。返回DBMS自动支持台州学院计算机系数据库原理与应用61.关系的定义 定义3.1:给定一组集合给定一组集合D1,D2,Dn，且这些集合可以且这些集合可以相同相同,定义定义D1,D2,Dn的笛卡尔积的笛卡尔积(Cartesian Product)为为 D1D2Dn=(d1,d2,dn)|di Di，i=l,2,n，其中的每一个元素其中的每一个元素(d1,d2,dn)叫做一个叫做一个n元组元组(n-tuple)，元素中第元素中第i个值个值di叫做第叫做第i个分量。个分量。台州学院计算机系数据库原理与应用7 例3.1 设设D1=1,2,3,D2=a,b,则则
6、D1D2=(1,a),(1,b),(2,a),(2,b),(3,a),(3,b),是元组的集合，是元组的集合，它还可用下图表示它还可用下图表示。123 D1 D21 a1 b2 a2 b3 a3 bab=台州学院计算机系数据库原理与应用8 定义3.2 笛卡尔积笛卡尔积D1D2Dn的任一个子集称为的任一个子集称为D1,D2,Dn上的一个关系。集合上的一个关系。集合D1,D2,Dn是关系中是关系中元组的取值范围，称为关系的域元组的取值范围，称为关系的域(Domain)，n称为关系称为关系的度的度(Degree)。从例从例3.13.1可知，关系就是一个二维表，表中的每一行对可知，关系就是一个二维表，
7、表中的每一行对应一个元组，每一列对应一个域。每一列有一个列名，应一个元组，每一列对应一个域。每一列有一个列名，它可以用域名表示，但由于不同列对应的域可以相同，它可以用域名表示，但由于不同列对应的域可以相同，因此需要不同的命名。这样，关系中的因此需要不同的命名。这样，关系中的列称为关系的称为关系的属性，属性，列名称为属性名。为属性名。台州学院计算机系数据库原理与应用9 例例3.2 3.2 选课结果关系选课结果关系ScoursesScourses 如下如下D D0 0=Sno=S01,S02,S03,S04=Sno=S01,S02,S03,S04D D1 1=SnameSname=王建平王建平,刘
8、华刘华,范林军范林军,李伟李伟 D D2 2=Class=19990l,199902,200001=Class=19990l,199902,200001D D3 3=CnameCname=数据结构数据结构,计算机原理计算机原理,数据库原理数据库原理 D D4 4=TnameTname=张征张征,杜刚杜刚,赵新民赵新民 SnoSnameClassCnameTnameS01S02S03S04王建平刘华范林军李伟19990l199902200001200001数据结构计算机原理数据库原理数据结构张征杜刚赵新民张征台州学院计算机系数据库原理与应用10 笛卡尔积笛卡尔积D D0 0D D1 1D D2
9、2D D3 3D D4 4是一个五元组的是一个五元组的集合，共有集合，共有4 44 43 33 33=3=432个元组，而关，而关系系ScoursesScourses是它的一个子集。可以发现，笛卡尔是它的一个子集。可以发现，笛卡尔积的某些元组并没有实际意义，如积的某些元组并没有实际意义，如S04,王建平,199902,数据结构,张征是笛卡尔积中的一个是笛卡尔积中的一个元组，但它是无意义的。元组，但它是无意义的。台州学院计算机系数据库原理与应用11由关系定义可得关系的如下性质由关系定义可得关系的如下性质(第二章已提到第二章已提到)(1)(1)每一列中的值是同类型的数据，都来自同一个域。每一列中的
10、值是同类型的数据，都来自同一个域。(2)(2)不同的列可以有相同的域，每一列称为一个属性，用属性名不同的列可以有相同的域，每一列称为一个属性，用属性名标识。标识。(3)(3)元组中的每个分量是不可分的数据项。元组中的每个分量是不可分的数据项。(4)(4)关系中的各个元组是不同的，即不允许有重复的元组。关系中的各个元组是不同的，即不允许有重复的元组。(5)(5)元组的次序是无关紧要的元组的次序是无关紧要的。说明：关系中的元组与E-R模型中的实体1-1对应，本书以后不加区别的使用。因此，关系是元组的集合，亦即实体的集合。台州学院计算机系数据库原理与应用12候选键(Candidate Key)：能唯
11、一地标识出一个元组的属能唯一地标识出一个元组的属性或属性组。性或属性组。联合键(Concatenated Key)：两个或两个以上属性组成的候选键。两个或两个以上属性组成的候选键。全键(All-Key)：关系的全部属性构成关系的唯一候选键。该关系称为关系的全部属性构成关系的唯一候选键。该关系称为全键关系全键关系(All-Key Relation)主键(Primary key)：在关系的多个候选键中选择的一个候选键，用它在关系的多个候选键中选择的一个候选键，用它作为元组的唯一标示。在一个关系中只能有一个主键。作为元组的唯一标示。在一个关系中只能有一个主键。外键(Foreign Key)：关系关系
12、R中的一组属性中的一组属性A不是关系不是关系R的主键，但的主键，但A是是另一个关系另一个关系S的主键，则属性组的主键，则属性组A就是关系就是关系R的外键。的外键。台州学院计算机系数据库原理与应用13关系模式：对一类实体特征的结构性描述，即对关系的结构性：对一类实体特征的结构性描述，即对关系的结构性描述，该描述一般包括关系名、属性名、属性域的类型和长度，描述，该描述一般包括关系名、属性名、属性域的类型和长度，属性之间固有的依赖联系等。属性之间固有的依赖联系等。若若U=A1,A2,An为关系为关系R的属性集，则关系模式简记为的属性集，则关系模式简记为R(U)或或R(A1,A2,An)关系模式和关系
13、的区别和联系：关系模式描述的是关系的静态关系模式描述的是关系的静态结构信息，是对一个关系的结构信息，是对一个关系的“型型”的描述，是相对固定的。关的描述，是相对固定的。关系是在关系模式约束之下的若干实体的集合，实体的数量是随系是在关系模式约束之下的若干实体的集合，实体的数量是随时间变化的，但这种变化必定在关系模式的约束范围内。时间变化的，但这种变化必定在关系模式的约束范围内。返回台州学院计算机系数据库原理与应用141.实体完整性规则(Entity Integrity)：关系中每一个元关系中每一个元组的主键属性对应的各个分量不能为空值。组的主键属性对应的各个分量不能为空值。空值：当前：当前“不知
14、道不知道”的值，它既不是的值，它既不是0也不也不是空字符是空字符，用，用NULL表示。表示。以关系Students为例：CREATE TABLE Students (Sno char(4)primary key Sname );台州学院计算机系数据库原理与应用15 2 2.参照完整性规则(Reference Integrity)：设属性组设属性组A是关系是关系R的外键且的外键且A又是关系又是关系S的主键，则对于的主键，则对于R中中的每一个元组在属性的每一个元组在属性A上的值必须为：或者空值或上的值必须为：或者空值或者等于者等于S中某一个元组的主键值。中某一个元组的主键值。(1)所谓参照，就是关
15、系所谓参照，就是关系R与另一关系与另一关系S之间的联系，之间的联系，这种联系是通过其相同属性来建立的。参照完整性这种联系是通过其相同属性来建立的。参照完整性规则给出规则给出 了关系之间建立联系的约束条件。了关系之间建立联系的约束条件。(2)实体完整性和参照完整性都是关系模型必须满实体完整性和参照完整性都是关系模型必须满足的完整性约束条件，这些约束条件由足的完整性约束条件，这些约束条件由RDBMS自动自动支持支持。请看文件“01-图示参照完整性”台州学院计算机系数据库原理与应用16 SQL Server 中按照以下命令建立参照完整性中按照以下命令建立参照完整性(假设假设Students和和Cou
16、rses已存在已存在)：CREATE TABLE Reports(Sno CHAR(10),Cno CHAR(6),Grade INT,PRIMARY KEY(Sno,Cno),CONSTRAINT Student_Report FOREIGN KEY(Sno)REFERENCES Students,CONSTRAINT Report_Course FOREIGN KEY(Cno)REFERENCES Courses,);台州学院计算机系数据库原理与应用173.用户定义的完整性规则用户定义的完整性规则(User-defined Integrity)：用户根据具体应用而对数据附加的约束条件。说明
17、：现在的商品化RDBMS提供了定义和检查这类完整性约束的机制，例如：CREATE TABLE Reports (Sno CHAR(5)NOT NULL,Cno CHAR(5)NOT NULL,Grade INT CHECK(Grade=0 and GradeD R S台州学院计算机系数据库原理与应用28自然连接(Natural join)Natural join)：两个关系进行连接比较的属性列完两个关系进行连接比较的属性列完全相同的等值连接，且结果关系中没有重复的属性。即若全相同的等值连接，且结果关系中没有重复的属性。即若R R和和S S具有相同的属性组具有相同的属性组A A，则自然连接可记作
18、：则自然连接可记作：其中集合其中集合B B是关系是关系R R和和S S属性的并集。属性的并集。自然连接是同时从行和列的角度进行运算，是自然连接是同时从行和列的角度进行运算，是最有用的等值连接。以后若无特殊说明，其连接均最有用的等值连接。以后若无特殊说明，其连接均指自然连接。指自然连接。R S=B(R.A=S.A(RS)台州学院计算机系数据库原理与应用29 关系关系R R、S S以及它们的自然连接结果关系。以及它们的自然连接结果关系。AC Ca1a1a2a3b1b2b2b13528BCDb1b2b2b13428d1d2d1d2ABCDa1a2a3b1b2b1328d1d1d2关系R关系S自然连接
19、结果台州学院计算机系数据库原理与应用30除法运算(Division)：设关系设关系R和和S的度数分别为的度数分别为n和和m(n m 0)，那那么么RS是一个度数为是一个度数为(n m)的关系，它满足下列条件：的关系，它满足下列条件：RS中的中的每个元组每个元组t与与S中每个元组中每个元组u所组成的元组所组成的元组(t,u)必在关系必在关系R中。为叙中。为叙述方便起见，我们假设述方便起见，我们假设S的属性为的属性为R中的后中的后m个属性，则个属性，则RS的具的具体计算过程如下：体计算过程如下：(1)T 1,2,n-m(R)(2)W(TS)R (即计算即计算TS中但不在中但不在R中的元组中的元组)
20、(3)V 1,2,n-m(W)(4)RST V台州学院计算机系数据库原理与应用31 例例3.7 3.7 关系关系R R和和S S 的除法的除法R RS S ABCDa1a1a1a2a3a3b1b1b1b2b3b3c1c2c3c2c1c2d1d2d3d2d1d2CDc1c2d1d2ABa1a2a3b1b2b3ABCDa2b2c1d1ABa2b2ABa1a3b1b3RSTWVR S 台州学院计算机系数据库原理与应用32例3.8 检索班级编号为检索班级编号为199902199902的全班学生的学号。对应关系代的全班学生的学号。对应关系代数表达式为：数表达式为：Sno(class=199902(Stu
21、dents)SELECT Sno FROM Students WHERE Class=199902例例3.9 3.9 查询选修了查询选修了英语英语 课程的学生姓名。课程的学生姓名。Sname(Cno(Cname=英语英语Courses)Reports)Students)SELECT Sname FROM Courses C,Reports R,Students SWHERE S.Sno=R.Sno AND R.Cno=C.Cno AND C.Cname=英语Sname(Cname=英语英语(Courses Reports Students)台州学院计算机系数据库原理与应用33例例3.10 3.
22、10 检索选修了所有课程的学生编号和姓名。检索选修了所有课程的学生编号和姓名。查学生选修课程的代数表达式为：查学生选修课程的代数表达式为：Sno,Cno(Reports)查现开设全部课程的代数表达式为查现开设全部课程的代数表达式为：Cno(Courses)根据除法定义，查选修了所有课程的根据除法定义，查选修了所有课程的学生编号的代数表达式为：的代数表达式为：Sno,Cno(Reports)Cno(Courses)；查选修了所有课程的学生编号和姓名的代数表达式为：查选修了所有课程的学生编号和姓名的代数表达式为：Sno,Sname(Students (Sno,Cno(Reports)Cno(Cou
23、rses)请同学们课后写出对应的SQL语句台州学院计算机系数据库原理与应用34例例3.11 3.11 设一学号为设一学号为S01S01的学生选修了课程号为的学生选修了课程号为C02C02的课程且得分为的课程且得分为9595，则将这些信息插入关系则将这些信息插入关系ReportsReports中的关系代数表达式为：中的关系代数表达式为：ReportsS01,C02,BReportsS01,C02,B。例例3.12 3.12 在关系在关系ReportsReports中删除学号为中删除学号为S02S02、选修课为选修课为网络网络课程的元课程的元组的关系代数表达式为：组的关系代数表达式为：请同学们课后
24、写出对应的SQL语句Reports(Cno(Cname=网络网络(Courses)Sno=S02(Reports)台州学院计算机系数据库原理与应用353.1 3.1 元组关系演算元组关系演算3.2 3.2 域关系演算域关系演算3.3 3.3 关系运算的安全限制关系运算的安全限制 台州学院计算机系数据库原理与应用361.元组关系演算表达式：表达式的一般形式为表达式的一般形式为 t|(t)，它是使它是使(t)为真的所有元组为真的所有元组t构成的集合。其中，构成的集合。其中，t是元是元组变量组变量，(t)是元组关系演算公式是元组关系演算公式(简称公式简称公式)，它由原，它由原子公式和运算符组成。子公
25、式和运算符组成。R=t|(t)；t R (t)为真；为真；甚至可以表示为甚至可以表示为 R=t|R(t)；t=(Sno,Sname,Ssex,Sage,Sdept)for Studnets (t)=“t5=数学数学”，则，则 R=t|(t)如下：如下：SnoSnameSsexSageSdeptS04S05S06李伟黄河长江男男男191820数学数学数学台州学院计算机系数据库原理与应用37 2.元组关系演算的原子公式一般有下三类：R(t)。其中其中R是关系名，是关系名，t是元组变量，是元组变量，R(t)表示这样一表示这样一个命题：个命题：“t是关系是关系R中的一个元组中的一个元组”。即关系。即关
26、系R可表示为可表示为 t|R(t)。ti sj。t、s是元组变量，是元组变量，是算术比较符。是算术比较符。ti，sj分别表示分别表示t的第的第i个分量和个分量和s的第的第j个分量。个分量。ti sj表示这样表示这样一个命题一个命题“元组元组t的第的第i个分量与元组个分量与元组s的第的第j个分量之间满个分量之间满足足 关系关系”。ti a或或a ti。其中其中a为常量，为常量，ti a表示这样一个命题表示这样一个命题“元组元组t的第的第i个分量与常量个分量与常量a满足满足 关系关系”。台州学院计算机系数据库原理与应用38元组关系演算公式定义为：元组关系演算公式定义为：每个原子公式都是公式。每个原
27、子公式都是公式。设设 l l和和 2 2是公式，则是公式，则 l l 2 2、l l 2 2、l l也都是也都是公式。公式。设设(t)t)是公式，是公式，t t是元组变量，则是元组变量，则 t(t(t)(t)和和 t(t(t)(t)都是公式。都是公式。元组演算表达式中的公式元组演算表达式中的公式(t)t)都是由以上三种方式都是由以上三种方式经过有限次复合而成的。经过有限次复合而成的。台州学院计算机系数据库原理与应用39元组关系演算表达举例元组关系演算表达举例 例3.13 检索班级编号为检索班级编号为199902199902的全班学生的学号：的全班学生的学号：t1|S(t)t5t1|S(t)t5
28、199902199902例3.14 查询选修了查询选修了英语英语 课程的学生姓名：课程的学生姓名：t2|S(t)t2|S(t)u(R(u)u1=t1u(R(u)u1=t1 v(C(v)v1=u2v2=v(C(v)v1=u2v2=英语英语)或者或者 t2|S(t)t2|S(t)u u v(R(u)C(v)v(R(u)C(v)u1=t1v1=u2v2=u1=t1v1=u2v2=英语英语)例3.15 检索选修了所有课程的学生：检索选修了所有课程的学生：t|S(t)t|S(t)v(C(v)v(C(v)u(R(u)u2=v1u1=t1)u(R(u)u2=v1u1=t1)台州学院计算机系数据库原理与应用4
29、01.域关系演算表达式：(t t1 1,t,t2 2,t tk k)|)|(t(t1 1,t,t2 2,t tk k)，它是它是使使 为真的那些为真的那些t t1 1,t,t2 2,t tk k 组成的元组之集合。组成的元组之集合。其中其中t t1 1,t t2 2,t tk k是域变量，是域变量，是由原子公式和运算符组成的公式。是由原子公式和运算符组成的公式。R=(t t1 1,t,t2 2,t tk k)|(t t1 1,t,t2 2,t tk k)对对Students表，表，(t t1 1,t,t2 2,t,t5 5)=(Sno,Sname,Ssex,Sage,Sdept)若若 (t t
30、1 1,t,t2 2,t,t5 5):“t5=数学数学”，则则 R=(t t1 1,t,t2 2,t,t5 5)|(t t1 1,t,t2 2,t,t5 5)如下：如下：SnoSnameSsexSageSdeptS04S05S06李伟黄河长江男男男191820数学数学数学台州学院计算机系数据库原理与应用412.2.域关系演算表达式中的原子公式有以下二种：域关系演算表达式中的原子公式有以下二种：R(tR(t1 1,t,t2 2,t tk k)。R R是一个是一个k k元关系，每个元关系，每个t ti i是域变量或者常是域变量或者常量。量。x x y y。其中其中x x为域变量，为域变量，y y为
31、域变量或者为常量。为域变量或者为常量。是算术是算术比较符。比较符。x x y y表示表示x x与与y y满足满足 关系。关系。台州学院计算机系数据库原理与应用42例3.16 检索班级编号为检索班级编号为199902199902的全班学生的学号。其域关系演的全班学生的学号。其域关系演算表达式为：算表达式为：t t1 1|S(t|S(t1 1,t,t2 2,t,t3 3,t,t4 4,t,t5 5)t)t5 5=199902=199902例3.17 查询选修了查询选修了英语英语 课程的学生名。其域关系演算表达式为：课程的学生名。其域关系演算表达式为：t t2 2|S(t|S(t1 1,t,t2 2
32、,t,t3 3,t,t4 4,t,t5 5)u u1 1 u u2 2 v v1 1 v v2 2(R(u(R(u1 1,u,u2 2,u,u3 3)C(v)C(v1 1,v,v2 2,v v3 3)t)t1 1=u=u1 1uu2 2=v=v1 1vv2 2=英语英语)例3.18 检索选修了所有课的学生，域关系演算表达式为：检索选修了所有课的学生，域关系演算表达式为：(t t1 1,t,t2 2,t,t3 3,t,t4 4,t,t5 5)|S(t)|S(t1 1,t,t2 2,t,t3 3,t,t4 4,t,t5 5)v v1 1 u u1 1 u u2 2(R(u(R(u1 1,u,u2
33、2,u,u3 3)C(v)C(v1 1,v,v2 2,v v3 3)u)u2 2=v=v1 1uu1 1=t=t1 1)台州学院计算机系数据库原理与应用433.由元组演算表达式t|(t)构造等价的域演算表达式的步骤如下：如果如果t是是k元的元组，则引入元的元组，则引入k个域变量个域变量t1，t2,tk,用用t1,t2,tk 替换替换t，用用ti替换替换ti。对于量词对于量词(u)或或(u)，如如u是是m元的元组，则引入元的元组，则引入m个新的域变量个新的域变量u1，u2，um，在对应量词的辖域在对应量词的辖域内，用内，用u1，u2，um 替换替换u，用用ui替换替换ui。用用(u1)(um)替
34、换替换(u)、用用(ul)(um)替换替换(u)。台州学院计算机系数据库原理与应用441.无限关系：当元组变元：当元组变元t t中某一属性的定义域是无限时，中某一属性的定义域是无限时，t t|R(|R(t t)为无限关系。为无限关系。2.无穷验证过程：t t的取值范围为无限，验证的取值范围为无限，验证(t t)()(t t)为为真的过程。真的过程。3.安全表达式：不产生无限关系和无穷验证过程的表达式。不产生无限关系和无穷验证过程的表达式。4.安全限制：为保证所有表达式都是安为保证所有表达式都是安全表达式所采取的所采取的限制措施。限制措施。5.关系代数运算是安全的：当给定的所有关系是有限时，当给
35、定的所有关系是有限时，其运算的有限次复合不会出现无限关系和无穷验证过程。其运算的有限次复合不会出现无限关系和无穷验证过程。台州学院计算机系数据库原理与应用456.关系演算就不一定是安全的，因为存在无限关系和无穷验证，因为存在无限关系和无穷验证过程过程7.对关系演算进行安全限制的方法：定义一个定义一个 的有限符号集的有限符号集合，记作合，记作DOM(DOM()()(不必是最小集合不必是最小集合)，它由以下两类符号构，它由以下两类符号构成：成：中的常量符号；中的常量符号；中涉及的所有关系的所有元组的各个分量值。中涉及的所有关系的所有元组的各个分量值。把把 t|R(t)t|R(t)和和(t)(t)t
36、)(t)中的中的t t都限制在都限制在DOM(DOM()中取值，中取值，就不会出现无限关系和无穷验证过程，这时关系演算是安就不会出现无限关系和无穷验证过程，这时关系演算是安全的。全的。台州学院计算机系数据库原理与应用468.8.一个元组演算表达式一个元组演算表达式 t|t|(t)(t)称为是安全的，如果它满足以下称为是安全的，如果它满足以下条件：条件：如果元组如果元组t t能使能使(t)(t)为真，则为真，则t t的每个分量是的每个分量是DOM(DOM()中的中的元素。元素。(2)(2)对于对于 中的每一个形如中的每一个形如(t)(t)(t)的子表达式，如果的子表达式，如果t t使使(t)(t
37、)为真，则为真，则t t 的每一个分量是的每一个分量是DOM(DOM()中的元素。中的元素。(3)(3)对于对于 中的每个形如中的每个形如(t)(t)(t)的子表达式，如果的子表达式，如果t t使使(t)(t)为为假，则假，则t t 的每个分量必属于的每个分量必属于DOM(DOM()，也可以说，若，也可以说，若t t的某个的某个分量不属于分量不属于DOM(DOM()，则，则(t)(t)为真。为真。台州学院计算机系数据库原理与应用47 设关系设关系R R如下，求元组演算表达式如下，求元组演算表达式S=t|R(t)S=t|R(t)ABCab1378关系R注意属性B和C的域是整数集，如不进行限制，S
38、是一个无限关系。根据安全表达式的条件和DOM()的构造方法，令DOM()A(R)B(R)C(R)a,b,1,3,7,8，则结果关系：S=t|R(t)=DOM()DOM()DOM()R。因此，由于有DOM()的安全限制，关系S中有214个元组，故是有限的。台州学院计算机系数据库原理与应用484.1 查询优化概述4.2 查询优化的一般策略4.3 关系代数的等价公式4.4 查询优化的一般步骤台州学院计算机系数据库原理与应用491.查询优化的含义：SQLSQL语言是高度非过程化的语言，用户语言是高度非过程化的语言，用户只要指出只要指出“做什么做什么”，至于，至于“怎么做怎么做”则由则由RDBMSRDB
39、MS自动自动优化实现。优化实现。好处好处：给用户带来极大的方便，使对数据库的操作变得简给用户带来极大的方便，使对数据库的操作变得简便易行。便易行。问题：问题：加重了系统的负担，系统需要自行选择存取路径，加重了系统的负担，系统需要自行选择存取路径，而存取路径选择的好坏是影响查询效率的关键所在。而存取路径选择的好坏是影响查询效率的关键所在。解决解决：在：在RDBMSRDBMS中使用查询优化技术，提高关系系统的中使用查询优化技术，提高关系系统的查询效率。查询效率。台州学院计算机系数据库原理与应用50 2.什么叫查询优化器：RDBMSRDBMS服务器的一个组成部分服务器的一个组成部分(程序程序)，其基
40、本任务是：通过产生多个可供选择的执，其基本任务是：通过产生多个可供选择的执行计划，找到最低估算成本的执行计划来优化一条行计划，找到最低估算成本的执行计划来优化一条SQLSQL语句，以提高语句，以提高RDBMSRDBMS的查询效率。的查询效率。台州学院计算机系数据库原理与应用513.查询优化器的优点 优化器可以从数据字典中获取许多统计信息，如关系中的元组数、优化器可以从数据字典中获取许多统计信息，如关系中的元组数、关系中每个属性值的分布情况等。优化器可以根据这些信息选择关系中每个属性值的分布情况等。优化器可以根据这些信息选择有效的执行计划，而用户程序则难以获得这些信息。有效的执行计划，而用户程序
41、则难以获得这些信息。如果数据库的物理统计信息改变了，系统可以自动对查询进行重如果数据库的物理统计信息改变了，系统可以自动对查询进行重新优化以选择相适应的执行计划。新优化以选择相适应的执行计划。优化器可以考虑数百种不同的执行计划，而程序员优化器可以考虑数百种不同的执行计划，而程序员般只能考虑般只能考虑有限的几种可能。有限的几种可能。优化器中包括了很多复杂的优化技术，这些优化技术往往只有最优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化器相当于使得所有人都拥好的程序员才能掌握。系统的自动优化器相当于使得所有人都拥有这些优化技术。有这些优化技术。台州学院计算
42、机系数据库原理与应用524.DBMS实现查询优化的一般步骤：将查询需求转换成某种内部表示，通常是语法树。将查询需求转换成某种内部表示，通常是语法树。根据一定的等价变换规则把语法树转换成标准根据一定的等价变换规则把语法树转换成标准(优化优化)形式。形式。选择低层的操作算法。对于语法树中的每一个操作需选择低层的操作算法。对于语法树中的每一个操作需要，根据存取路径、数据的存储分布、存储数据的聚要，根据存取路径、数据的存储分布、存储数据的聚簇等信息来选择具体的执行算法。簇等信息来选择具体的执行算法。生成查询计划生成查询计划(查询执行方案查询执行方案)：查询计划由一系列有：查询计划由一系列有次序的内部操
43、作构成的。次序的内部操作构成的。DBMSDBMS生成多个执行方案，生成多个执行方案，在计算每个执行方案的执行代价后，从中选择代价最在计算每个执行方案的执行代价后，从中选择代价最小的一个执行。小的一个执行。台州学院计算机系数据库原理与应用534.在集中式数据库中，查询的执行代价为：总代价总代价=I/OI/O代价代价+CPUCPU代价代价5.在多用户环境下查询的执行代价为：总代价总代价=I/OI/O代价代价+CPUCPU代价代价+内存代价内存代价台州学院计算机系数据库原理与应用54 例3.48 用户要查询选修了用户要查询选修了C02C02号课程的学生姓号课程的学生姓名，他输入的名，他输入的SQLS
44、QL语言表达为语言表达为：SELECT Sname FROM Students S，Reports R WHERE S.Sno=R.Sno AND R.Cno=C02 RDBMS RDBMS将以上要求转换成关系代数表示：将以上要求转换成关系代数表示：台州学院计算机系数据库原理与应用55RDBMSRDBMS将以上要求转换成关系代数表示将以上要求转换成关系代数表示：Q1:Sname(S.Sno=R.SnoR.Cno=C02(StudentsReports)先计算广义笛卡尔积，再做选择操作，最后执行投影先计算广义笛卡尔积，再做选择操作，最后执行投影操作操作。Q2:Sname(R.Cno=C02(St
45、udents Reports)先计算自然连接，再做选择操作，最后执行投影操作。Q3:Sname(Students R.Cno=C02(Reports)先计算选择操作，再做连接操作，最后执行投影操作。台州学院计算机系数据库原理与应用56 在相同的假设条件下，三种查询方式：在相同的假设条件下，三种查询方式：QQ1 1：其时间耗费为其时间耗费为5 510104 4s s QQ2 2：其时间耗费为其时间耗费为210s 210s QQ3 3：其时间耗费为其时间耗费为20s 20s 此例说明了此例说明了RDBMSRDBMS中查询优化的必要性和重要中查询优化的必要性和重要性，同时也给出一些查询优化方法的基本
46、思想：性，同时也给出一些查询优化方法的基本思想：先选择运算后连接运算先选择运算后连接运算台州学院计算机系数据库原理与应用571.选择运算应尽早执行。选择符合条件的元组可以使中间。选择符合条件的元组可以使中间结果所含的元组数大大减少，从而减少运算量和输入输结果所含的元组数大大减少，从而减少运算量和输入输出次数。出次数。2.把投影运算和选择运算同时进行。如果投影运算和选择。如果投影运算和选择运算是对同一关系操作，则可以在对关系的一次扫描中运算是对同一关系操作，则可以在对关系的一次扫描中同时完成，从而减少操作时间。同时完成，从而减少操作时间。3.把投影操作与它前面或后面的一个双目运算结合起来，不必为
47、投影(减少几个字段)而专门扫描一遍关系。4.在执行连接运算之前，可对需要连接的关系进行适当地预处理，如建索引或排序。当一个关系读入内存后，就当一个关系读入内存后，就可根据连接属性值在另一个关系中快速查找符合条件的可根据连接属性值在另一个关系中快速查找符合条件的元组，加速连接运算速度。元组，加速连接运算速度。台州学院计算机系数据库原理与应用585.把笛卡尔乘积和其后的选择运算合并成为连接运算，以避免扫描笛卡尔乘积的中间结果。两个关系的连接运算，两个关系的连接运算，特别是等值连接运算比同样两个关系的笛卡尔乘积节约特别是等值连接运算比同样两个关系的笛卡尔乘积节约更多计算时间。更多计算时间。6.存储公
48、用子表达式。对于重复出现的子表达式对于重复出现的子表达式(简称公用简称公用子表达式子表达式)，如果该表达式的结果不是很大的关系，则应，如果该表达式的结果不是很大的关系，则应将这个公用子表达式的结果关系存于外存。这样，从外将这个公用子表达式的结果关系存于外存。这样，从外存中读出这个关系比计算它的时间少得多，从而达到节存中读出这个关系比计算它的时间少得多，从而达到节省操作时间的目的，特别是当公用子表达式频繁出现时省操作时间的目的，特别是当公用子表达式频繁出现时效果更加显著。效果更加显著。台州学院计算机系数据库原理与应用59定义定义3.1 3.1 设设E1E1和和E2E2是两个关系代数表达式，若将相
49、同的关系是两个关系代数表达式，若将相同的关系代替代替E1E1和和E2E2中的相应关系，所得到的结果关系完全一样，中的相应关系，所得到的结果关系完全一样，则称关系代数表达式则称关系代数表达式E1E1和和E2E2是等价的，或称是等价的，或称E1E1和和E2E2互为等互为等价公式，记作价公式，记作E1E2E1E2。关系代数中一些常用的等价公式。关系代数中一些常用的等价公式。1 1.笛卡尔积的等价公式。设笛卡尔积的等价公式。设E E1 1，E E2 2，E E3 3是关系代数表达式，则是关系代数表达式，则以下等价公式成立：以下等价公式成立：E E1 1E E2 2 E E2 2E E1 1 (交换律交
50、换律)(E E1 1E E2 2)E E3 3EE1 1(E(E2 2E E3 3)()(结合律结合律)台州学院计算机系数据库原理与应用602.连接运算的等价公式。设设E E1 1，E E2 2，E E3 3是关系代数表达式，是关系代数表达式，F F，F F1 1和和F F2 2是连接运算的条件。则以下等价公式成立：是连接运算的条件。则以下等价公式成立：(自然连接的交换律自然连接的交换律)(条件连接的交换律条件连接的交换律)(自然连接的结合律自然连接的结合律)(条件连接的结合律条件连接的结合律)1221EEEE1221EEEEFF)()(321321EEEEEE)()(3213212121EE
