第5章关系系统及其查询优化

5-15-2第五章关系系统及其查询优化要点回顾关系系统关系数据库系统的查询优化5-3关系系统——关系数据库系统（RDBS），其核心是RDBMS。5.0

要点回顾关系模型关系数据结构

单一的数据结构——关系表关系操作集合更新：增加、删除、修改查询：选择、投影、连接、除、并、交、差关系完整性约束实体完整性参照完整性用户定义的完整性5-45.1关系系统什么是关系数据库管理系统呢?支持关系模型的数据库管理系统称为关系数据库管理系统，简称关系系统。关系系统的定义和分类全关系系统的基本准则5-55.1.1关系系统的定义和分类1．关系系统的定义一个系统可定义为关系系统，当且仅当：支持关系数据结构支持选择、投影和（自然）连接运算，对这些运算不要求定义任何物理存取路径。满足上述两个条件的系统就可称为关系系统。这是关系系统的最基本要求，也称为最小关系系统。5-65.1.1关系系统的定义和分类2.关系系统的分类关系系统根据其对关系模型的支持程度可分为三类：最小关系系统关系完备的关系系统全关系系统5-75.1.1关系系统的定义和分类——分类①最小关系系统支持关系数据结构支持选择、投影和（自然）连接运算S

结构M

数据操纵I

完整性I域结并、交、M差、选择、投影、连接运算表选择投影连接除等构S

表等I域结并、、M差、选择交投影连接除等构S

表等5-8②完备的关系系统支持：关系数据结构所有的关系代数运算S

结构M

数据操纵I

完整性5.1.1关系系统的定义和分类——分类选择、投影、连接、并、交、差、除等运算表55--99③全关系系统支持关系模型的所有特征。包括支持域的概念及完整性约束。结构数据操纵完整性5.1.1关系系统的定义和分类——分类55--11005.1.2 全关系系统的基本准则（十三条）1.基本准则准则0：一个关系型的数据库管理系统（RDBMS）必须能完全通过它的关系能力来管理数据库。准则12：无破坏准则。如果一个关系系统具有一个低级（指一次一个记录）语言，则这个低级语言不能违背或绕过完整性准则。55--11112.结构准则准则1：信息准则。关系型的数据库管理系统（RDBMS）的所有信息都应在逻辑一级上用表中的值显式地表示。例:关系表的表名、列名、列的类型、域等信息是数据库的信息，在逻辑上这些信息都用数据字典表中的值表示。准则6：视图更新准则。所有理论上可更新的视图也应该允许由系统更新。5.1.2

全关系系统的基本准则55--11223.完整性准则准则3：空值的系统化处理。全关系型的DBMS应支持空值的概念，并用系统化的概念处理空值准则10：数据完整性的独立性。关系数据库的完整性约束条件必须是用数据库语言定义并存储在数据字典中的，而不是在应用程序中加以定义的。5.1.2

全关系系统的基本准则55--11335.数据操作准则准则2：保证访问准则。依据表名、主码（主键）和列名的组合，保证能以逻辑方式访问关系数据库中的每个

数据项（每个分量值）。准则4：基于关系模型的动态的联机数据字典。数据库的描述在逻辑级上应和普通数据采用同样的表示方式，使得授权用户可以查询一般数据所用的关系语言来查询数据库的描述信息。5.1.2

全关系系统的基本准则55--11445.数据操作准则——准则5准则5：统一的数据子语言准则。一个关系系统可以具有几种语言和多种终端使用方式（如表格填空方式、命令方式等）。但必须有一种语言，它的语句可以表示为具有严格语法规定的字符串，并能全面支持数据定义、视图定义、数据操作、完整性约束、授权以及事务处理等功能。5.1.2

全关系系统的基本准则55--11555.数据操作准则——准则7

准则7：高级的插入、修改和删除操作。关系系统的操作对象是单一的关系。以关系为操作对象不仅简化了用户查询，提高了用户的生产率，而且也为系统提供了很大的余地进行查询优化，提高了系统的运行效率。它允许系统来选择存取路径，以便得到最有效的运行代码。5.1.2

全关系系统的基本准则55--11665.1.2

全关系系统的基本准则5.数据独立性准则准准则则181：：数分据布物独理立独性立。性。无论数据库的数据在存储表示或存取方法关上系作型任数何据变库化管，理应系用统程具序有和分终布端独立活性动。都保持逻辑上的不变性。准则9：数据逻辑独立性。当对基本关系进行理论上信息不受损害的任何改变时，应用程序和终端活动都保持逻辑上的不变性。查询优化概述查询优化的一般准则关系代数等价变换规则查询处理的主要阶段55--11775.2关系数据库系统的查询优化55--11885.2.1查询优化概述一、查询处理及查询优化⒈什么是查询处理？数据库的查询一般都使用查询语言（如SQL语言），从查询语句出发直到获得查询结果有一个处理的过程，这个过程就叫做查询处理。查询处理：“从数据库中检索数据的活动。”55--11995.2.1查询优化概述一、查询处理及查询优化⒉查询处理的目标将高级语言（如SQL）表示的查询转换

