数据库原理与技术学习教案

1、会计学1数据库原理数据库原理(yunl)与技术与技术第一页，共87页。输出：满足查询条件的数据输出：满足查询条件的数据第1页/共87页第二页，共87页。语法分析与翻译语法分析与翻译关系代数表达式关系代数表达式执行计划执行计划优化器优化器查询语句查询语句执行引擎执行引擎查询结果查询结果有关数据的统计值有关数据的统计值数据数据第2页/共87页第三页，共87页。第3页/共87页第四页，共87页。第4页/共87页第五页，共87页。优化器能够对多种实现策略逐一优化器能够对多种实现策略逐一进行考虑进行考虑优化器集中了最优秀的程序员的优化器集中了最优秀的程序员的智慧和经验智慧和经验第5页/共87页第六页，共

2、87页。第6页/共87页第七页，共87页。一文件中，则：一文件中，则： br = nr / fr n第7页/共87页第八页，共87页。一个等值条件的平均元组数。一个等值条件的平均元组数。n若若A为为r的码属性，则的码属性，则SC(A,r) 1n若若A为非码属性，并假定为非码属性，并假定V(A,r)个不同的值在元组上均匀分布，个不同的值在元组上均匀分布，则则SC(A,r) (nr / V(A,r)。n说明：说明：V(A,r)与与SC(A,r)中的中的A可以可以是属性组。是属性组。n第8页/共87页第九页，共87页。索引叶层的块数。索引叶层的块数。n对于散列索引，对于散列索引，Lbi就是索引中的块

3、就是索引中的块数。数。n算法算法A的代价估计记为的代价估计记为EA。第9页/共87页第十页，共87页。第10页/共87页第十一页，共87页。 执行代价不同执行代价不同第11页/共87页第十二页，共87页。第12页/共87页第十三页，共87页。n适用于任何选择条件。适用于任何选择条件。n第13页/共87页第十四页，共87页。条件的一系列元组。条件的一系列元组。第14页/共87页第十五页，共87页。较条件）较条件）利用利用(lyng)辅助索引，非等值比辅助索引，非等值比较：较： E = HTi + LBi /2 + nr /2 第15页/共87页第十六页，共87页。第16页/共87页第十七页，共8

4、7页。过程需要使用外存。过程需要使用外存。第17页/共87页第十八页，共87页。nn第二阶段，对已排序子表进行第二阶段，对已排序子表进行归并（可能归并（可能(knng)需进行若干需进行若干趟）。趟）。第18页/共87页第十九页，共87页。第19页/共87页第二十页，共87页。 then 读入Ri的下一块到相应的缓冲页； if 第M个缓冲页满 then 将第M个缓冲页写到磁盘，并清空该缓冲页； until 所有的缓冲页均空将下M-1个已排序子表的每一个的第一块读入内存，归并。 .第20页/共87页第二十一页，共87页。 初始关系 归并段文件(wnjin) 归并段文件(wnjin) 排序结果 第一

5、阶段 第二阶段 第二阶段 创建归并段文件(wnjin) 第一趟归并 第二趟归并第21页/共87页第二十二页，共87页。第22页/共87页第二十三页，共87页。第23页/共87页第二十四页，共87页。或或 ns *( nr /V(A,r)说明说明(shumng)： 当当V(A,s)与与V(A,r)不同时，取两个估计值中较小者。不同时，取两个估计值中较小者。若两个关系中的元组在连接属性上的取值能匹配上的很少时，上述估计值若两个关系中的元组在连接属性上的取值能匹配上的很少时，上述估计值太高。但实际上这种情况很少发生。太高。但实际上这种情况很少发生。第24页/共87页第二十五页，共87页。第25页/共

6、87页第二十六页，共87页。n endn end第26页/共87页第二十七页，共87页。n最好情况（内层关系最好情况（内层关系s能完全放能完全放在内存中）：在内存中）：n bs + br 第27页/共87页第二十八页，共87页。n测 试 元测 试 元组对组对(tr,ts)是否是否(sh fu)满足连接条满足连接条件件n如 果 满如 果 满足，把足，把tr ts加到结果中加到结果中n end n end n endn end第28页/共87页第二十九页，共87页。在内存中）：在内存中）：n bs + br 第29页/共87页第三十页，共87页。第30页/共87页第三十一页，共87页。(suyn)

7、取到相应的取到相应的tsn把把tr ts加到结果中加到结果中n end n endn第31页/共87页第三十二页，共87页。连接方法。连接方法。对关系S使用连接(linji)条件利用索引进行选择操作的代价第32页/共87页第三十三页，共87页。a3b1d8d13f7m5q6aAaGcLdNmB r sa1a2a1a3在归并连接中使用的已排序关系在归并连接中使用的已排序关系rs第33页/共87页第三十四页，共87页。在连接属性上具有在连接属性上具有(jyu)(jyu)相相同值的同值的S S元组被加入到了元组被加入到了SsSs中中。PsPs指向在连接属性上具有指向在连接属性上具有(jyu)(jyu

8、)另一个值的另一个值的S S元组。元组。第34页/共87页第三十五页，共87页。在在r r中跳过中不能与中跳过中不能与SsSs中的中的s s元组匹配元组匹配(ppi)(ppi)的的r r元组。元组。在在r中前进，将中前进，将r元组与元组与Ss中的每中的每个个s元组连接，直元组连接，直至至r元组中的连元组中的连接属性值大于接属性值大于s元组的连接属性值元组的连接属性值。 第35页/共87页第三十六页，共87页。a3b1d8d13f7m5q6aAaGcLdNmBprpsa1a2a1a3在归并连接中使用的已排序关系在归并连接中使用的已排序关系rs第36页/共87页第三十七页，共87页。第37页/共8

9、7页第三十八页，共87页。进行进行(jnxng)“(jnxng)“连接连接”，（结，（结果的果的“元组元组”为为r r元组与元组与s s元组地址）元组地址）n按按s s元组地址排序，元组地址排序，n访问访问s s的块，完成连接。的块，完成连接。第38页/共87页第三十九页，共87页。中进行索引嵌套循环连接（散列中进行索引嵌套循环连接（散列索引）。索引）。第39页/共87页第四十页，共87页。引，引，n再对同一划分中的再对同一划分中的r r元组查元组查找散列索引，同时进行连接。找散列索引，同时进行连接。n第40页/共87页第四十一页，共87页。rs关系关系(gun x)r 的划分的划分关系关系s

10、 的划分的划分0123401234第41页/共87页第四十二页，共87页。 begin i := h(trJoinAttrs)； Hri := Hri tr； end第42页/共87页第四十三页，共87页。构造用输入(shr)关系查找用输入关系第43页/共87页第四十四页，共87页。n当当bs M2bs M2时，关系的划分不可能时，关系的划分不可能一趟完成，需要递归划分。一趟完成，需要递归划分。n当对于某个当对于某个i i， Hsi Hsi中的元组数大中的元组数大于内存容量时，需要进行溢出处理，于内存容量时，需要进行溢出处理，想办法使想办法使HsiHsi变小。变小。n改进：混合散列连接改进：混

11、合散列连接n当当M 2 bsM 2 bs时，充分利用内时，充分利用内存空间，减少磁盘存空间，减少磁盘I/OI/O的方法。的方法。前提：读每个关系一遍就能完成散列划分，构造用输入关系的每一个分划都能完全(wnqun)放入内存。第44页/共87页第四十五页，共87页。n = r | r | n s n s第45页/共87页第四十六页，共87页。第46页/共87页第四十七页，共87页。第47页/共87页第四十八页，共87页。第48页/共87页第四十九页，共87页。第49页/共87页第五十页，共87页。第50页/共87页第五十一页，共87页。customer_name balance 1000 (br

12、anch |customer-name(branch-city=”Brooklyn”balance1000 (branch |customer-name(branch_city=”Brooklyn”balance1000 (branch | customer-name(branch-city=”Brooklyn” (branch) |1000 (account) |customer-name(account-number(branch-city=”Brooklyn”(branch) |1000 (account) | depositor) 第68页/共87页第六十九页，共87页。第69页/共8

13、7页第七十页，共87页。各个运算之间的相互作用。各个运算之间的相互作用。第70页/共87页第七十一页，共87页。第71页/共87页第七十二页，共87页。采用启发式方法来减少需考虑采用启发式方法来减少需考虑的表达式的数目。的表达式的数目。第72页/共87页第七十三页，共87页。r1r2r3r4r5左深连接树r1r2r3r4r5非左深连接树第73页/共87页第七十四页，共87页。最小的方法所用的代价比先前已检最小的方法所用的代价比先前已检查过的整个表达式的最小代价执行查过的整个表达式的最小代价执行计划所需代价还大，则没有必要对计划所需代价还大，则没有必要对包含该子表达式的任何完整表达式包含该子表达

14、式的任何完整表达式进行检查。进行检查。第74页/共87页第七十五页，共87页。第75页/共87页第七十六页，共87页。查询树，使得具有限制比较严格的选查询树，使得具有限制比较严格的选择运算的叶结点关系首先执行。择运算的叶结点关系首先执行。4.将跟有选择条件的笛卡尔积运算替换将跟有选择条件的笛卡尔积运算替换成连接运算。成连接运算。5.将投影属性加以分解并在查询树上尽将投影属性加以分解并在查询树上尽可能往下推。必要时可以引入新的投可能往下推。必要时可以引入新的投影运算。影运算。6.识别那些识别那些(nxi)可用流水方式执行其可用流水方式执行其运算的子树，并采用流水线方法执行运算的子树，并采用流水线方法执行之。之。第76页/共87页第七十七页，共87页。SQL概念上按以下方式执行查询：计算外层查询的from子句(z j)中的关系的笛卡尔积，然后对该笛卡尔积的每个元组用位于where子句(z j)中的谓词进行测试。本例中，即测试子查询运算结果是否为空。第77页