五门基础或专业课程的教学2016数据库系统原理db-chapter

数据库系统原理主讲：杨艳2023/2/19HD-ITR2第三篇实现篇2023/2/19HD-ITR3实现篇第八章物理存储结构第九章数据库管理系统的数据字典第十章关系代数操作的实现算法第十一章查询优化技术第十二章事务处理技术之一：并发控制技术第十三章事务处理技术之二：数据库恢复技术第十四章其他事务处理技术第十章关系代数操作的实现算法2023/2/19HD-ITR410.1查询处理的过程10.2选择操作的实现算法10.3笛卡儿积的实现算法10.4连接操作的实现算法10.5投影操作的实现算法10.6集合的并、交、差的实现算法第十章关系代数操作的实现算法10.1查询处理的过程2023/2/19HD-ITR5查询：由高级查询语言（如SQL）表示的对数据库的一个或一组操作。查询处理的步骤：扫描和语法分析查询优化查询代码生成查询执行10.1查询处理的过程2023/2/19HD-ITR6查询处理流程图和各步骤所产生的结果10.1查询处理的过程2023/2/19HD-ITR7关系数据库系统的查询处理包括两个方面：实现各种关系代数操作的算法查询优化产生具有较高效率的查询执行计划，不一定是最优的执行计划。查询优化并不是所有的数据库系统都能做到。过程性语言：查询优化的工作由用户来做说明性语言：系统来做10.1查询处理的过程2023/2/19HD-ITR8设每个关系存储在一个文件中，每个文件仅存储一个关系。参数说明：TR：关系Ｒ中的元组数。BR：关系Ｒ的磁盘块数。M：主存缓冲区的块数(每块的容量等于一个磁盘块的容量)。IR：关系Ｒ的每个元组的字节数。ｂ：每个磁盘块的字节数。10.1查询处理的过程2023/2/19HD-ITR910.1查询处理的过程10.2选择操作的实现算法10.3笛卡儿积的实现算法10.4连接操作的实现算法10.5投影操作的实现算法10.6集合的并、交、差的实现算法第十章关系代数操作的实现算法10.2选择操作的实现算法2023/2/19HD-ITR10使用SQL语言，选择操作表示如下：SELECT*FROMRWHEREC1ANDC2ORC3...，选择条件可以是简单条件：仅包含关系R的一个属性的条件也可以是复合条件：由简单条件经AND、OR、NOT等逻辑运算符连接而成的条件。10.2选择操作的实现算法2023/2/19HD-ITR11具有简单选择条件的选择操作实现算法10.2选择操作的实现算法1．线性搜索算法2．二元或插值搜索算法顺序地读取被操作关系的每个元组，测试该元组是否满足选择条件，如果满足，则作为一个结果元组输出。选择条件是在某个属性上的相等比较并且操作关系已经按该属性排序；如果操作关系具有N个元组，二元搜索需要O(log(N))时间完成选择操作，插值搜索需要O(log(log(N)))时间完成选择操作。2023/2/19HD-ITR12具有简单选择条件的选择操作实现算法10.2选择操作的实现算法3、索引扫描算法主索引辅助索引聚集索引Hash文件B树2023/2/19HD-ITR131．合取选择算法如果合取条件中存在一个简单条件Ｃ，Ｃ所涉及的属性上定义有某种存取方法，而且这种存取方法适应于上述3个算法之一，则使用相应算法搜索操作关系，选择满足Ｃ的元组，并检验是否满足其他条件，如果满足，作为结果元组。10.2选择操作的实现算法具有复合选择条件的选择操作实现算法称由一组简单条件经逻辑运算符AND连接在一起的复合条件为合取条件。2．使用复合索引的合取选择算法如果合取条件是定义在一组属性上的相等比较，而且存在一个由这组属性构成的复合索引，则使用这个复合索引完成选择操作。2023/2/19HD-ITR143．使用元组指针交集的合取选择算法如果合取条件是定义在一组属性上的相等比较，每个属性上都定义有一个辅助索引，则首先使用每个索引形成满足对应条件的元组指针集合；然后计算这些指针集合的交集；最后使用交集中的指针产生结果元组集合。这个方法也可以用于合取条件中只有部分属性具有辅助索引的情况在这种情况下，首先使用指针交集读取满足部分简单条件的元组，然后进一步地检验是否满足其他条件。10.2选择操作的实现算法具有复合选择条件的选择操作实现算法称由一组简单条件经逻辑运算符AND连接在一起的复合条件为合取条件。2023/2/19HD-ITR1510.1查询处理的过程10.2选择操作的实现算法10.3笛卡儿积的实现算法10.4连接操作的实现算法10.5投影操作的实现算法10.6集合的并、交、差的实现算法第十章关系代数操作的实现算法10.3笛卡儿积的实现算法2023/2/19HD-ITR16参数说明：TR：关系Ｒ中的元组数。BR：关系Ｒ的磁盘块数。M：主存缓冲区的块数(每块的容量等于一个磁盘块的容量)。IR：关系Ｒ的每个元组的字节数。ｂ：每个磁盘块的字节数。10.3笛卡儿积的实现算法R×S的每个元组的字节数是R×S的磁盘块数是BR×S＝