为正确有效的、用低级语言表达的执行策略，即实现关系代数，并通过执行该策略来获取

所需数据。⒊查询优化查询优化指的是查询处理的优化。“选择有效的执行策略执行查询的活动。”①代数优化②物理优化③规则优化④代价估算优化55--2200二、查询优化的方法和步骤⒈

查询优化的方法5.2.1查询优化概述对查询语句进行变换，改变基本操作的次序，使查询语句执行起来

更为有效。根据系统提供的存取路径，选择合理的存取策略。根据启发性规则，选择执行策略。对供选择的执行策略进行代价估算。实际系统往往采用多种方式的综合。55--2211⒉查询优化的步骤5.2.1查询优化概述——查询优化的方法和步骤①将查询转换成内部表示。（一般是语法树）②根据一定的等价变换规则将语法树转换成标准（优化）形式。③选择低层的操作算法。④生成查询计划。对多个计划进行代价估算，选取代价最小的计划。55--22225.2.1查询优化概述三、查询的开销一般：总开销=I/O代价+CPU代价多用户系统：总开销=I/O代价+CPU代价+内存代价55--2233例5.1

假设数据库中有两个基本表，计算查询开销。5.2.1查询优化概述——查询的开销中山区解放路10号

116002州市沙河路40号

510501分支机构Branch分支编号城市地址邮编工作人员StaffbranchNocityaddresspostCodeB0001北京北京海淀区青龙桥18号100091B0002石家庄石家庄市北马路90号050003B0003大连大连工号姓名性别职务月薪所属分支B0004广州广staffNonamesexpositionsalarybranchNo……SB1…01赵海洋男…经理8000．B0001B0005长沙长沙市S韶S山20北1路钱1光68明号4男10003

经理6000．B0002SS212孙佩霞女经理助理5000．B0002SS223李万章男业务员3000B0002SB112周全男经理助理6000B0001………………SG401吴德海男经理5500B000455--22445.2.1查询优化概述—查询的开销(例5.1)以查询在北京分支机构工作的经理为例：用SQL语句表达的查询为：SELECT

*FROM

staff，branchWHERE

staff.branchNo=branch.branchNo

AND(staff.position=’经理’AND

branch.city=’北京’)；设：关系表branch50个元组，即共有50个分支机构，每个分支机构有一位经理。关系表branch中有5个元组的所在地为北京，即北京有5个分支机构。关系表staff有1000个元组，即共有1000个员工。55--2255计算查询开销—①形成笛卡尔积再选择5.2.1查询优化概述—查询的开销(例5.1)s

staff.branchNo=branch.branchNo∧staff.position=‘经理’∧branch.city=‘北京’(staff

×

branch)读取staff表1000

次，读取branch表50次，计1050次。形成笛卡尔积关系表：1000×50

=50000读取笛卡尔积关系表并提取满足选择条件的元组访问：50000访问次数

2×50000

=1010505-265.2.1查询优化概述—查询的开销(例5.1)计算查询开销—②先连接后选择s

staff

.position=‘经理’∧branch

.city=‘北京’(staff

▷◁branch)staff.branchNo=branch.branchNo读取staff表1000

次，读取branch表50次，计1050次。形成staff和branch连接的关系表1000从形成staff和branch连接的关系表中提取满足选择条件的元组1000访问次数

2×1000

=305055--2277计算查询开销—③分别选择再连接5.2.1查询优化概述—查询的开销(例5.1)(sstaff.position=‘经理’(staff))▷◁(sbranch.city=‘北京’(branch))staff.branchNo=branch.branchNo查询σstaff.position=‘经理’（staff）需访问1000次形成50个记录查询σbranch.city=‘北京’（branch）需访问50次形成5个记录访问新形成的两个表：50+5访问次数1000+50+50+5+50+5=116055--22885.2.2查询优化的一般准则准则一：基本准则——尽可能先做选择运算理由：选择运算一般可减少关系中元组的数量，从而降低了后面关系处理的复杂度。55--22995.2.2查询优化的一般准则—准则二准则二：执行连接前对关系适当进行预处理。①

索引连接

在连接属性上建立索引，然后根据建立的索引查找元组进行连接。②

