数据库系统习题评讲期末复习

1、数据库系统习题评讲 & 期末复习1 数据库模型和数据库开发过程数据库模型和数据库开发过程2 需求分析需求分析 数据流图3 概念模型设计概念模型设计 E-R模型4 逻辑模型设计逻辑模型设计 关系模式及其优化5 数据库实现数据库实现 关系代数、SQL6 数据物理存储数据物理存储7 索引与散列索引与散列8 查询处理与优化查询处理与优化9 事物机制事物机制10 并发控制并发控制11 恢复系统恢复系统知识框架6 数据物理存储数据物理存储7 索引与散列索引与散列8 查询处理与优化查询处理与优化9 事物机制事物机制10 并发控制并发控制11 恢复系统恢复系统知识框架10.4 考虑从图10-6的文件中

2、删除记录5。比较下列实现删除的技术的相对优点：a. 移动记录6到记录5所占用的空间，然后移动记录7到记录6所占用的空间。b. 移动记录7到记录5所占用的空间。c. 标记记录5被删除，不移动任何记录。数据存储33456GoldPhysics8700045565KatzComp.Sci.7500058583CalifieriHistory62000记录5记录6记录710.4 考虑从图10-6的文件中删除记录5。比较下列实现删除的技术的相对优点：a. 移动记录移动记录6到记录到记录5所占用的空间，然后移动记录所占用的空间，然后移动记录7到记录到记录6所占用的空间。所占用的空间。移动了最多的记录，进行

3、了多次数据存取（access）b. 移动记录移动记录7到记录到记录5所占用的空间。所占用的空间。移动了少量记录，但是破坏了文件内数据的排序c. 标记记录标记记录5被删除，不移动任何记录。被删除，不移动任何记录。没有移动任何数据，但是需要额外的开销来记录文件中空闲空间。这种方式会导致文件中出现很多空洞（holes），长此以往会降低存储效率和查询性能。数据存储674764567467410.18 在顺序文件组织中，为什么即使当前只有一条溢出记录，也要使用一个溢出块？数据存储10.18 在顺序文件组织中，为什么即使当前只有一条溢出记录，也要使用一个溢出块？由于文件被组织成物理块的形式，当数据块放满时

4、，只能再申请一个溢出块存放这个记录。数据存储33456GoldPhysics8700045565KatzComp.Sci. 7500058583CalifieriHistory6200050000AMusic60000搜索码搜索码链表溢出块文件中记录的组织：堆文件组织堆文件组织：一条记录可以放在文件中的任何地方，记录没有顺序。顺序文件组织顺序文件组织：记录根据“搜索码”的值顺序存储。搜索码是任何一个属性或者属性的集合。散列文件组织散列文件组织：在每条记录的某个属性上计算一个散列函数，来确定记录放到文件的哪个块中。1 数据库模型和数据库开发过程数据库模型和数据库开发过程2 需求分析需求分析 数据

5、流图3 概念模型设计概念模型设计 E-R模型4 逻辑模型设计逻辑模型设计 关系模式及其优化5 数据库实现数据库实现 关系代数、SQL6 数据物理存储数据物理存储7 索引与散列索引与散列8 查询处理与优化查询处理与优化9 事物机制事物机制10 并发控制并发控制11 恢复系统恢复系统知识框架11.3 用下面的关键码值集合建立一个B+树（2 , 3 , 5 , 7 , 11 , 17 , 19 , 23 , 29 , 31）假设树初始为空，值按上升顺序加入。根据一个结点所能容纳指针数的下列情况分别构造B+树。a. 4b. 6c. 8索引与散列search-key valueB+树索引搜索码值指针B+

6、树索引235（2 , 3 , 5 , 7 , 11 , 17 , 19 , 23 , 29 , 31）2357523575111117空的结点按照B+树的准则插入数据结点满，创建新的结点（2 , 3 , 5 , 7 , 11 , 17 , 19 , 23 , 29 , 31）索引与散列11.17 对习题11.3中的每一棵B+树，给出下列查询中涉及的步骤：a. 找出搜索码值为11的记录索引与散列B+树索引Find record with search-key value V. （搜索算法）1.C=root2. While C is not a leaf node 1） Let i be leas

7、t value s.t.满足 V Ki. 2） If no such exists, set C = last non-null pointer in C 3） Else if (V = Ki ) Set C = Pi +1 else set C = Pi 取右方指针 取左方指针3. Let i be least value s.t. Ki = V (in C)4. If there is such a value i, follow pointer Pi to the desired record.5. Else no record with search-key value k exist