IR＋ISTRTS(IR＋IS)/ｂ2023/2/19HD-ITR17简单算法（嵌套循环算法）10.3笛卡儿积的实现算法BR＋BR×BS＋BR×SFORR中每个元组rDO

FOR

S中每个元组sDO产生元组(rs)，存入结果关系；

ENDFOR；ENDFOR算法的磁盘存取块数：R和S在算法中的位置可以调换把小关系放在外层循环可以节省时间。2023/2/19HD-ITR18主存算法10.3笛卡儿积的实现算法BR＋BS＋BR×S

读入R和S；

FOR主存中R的每个元组rDO

FOR主存中S的每个元组sDO产生元组(rs)，存入结果关系；

ENDFOR;

ENDFOR算法的磁盘存取块数：如果M≥BS＋BR，可以首先把R和S读入主存，然后在主存中产生R×S。2023/2/19HD-ITR19

读入S到SB；WHILE

R中仍有元组待处理DO读R的元组到RB； /*每次读的元组数不超过RB的容量*/

FOR

RB中每个R元组rDO

FOR

SB中每个S元组sDO产生元组(rs)，存入结果关系；

ENDFOR;

ENDFOR;

ENDWHILE

半主存算法10.3笛卡儿积的实现算法算法的磁盘存取块数：BR＋BS＋BR×S

如果BR≥BS，BS＜M，可以首先把S读入主存，并保留至少一块主存作为R的缓冲区。设SB是存储S的主存区，RB是R的缓冲区，半主存算法如下：2023/2/19HD-ITR20

FOR

i＝1TO

BS/(M－1)DO读S的第i个子集合到SB；FOR

j＝1TO

BRDO读R的第j块到RB；

FOR

RB中每个R元组r

DO

FORSB中每个S元组s

DO产生元组(rs),存入结果关系；

ENDFOR;

ENDFOR;

ENDFOR;

ENDFOR大关系算法10.3笛卡儿积的实现算法算法的磁盘存取块数：BR(BS/(M－1))＋BS＋BR×S

如果M≤BR，M≤BS，则R和S都不能一次读入主存。设BS≤BR，则可把关系S划分为BS／(Ｍ－1)个子集合，每个子集合具有M－1块。令SB是容量为M－1块的S的主存缓冲区，RB是容量为1块的R的主存缓冲区。大关系算法如下：2023/2/19HD-ITR2110.1查询处理的过程10.2选择操作的实现算法10.3笛卡儿积的实现算法10.4连接操作的实现算法10.5投影操作的实现算法10.6集合的并、交、差的实现算法第十章关系代数操作的实现算法10.4连接操作的实现算法2023/2/19HD-ITR22使用SQL语言，关系R和S的连接操作表示为：SELECTR.*,S.*FROMR,SWHERER.AθS.B其中，θ是算术比较符。这种连接操作简称为θ连接。10.4连接操作的实现算法2023/2/19HD-ITR23

FOR

i＝1TO

BS/(M－1)DO读S的第i个子集合到SB；FOR

j＝1TO

BRDO读R的第j块到RB；

FOR

RB中每个元组r

DO

FORSB中每个S元组s

DOIF

r.Aθs.BTHEN(rs)存入结果关系；

ENDFOR;

ENDFOR;

ENDFOR;

ENDFOR修改笛卡儿积的大关系算法来实现θ连接。10.4连接操作的实现算法算法的磁盘存取块数：BR(BS/(Ｍ－１))＋BS＋B