排序归并连接

对连接的两个表按连接属性排序，然后将连接属性相同的元组连接起来。55--33005.2.2查询优化的一般准则准则三：将投影运算和选择运算同时处理。对同一个关系表的投影运算和选择运算一同处理，减少对关系表的扫描次数。准则四：找出公共的子表达式。只计算一次公共表达式的值。55--33115.2.2查询优化的一般准则——准则五准则五：把某些选择同它前面要执行的笛卡尔积结合起来成为一个新的连接运算。例：查询在北京分支机构工作的员工sstaff.branchNo=branch.branchNo∧branch.city=‘北京’(staff

×

branch)sbranch

.city=‘北京’(staff▷◁

branch)staff.branchNo=branch.branchNo55--33225.2.3关系代数等价变换规则连接、笛卡尔积交换律连接、笛卡尔积结合律投影的串接定律选择的串接定律选择与投影的交换律选择与笛卡尔积的交换律选择与并的交换选择与差运算的交换投影与笛卡尔积的交换10.投影与并的交换55--33335.2.3关系代数等价变换规则1．连接、笛卡尔积交换律设：E1

、E2是关系代数表达式，F是连接运算条件。则：E1

×

E2

≡ E2

×

E1E1

▷◁

E2

≡

E2

▷◁

E1E1

▷◁

E2

≡ E2

▷◁

E1F

F5-34(s

branch.所在城市=‘北京’branch)×(sstaff.职务=‘经理’staff)分支编号所在城市地址邮编工号姓名性别职务月薪分支编号B0001北京北京海淀区青龙桥18号100091SB101赵海洋男经理8000.B0001B0001北京北京海淀区青龙桥18号100091SS201钱光明男经理6000.B0002B0001北京北京海淀区青龙桥18号100091SG401吴德海男经理5500.B0004(sstaff.职务=‘经理’staff)×(s

branch.所在城市=‘北京’branch)工号姓名性别职务月薪分支编号分支编号所在城市地址邮编SB101赵海洋男经理8000.B0001B0001北京北京海淀区青龙桥18号100091SS201钱光明男经理6000.B0002B0001北京北京海淀区青龙桥18号050003SG401吴德海男经理5500.B0004B0001北京北京海淀区青龙桥18号510501例:笛卡尔积交换律实例5.2.3关系代数等价变换规则5-35工号姓名性别职务月薪分支编号分支编号所在城市地址邮编SB101赵海洋男经理8000.B0001B0001北京北京海淀区青龙桥18号100091(sstaff.职务=‘经理’staff)▷◁(s

branch.所在城市=‘北京’branch)staff.分支编号=branch.分支编号(s

branch.所在城市=‘北京’branch)▷◁(sstaff.职务=‘经理’staff)staff.分支编号=branch.分支编号分支编号所在城市地址邮编工号姓名性别职务月薪分支编号B0001北京北京海淀区青龙桥18号100091SB101赵海洋男经理8000.B0001例:连接交换律实例5.2.3关系代数等价变换规则（E1

▷◁

E2）▷◁E3≡E1

▷◁（E2

▷◁

E3

）F1F2F1

F25-365.2.3关系代数等价变换规则2．连接、笛卡尔积结合律设E1

、E2

、E3是关系代数表达式，F1、F2

是连接运算条件。则：（E1

×

E2

）×

E3

≡ E1

×（E2

×

E3

）（E1

▷◁

E2

）▷◁

E3

≡ E1

▷◁（E2

▷◁

E3

）5-375.2.3关系代数等价变换规则3．投影的串接定律设：E是关系代数表达式;Ai(i=1,

2,…,n)，Bj(j=1,

2,…,m)是属性名;{A1

，A2，…，An}是{B1，B2，…，Bm}的子集。πA1,A2,…,An(πB1,B2,…,Bm

(E))

≡πA1,A2,…,An（E）5-38务员B0002理助理B0001理B0004姓名职务所属分支赵海洋经理B0001钱光明经理B0002孙佩霞经理助理B0002李万章业工号姓名性别职务月薪所属分支周全经SB101赵海洋男经理8000.B0001吴德海经SS201钱光明男经理6000.B0002SS212孙佩霞女经理助理5000.B0002SS223李万章男业务员3000.B0002SB112周

全男经理助理6000.B0001SG401吴德海男经理5500.B0004例：投影的串接定律实例例如：π姓名(π姓名，职务，分支编号(Staff))=π姓名(Staff)π姓名，职务，分支编号(Staff)π姓名(Staff)姓名赵海洋钱光明孙佩霞李万章周