8、s.to the desired record11.17 对习题11.3中的每一棵B+树，给出下列查询中涉及的步骤：a. 找出搜索码值为11的记录索引与散列11.6 假设我们在一个文件上使用可扩充散列，该文件所含记录的搜索码值如下：2、3、5、7、11、17、19、23、29、31如果散列函数为h(x)=x mod 8，且每个桶可以容纳3条记录。给出此文件的可扩充散列结构。索引与散列可扩充散列，与静态散列对比，是一种动态散列的方式为桶引入了一个间接层，即用一个指向块的指针数组来表示桶，而不是用数据块本身组成的数组来表示桶。索引与散列h(x)的前的前i位位共同的散列共同的散列前缀长度前缀长度文件

9、所含记录的搜索码值：2、3、5、7、11、17、19、23、29、31散列函数为h(x)=x mod 8，且每个桶可以容纳3条记录索引与散列搜索码值2357111719232931h(x)2357313757h(x)二进制0100111011110110010111111011110112(010)3(011)11(011)5(101)7(111)1100011011217(001)5(101)7(111)122(010)3(011)11(011)2桶分裂成两个前缀位数+117(001)插入搜索码值17索引与散列000001010011100101110111317(001)23(011)11

10、(011)19(011)35(101)7(111)12(010)3搜索码值1719232931h(x)13757h(x)二进制001011111101111插入搜索码值19可扩充散列结果11.20 在散列文件组织中导致桶溢出的原因是什么？如何减少桶溢出的发生？索引与散列11.20 在散列文件组织中导致桶溢出的原因是什么？如何减少桶溢出的发生？如果桶没有足够的空间，就会发生桶溢出。桶溢出发生的几个原因：桶不足：桶数目的选择必须满足n总记录数N/每个桶的容量f偏斜：由于多个记录可能具有相同的搜索码，或者所选的散列函数造成搜索码分布不均，导致某些桶分配到的记录比其他桶多。即使其他桶有空间，某个桶仍有

11、可能溢出。解决：桶的数目选为(N/f)*(1+d)，d常取0.2，即大约20%的空间是空的。溢出桶索引与散列桶1溢出桶1溢出桶2桶01 数据库模型和数据库开发过程数据库模型和数据库开发过程2 需求分析需求分析 数据流图3 概念模型设计概念模型设计 E-R模型4 逻辑模型设计逻辑模型设计 关系模式及其优化5 数据库实现数据库实现 关系代数、SQL6 数据物理存储数据物理存储7 索引与散列索引与散列8 查询处理与优化查询处理与优化9 事物机制事物机制10 并发控制并发控制11 恢复系统恢复系统知识框架12.2 考虑图12-13中银行数据库的例子，其中主码以下划线标出。考虑下面的SQL语句：sele

12、ct T.branch_namefrom branch T, branch Swhere T.assets S.assets and S.branch_city = “Brooklyn”写出一个与此等价的、高效的关系代数表达式，并论证你的选择。查询处理12.2 考虑图12-13中银行数据库的例子，其中主码以下划线标出。考虑下面的SQL语句：select T.branch_namefrom branch T, branch Swhere T.assets S.assets and S.branch_city = “Brooklyn”写出一个与此等价的、高效的关系代数表达式，并论证你的选择。查询优

13、化一般规则：尽量减少中间结果选择连接次序尽早执行选择和投影运算查询处理select T.branch_namefrom branch T, branch Swhere T.assets S.assets and S.branch_city = “Brooklyn”查询处理 T.branch_name T.assetsS.assets S.branch_city = “Brooklyn”branch Tbranch S T.branch_name branch_name,assets assets S.branch_city = “Brooklyn”branch Tbranch ST.asset

14、sS.assets查询处理12.3 设关系r1(A,B,C)，r2(C,D,E)有如下特性：r1有20000个元组，r2有45000个元组，一块中可容纳25个r1元组或者30个r2元组。估计使用以下连接策略计算r1 r2需几次块传输和磁盘搜索。a.嵌套循环连接b.块嵌套循环连接r1需要20000/25=800块，r2需要45000/30=1500块。连接r1 r2，n是r中的元组数，b是r中元组的磁盘块数a. 对于嵌套循环连接，需n1*b2+b1次块传输，n1+b1次磁盘搜索b. 对于块嵌套循环连接，需b1*b2+b1次块传输，2*b1次磁盘搜索假设r1是外循环：a. 20000*1500+8