设M≤BR，Ｍ≤BS，BS≤BR。把S划分为BS/(M－1)个子集合，每个子集合具有M－1块。令SB是容量为M－1块的S的主存缓冲区，RB是容量为1块的R的主存缓冲区。θ连接的大关系算法如下：2023/2/19HD-ITR2410.4连接操作的实现算法等值连接和自然连接是应用最多的连接操作。自然连接与等值连接无本质区别。下文主要讨论自然连接。2023/2/19HD-ITR25输入：关系R(A1,...,Ai,...,An)，S(B1,...,Bj,...,Bm)，连接条件R.Ai＝S.Bj。输出：R与S的连接T。方法：

FOR每个t∈R

DO

FOR每个s∈S

DO

IF

t[Ai]＝s[Bj]THEN(ts)写入T；ENDIF;

ENDFOR;

ENDFOR循环嵌套算法（Nest-LoopJoin）10.4连接操作的实现算法算法的磁盘存取块数：BR＋BRBS＋U

2023/2/19HD-ITR2610.4连接操作的实现算法排序合并算法（Sort-MergeJoin）如果关系R和S的元组已经在连接属性R.Ai和S.Bj上物理地排序设R.Ai和S.Bj中至少有一个是键属性按照排序顺序扫描R和S；查找在R.Ai和S.Bj上具有相同值的R和S的元组，进行连接。磁盘存取块数：BR＋BS＋U。如果R.Ai和S.Bj都不是键属性上述算法做一点小的修改。如果关系R和S的元组都未排序使用下文的Sort-Merge连接算法。用X(i)表示已排序关系X的第i个元组。2023/2/19HD-ITR27输入：关系R(A1,...,Ai,...,An)，S(B1,...,Bj,...,Bm)，连接条件R.Ai＝S.Bj。输出：R与S的连接T。方法：(1)按属性R.Ai值排序R；(2)按属性S.Bj值排序S；(3)扫描R和S一遍，形成T={R(k)S(m)|R(k)[Ai]=S(m)[Bj]}。排序合并算法（Sort-MergeJoin）10.4连接操作的实现算法算法的磁盘存取块数：O(BRlogMBR+BSlogMBS+BR+BS+U)2023/2/19HD-ITR2810.4连接操作的实现算法Hash连接算法(HashJoin)第一阶段：扫描R和S，使用定义在连接属性上的Hash函数把R和S的元组分别构造成Hash文件HR和HS。第二阶段：对于HR和HS的每对对应Hash桶，考察其中R和S的元组在连接属性上的值，产生R和S的连接结果。2023/2/19HD-ITR29输入：关系R(A1,...,Ai,...,An)，S(B1,...,Bj,...,Bm)，连接条件R.Ai＝S.Bj，HASH函数H(X),值域为{1,2,…,N}。输出：R与S的连接T。方法：FOR每个t∈RDOt写入HR的第H(t[Ai])个HASH桶；

ENDFOR；FOR每个s∈SDOs写入HS的第H(s[Bj])个HASH桶；

ENDFOR;FORL=1TONDO

连接HR和HS的第L个HASH桶，结果写入T;ENDFORHash连接算法(HashJoin)10.4连接操作的实现算法算法的磁盘存取块数：O(BR+BS+NCOST(B1,B2)+U)2023/2/19HD-ITR30

FORR的每一个数据块BLOCKDOFORBLOCK中的每个元组tDO

用t[Ai]搜索IS,找到所有与t[Ai]匹配的索引值对应的S元组指针，送到P中;FORP中每个指针p所对应的S元组sDO(ts)写入连接结果T;ENDFOR;ENDFOR;ENDFOR索引连接算法10.4连接操作的实现算法仍然考虑关系R(A1,...,Ai,...,An)和S(B1,...,Bj,...,Bm)的连接，R.Ai=S.Bj是连接条件。若S在属性Bj上具有聚集索引，索引文件名为IS：

2023/2/19HD-ITR3110.4连接操作的实现算法索引连接算法设I是S.Bj的连接值域大小，S在连接值域上均匀分布,R.Ai的连接值域是S.Bj的连接值域的子集合对于R的每个元组，算法平均需要读S的BS/I个数据块，总的需要读取S的TRBS/I个数据块。如果不计索引文件IS的存取数据块数，算法需要存取的数据块数是：BR+(TRBS)/I+U，其中U是连接结果T的数据块数。2023/2/19HD-ITR32

搜索IXS形成连接属性的连接值域Y以及Y中每个值所对应的S元组指针集合PS;FORY中每个值bDO