全吴德海Staff5.2.3关系代数等价变换规则5-394.选择的串接定律设E是关系代数表达式，F1、F2是选择运算条件。则有：5.2.3关系代数等价变换规则σF1(σF2(E))

≡σF1∧F2

(E)5-40σＦ1(σＦ2(E))≡σＦ1∧F2

(E)实例例如：σ分支编号=’B0001’(σ姓名月薪>5500.

(Staff))工号姓名性别职务月薪所属分支SB101赵海洋男经理8000.B0001SS201钱光明男经理6000.B0002SB112周全男经理助理6000.B0001工号姓名性别职务月薪所属分支SB101赵海洋男经理8000.B0001SB112周全男经理助理6000.B0001σ姓名月薪>5500.

(Staff)σ分支编号=’B0001’

()5.2.3关系代数等价变换规则5-415．选择与投影的交换律设：E是关系代数表达式，F是运算条件且只涉及属性A1，A2，…，An

。则：σＦ(πA1,A2,…,An

(E))≡πA1,A2,…,An(σＦ(E))5.2.3关系代数等价变换规则5-42σ性别=‘男’(π姓名,性别,职务(Staff))π姓名,性别,职务(σ性别=‘男’(Staff))姓名性别职务赵海洋男经理钱光明男经理孙佩霞女经理助理李万章男业务员周全男经理助理吴德海男经理π姓名,性别,职务(Staff))σ性别=‘男’()姓名性别职务赵海洋男经理钱光明男经理李万章男业务员周

全男经理助理吴德海男经理5．选择与投影的交换律——实例5.2.3关系代数等价变换规则5-43π姓名,性别,职务()姓名性别职务赵海洋男经理钱光明男经理李万章男业务员周全男经理助理吴德海男经理σ性别=‘男’(Staff)的结果工号姓名性别职务月薪所属分支SB101赵海洋男经理8000.B0001SS201钱光明男经理6000.B0002SS223李万章男业务员3000.B0002SB112周全男经理助理6000.B0001SG401吴德海男经理5500.B0004π姓名,性别,职务(σ性别=‘男’(Staff))5.2.3关系代数等价变换规则5-445.2.3关系代数等价变换规则6．选择与笛卡尔积的交换律若F中所涉及的属性都是E1

中的属性，则：σＦ(E1

×

E2)

≡σＦ(E1)

×

E2若F=F1∧F2，并且F1只涉及E1

中的属性，F2只涉及E2

中的属性，则：σＦ(E1

×

E2)

≡σＦ1(E1)

×

σＦ2(E2)若F=F1∧F2，并且F1只涉及E1中的属性，F2涉及E1

、E2

两者的属性，则：σＦ(E1

×

E2)

≡σＦ2(σＦ1(E1)

×

E2)5-45例:σ职务=‘业务员’(Staff

×Branch)工号姓名职务所属分支SB101赵海洋经理B0001SS201钱光明经理B0002SS223李万章业务员B0002Staff分支编号城市地址邮编B0001北京北京海淀区青龙桥18号100091B0002石家庄石家庄市北马路90号050003Branch工号姓名职务所属分支分支编号城市地址邮编SB101赵海洋经理B0001B0001北京北京海淀区青龙桥18号100091SB101赵海洋经理B0001B0002石家庄石家庄市北马路90号050003SS201钱光明经理B0002B0001北京北京海淀区青龙桥18号100091SS201钱光明经理B0002B0002石家庄石家庄市北马路90号050003SS223李万章业务员B0002B0001北京北京海淀区青龙桥18号100091SS223李万章业务员B0002B0002石家庄石家庄市北马路90号050003Staff

×Branch工号姓名职务所属分支分支编号城市地址邮编SS223李万章业务员B0002B0001北京北京海淀区青龙桥18号100091SS223李万章业务员B0002B0002石家庄石家庄市北马路90号0500035.2.3关系代数等价变换规则5-46工号姓名职务所属分支SB101赵海洋经理B0001SS201钱光明经理B0002SS223李万章业务员B0002例:σ职务=‘业务员’(Staff

×Branch)Staff分支编号城市地址邮编B0001北京北京海淀区青龙桥18号100091B0002石家庄石家庄市北马路90号050003BranchStaff

×Branch工号姓名职务所属分支分支编号城市地址邮编SS223李万章业务员B0002B0001北京北京海淀区青龙桥18号100091SS223李万章业务员B0002B0002石家庄石家庄市北马路90号0500035.2.3关系代数等价变换规则工号姓名职务所属分支SS223李万章业务员B0002×

Branchσ职务=‘业务员’(Staff)5-475.2.3关系代数等价变换规则7．选择与并的交换设: E＝