15、00=30000800次块传输，20000+800=20800次磁盘搜索b. 800*1500+800=1200800次块传输，2 *800=1600次磁盘搜索查询处理连接r1 r2，n是r中的元组数，b是r中元组的磁盘块数a. 对于嵌套循环连接嵌套循环连接，需n1*b2+b1次块传输，n1+b1次磁盘搜索b. 对于块嵌套循环连接块嵌套循环连接，需b1*b2+b1次块传输， 2*b1次磁盘搜索元组0元组1元组2元组3元组n1元组0元组1元组0元组1元组2元组3元组n1元组0元组1元组2元组3块0块0块1块0块1块0块1块0块0块1磁盘磁盘内存内存块对块0块1块b1n1块0块1块b2块传输：r1

16、需b1次，r2需n1*b2次磁盘搜索：r1需b1次，r2需n1*1次块传输：r1需b1次，r2需b1*b2次磁盘搜索：r1需b1次，r2需b1*1次嵌套循环连接块嵌套循环连接b1b212.6 考虑12-13的银行数据库，其中主码用下划线标出。假设关系branch在branch_city属性上有B+树索引，此外别无其他索引。列出处理下列包含取反运算的选择操作的不同的方法。a. (branch_city “Brooklyn”) (branch)查询处理12.6 考虑12-13的银行数据库，其中主码用下划线标出。假设关系branch在branch_city属性上有B+树索引，此外别无其他索引。列出处

17、理下列包含取反运算的选择操作的不同的方法。a. (branch_city =“Brooklyn”的所有元组。13.6 假设关系department在building属性上有B+树索引，此外别无其他索引。处理下列包含否定条件的选择操作的最佳方法是什么？ a. (building 将R分解为R1(B, D)和R2(A, B, C, E)R1上的函数依赖F1=B D，满足BCNFR2上的函数依赖F2=A BC, E AA BC中A不是R2的超码，不满足BCNF= 将R2分解为R3(A, B, C)和R4(A, E)R3上的函数依赖F3=A BC ，满足BCNFR2上的函数依赖F4=E A ，满足BC

18、NFR的BCNF分解为：(B,D) (A,B,C) (A,E)BCNF & 3NF8.19 给出模式R的一个BCNF分解分解和3NF分解。R=(A,B,C,D,E)函数依赖集F：A BCCD EB DE AABC = AB, ACAB, BD =ADACD, CDE =AE = AABCDEEA =EABCDECDE = CDABCDEBD = BCCD =BCABCDER的候选码是A, E, CD, BC。R=(A,B,C,D,E)F：A BC CD E B D E ABCNF & 3NFR的超码是A, E, CD, BCBD中B不是R的超码，R不满足BCNF = 将R分解为

19、R1(B, D)和R2(A, B, C, E)R1上的函数依赖F1=B D，满足BCNFR2上的函数依赖F2=A BC, E AA BC中A不是R2的超码，不满足BCNF= 将R2分解为R3(A, B, C)和R4(A, E)R3上的函数依赖F3=A BC ，满足BCNFR2上的函数依赖F4=E A ，满足BCNFR的BCNF分解为：(B,D) (A,B,C) (A,E)BCNF & 3NF8.19 给出模式R的一个BCNF分解分解和3NF分解。R=(A,B,C,D,E)函数依赖集F：A BCCD EB DE ABCNF & 3NF8.19 给出模式R的一个BCNF分解和3NF

20、分解分解。R=(A,B,C,D,E)函数依赖集F：A BCCD EB DE A没有需要合并的函数依赖没有无关属性Fc=F=A BC, CD E, B D, E A计算正则覆盖计算正则覆盖FcFc=Frepeat 合并ab1, ab2为ab1b2 删除ab中的无关属性until Fc不变-无关属性无关属性left：(a-A)+ b ?right：替换为a(b-A)与F等价?正则覆盖R=(A,B,C,D,E)F：A BC CD E B D E AFc=A BC, CD E, B D, E AR的候选码是A, E, CD, BCA BC = R1=(A, B, C)CD E = R2=(C, D, E)B D = R3=(B, D)E A = R4=(E,A)且，R1R4中包含了R的候选码R的3NF分解为：(A,B,C) (C,D,E) (B,D) (A,E)不在已有的模式中不在已有的模式中重新形成新的模式重新形成新的模式BCN