用b搜索IXR,找到所有与b匹配的R元组的指针送PR;FORPS中每个与b对应的S元组指针所指的S元组sDOFORPR每个指针所指的R元组rDO(rs)写入连接结果T;ENDFOR;ENDFOR;ENDFOR索引连接算法10.4连接操作的实现算法仍然考虑关系R(A1,...,Ai,...,An)和S(B1,...,Bj,...,Bm)的连接，R.Ai=S.Bj是连接条件。若R和S都在连接属性上具有聚集索引；设IXR和IXS分别是R和S在R.Ai和S.Bj上的索引文件；IXS中的元素数小于IXR中的元素数。

2023/2/19HD-ITR3310.4连接操作的实现算法索引连接算法设I是S.Bj的连接值域的大小；J是R.Ai的连接值域的大小；S.Bj的连接值域是R.Ai的连接值域的子集合；S和R在连接值域上均匀分布。最外层循环的次数是I；在每次循环中，R的平均存取块数是O(BR/J)，S的平均存取块数是O(BS/I)。于是，如果不计索引文件的存取数据块数，算法需要存取的数据块数至多是O(I×(BR/J+BS/I)+U),其中，U是连接结果T的数据块数。2023/2/19HD-ITR3410.4连接操作的实现算法连接操作结果的估计连接操作结果的大小U在分析连接操作算法的复杂性和查询优化处理中具有重要的作用。估计连接操作结果的大小。2023/2/19HD-ITR3510.1查询处理的过程10.2选择操作的实现算法10.3笛卡儿积的实现算法10.4连接操作的实现算法10.5投影操作的实现算法10.6集合的并、交、差的实现算法第十章关系代数操作的实现算法10.5投影操作的实现算法2023/2/19HD-ITR3610.5投影操作的实现算法设A1,...,Ak(R)是关系R上的投影操作。如果投影属性表{A1,...,Ak}中包括R的键存取R的所有元组一次即可完成；操作的结果具有与R同样多的元组，只是每个元组仅包括属性A1,A2,…,Ak的值。如果投影属性表中不包含R的键需要删除操作结果中的重复元组可以利用排序算法来实现投影操作2023/2/19HD-ITR37输入:具有n个元组的关系R。输出:R的投影T=A1,...,Ak(R)。方法：

FORR中每个元组rDOr[A1,...,Ak]写入TMP;ENDFOR;IF{A1,...,Ak}中包含R的键属性THENT:=TMP;结束；

ELSE排序TMP;i=1;j=2;WHILE(i≤n)DO

写TMP(i)到T;WHILE(TMP(i)=TMP(j))DOj=j+1;ENDWHILE;i=j;j=j+1;ENDWHILE;ENDIF利用排序实现投影操作的算法10.5投影操作的实现算法2023/2/19HD-ITR38利用排序实现投影操作的算法设L是元组r[A1,...,Ak]的字节数；b是一个数据块所包含的字节数。如果{A1,...,Ak}包含R的候选键算法需要存取的磁盘块数是O(BR+nL/b)如果{A1,...,Ak}不包含R的候选键算法需要存取的磁盘块数至多为

O(BR+nL/blogM(nL/b)+nL/b)10.5投影操作的实现算法2023/2/19HD-ITR3910.1查询处理的过程10.2选择操作的实现算法10.3笛卡儿积的实现算法10.4连接操作的实现算法10.5投影操作的实现算法10.6集合的并、交、差的实现算法第十章关系代数操作的实现算法10.6集合的并、交、差的实现算法2023/2/19HD-ITR4010.6集合的并、交、差的实现算法实现集合的并、交、差操作要求操作关系具有相同的属性集合，并且属性的排列顺序必须也相同。实现这些操作的常用算法首先利用排序算法在相同的键属性上排序两个操作关系；然后扫描这两个排序后的关系，完成并、交或差操作。2023/2/19HD-ITR4110.6集合的并、交、差的实现算法并操作

输入:关系R和S,R具有n个元组，S具有m个元组，K是R和S的键。输出:T=R∪S。

方法:(1)按照键K值排序R和S;(2)i:=1;j:=1;(3)WHILE(i≤n)AND(j≤m)DO(4)IFR(i)[K]>S(j)[K]THEN写S(j)到T;j:=j+1;(5)ELSEIFR(i)[K]<S(j)[K]THEN写R(i)到T;i:=i+1;(6)ELSE写R(i)到T;i:=i+1;j:=j+1;(7)ENDIF;(8)ENDIF;(9)ENDWHILE;(10)IFi≤nTHENFORk=iTOnDO写R(k)到T;ENDIF;(11)IFj≤mTHENFORk=jTOmDO写S(k)到T;ENDIF。算法的磁盘存取块数：O(BRlogM(BR)