E1

∪

E2

，E1

、E2有相同的属性名，则：或:σＦ(E1

∪

E2)≡σＦ(E1)∪σＦ(E2)σＦ(E)≡σＦ(E1)∪σＦ(E2)5-48工号姓名性别所属分支SB101赵海洋男B0001SS201钱光明男B0002SS223李万章男B0002工号姓名性别所属分支SS212孙佩霞女B0002SB112周全男B0001SG401吴德海男B0004工号姓名性别所属分支SB101赵海洋男B0001SS201钱光明男B0002SS223李万章男B0002SS212孙佩霞女B0002SB112周全男B0001SG401吴德海男B0004工号姓名性别所属分支SB101赵海洋男B0001SB112周全男B0001例如：σ所属分支=’B0001’

(Staff1

∪Staff2)Staff=Staff1

∪

Staff2σ所属分支=‘B0001’(Staff)的结果7．选择与并的交换——举例工作人员Staff1

工作人员Staff25.2.3关系代数等价变换规则5-49工号姓名性别所属分支SB101赵海洋男B0001SS201钱光明男B0002SS223李万章男B0002工号姓名性别所属分支SS212孙佩霞女B0002SB112周全男B0001SG401吴德海男B0004σ所属分支=’B0001’

(Staff1)工号姓名性别所属分支SB101赵海洋男B0001SB112周全男B00017．选择与并的交换——举例工作人员Staff1

工作人员Staff25.2.3关系代数等价变换规则σ所属分支=’B0001’

(Staff2)σ所属分支=‘B0001’(Staff1)

∪σ所属分支=’B0001’

(Staff2)工号姓名性别所属分支SB101赵海洋男B0001工号姓名性别所属分支SB112周全男B00015-505.2.3关系代数等价变换规则8．选择与差运算的交换若E1

、E2有相同的属性名，则：

σＦ(E1

-E2)≡σＦ(E1)-σＦ(E2)9．投影与笛卡尔积的交换设:E1

、E2是两个关系表达式，A1，A2，…，An是E1的属性，B1，B2，…，Bm是E2的属性，则：πA1,A2,…,AnB1,B2,…,Bm（E1×E2）≡πA1,A2,…,An（E1）×πB1,B2,…,Bm（E2）5-51工号姓名职务所属分支SB101赵海洋经理B0001SS201钱光明经理B0002SS223李万章业务员B0002Staff分支编号城市地址邮编B0001北京北京海淀区青龙桥18号100091B0002石家庄石家庄市北马路90号050003Branch工号姓名职务所属分支分支编号城市地址邮编SB101赵海洋经理B0001B0001北京北京海淀区青龙桥18号100091SB101赵海洋经理B0001B0002石家庄石家庄市北马路90号050003SS201钱光明经理B0002B0001北京北京海淀区青龙桥18号100091SS201钱光明经理B0002B0002石家庄石家庄市北马路90号050003SS223李万章业务员B0002B0001北京北京海淀区青龙桥18号100091SS223李万章业务员B0002B0002石家庄石家庄市北马路90号050003Staff

×Branchπ工号,姓名,地址,邮编（Staff

×Branch）≡π工号,姓名（Staff）×π地址,邮编（Branch）9．投影与笛卡尔积的交换——举例5.2.3关系代数等价变换规则5-52工号姓名地址邮编SB101赵海洋北京海淀区青龙桥18号100091SB101赵海洋石家庄市北马路90号050003SS201钱光明北京海淀区青龙桥18号100091SS201钱光明石家庄市北马路90号050003SS223李万章北京海淀区青龙桥18号100091SS223李万章石家庄市北马路90号050003π地址,邮编（Branch）工号姓名SB101赵海洋SS201钱光明SS223李万章π工号,姓名（Staff）地址邮编北京海淀区青龙桥18号100091石家庄市北马路90号0500035.2.3关系代数等价变换规则π工号,姓名,地址,邮编（Staff

×Branch）的结果5-5310．投影与并的交换设:

E1

、E2是两个关系表达式，若E1

、E2

有相同的属性名，A1，A2，…，An

是E1

、E2的属性，则：5.2.3关系代数等价变换规则πA1,A2,…,An(E1∪E2)≡πA1,A2,…,An(E1)∪πA1,A2,…,An(E2)5-54工号姓名性别所属分支SB101赵海洋男B0001SS201钱光明男B0002SS223李万章男B0002工号姓名性别所属分支SS212孙佩霞女B0002SB112周全男B0001SG401吴德海男B0004π工号,姓名(Staff1)π工号,姓名(Staff2)工号姓名SB101赵海洋SS201钱光明SS