数据库系统实现复习提纲

1、.wd.wd.wd.复习提纲20151.数据库管理系统主要包括存储管理器、查询处理器和事务管理器等几个子系统。2.DBMS从承受查询请求到返回结果的整个运行过程。有图简答，问答Step 1:用户向DBMS发出调用数据库数据的命令Step 2:DBMS对命令进展语法检查、语义检查、存取权限检查，决定是否执行该命令Step 3:DBMS执行查询优化，把命令转换为一串单记录的存取操作序列Step 4:执行存取操作序列反复执行以下各步，直至完毕Step 5:DBMS首先在缓冲区内查找记录，假设找到转10，否那么转6Step 6:DBMS查看存储模式，决定从哪个文件存取哪个物理记录Step 7:DBMS

2、根据6的结果，向操作系统发出读取记录的命令Step 8:操作系统执行读取数据的命令Step 9:操作系统将数据从数据库存储区送到系统缓冲区Step 10:DBMS根据用户命令和数据字典的内容导出用户所要读取的数据格式Step 11:DBMS将数据记录从系统缓冲区传送到用户工作区Step 12:DBMS将执行状态信息返回给用户3.存储管理器负责管理的数据包括目标数据、元数据、索引和日志等，这些数据保存在磁盘上。4.磁盘构造及磁盘容量的计算。填空题磁盘控制器： 控制一个或多个磁盘的小处理器，功能如下,定位磁头到一个特定的半径位置。选择一个准备读写的盘面，从位于该盘面的磁头下的磁道上选择一个扇区。并

3、识别何时该扇区正开场移动到磁头下面。将从该扇区读取的二进制位传送到主存储，或将从主存要写入的二进制位传送到该扇区。为所写扇区附加校验和，并在读取扇区时检查它。进展坏扇区的重映射。硬盘容量 = 柱面数(表示每面盘面上有几条磁道，一般总数是1024) 磁头数(表示盘面数) 扇区数表示每条磁道有几个扇区，一般总数是64 扇区(存储 基本单元，大小一般为512B/4KB)5.一次磁盘访问I/O的时间包括寻道时间占时多、定位时间中和读取时间小，相互关系。6.磁盘块存取的优化方法。调度那些，双缓冲，什么鬼填空，简答在主存储器中对块进展缓冲以减少块的读写次数 按柱面组织数据 使用多个磁盘 磁盘镜像 磁盘臂调

4、度- 电梯算法 利用非易失性RAM作为写缓冲 预读和双缓冲 日志磁盘7.RAID具有提高性能和提高可靠性能两方面的作用。填空题Redundant Arrays of Inexpensive Disks价格上，大量廉价的磁盘比少量昂贵的大磁盘合算得多性能上，使用大量磁盘可以提高数据的并行存取可靠性上，冗余数据可以存放在多个磁盘上，因此一个磁盘的故障不会导致数据丧失RAID级别RAID 0级：块级拆分，无冗余RAID 1级：带块级拆分的磁盘镜像RAID 2级：内存风格的纠错码组织构造RAID 3级：位穿插的奇偶校验组织构造RAID 4级：块穿插的奇偶校验组织构造RAID 5级：块穿插的分布奇偶校验

5、位的组织构造RAID 6级：P+Q冗余方案8.重点掌握RAID4块级拆分，奇偶校验、RAID5块级拆分，和RAID6提供两个冗余盘，允许两个盘出现故障优缺点填空简答RAID 4假定:有4个数据盘和一个冗余盘读出数据，与从任何一个磁盘读块没有差异；写数据需要2次磁盘读和2次磁盘写操作。RAID 5将数据和奇偶校验位都分布到所有的N+1个磁盘上；对每个块，一个磁盘存储奇偶校验位，其余磁盘存储数据例如由5个磁盘组成的阵列，第n块的奇偶校验位存储在第(n mod 5)+1上，其余4个磁盘的第n块存储了对应这个块的实际数据奇偶校验块不能和这个块对应的数据存储在同一个磁盘上所有磁盘都参与对读请求的服务，而

6、RAID 4中奇偶校验磁盘不参与读操作RAID 5包容了RAID 4，同时在一样成本下，提供了更好的读写性能RAID 6类似于RAID 5，存储了额外的冗余信息不采用奇偶校验位的方法，使用类似Reed-Solomon码的编码对每4位数据存储2位冗余信息可以容忍两个磁盘发生故障9.缓冲区管理工作流程。还有数据构造，填空简答数据构造和流程:每个frame包括：pin_count,dirtypin_count:正在访问该frame的事务的个数Dirty:已经被修改正的Frame请求处理的流程查看Buffer pool是否包含此页，如没有，那么找一个pin_count为0的frame，pin_coun

7、t+如dirty为true,那么将其写入磁盘将相应的页读入此frame将frame的地址返回10.文件中定长纪录的组织方法，纪录id页号，块号的组成。11.文件中变长纪录的组织方法，纪录id页号，块号，块内起始地址，长度的组成。填空12.文件中组织纪录的几种方法：堆文件组织、顺序文件组织、散列文件组织、聚簇文件组织。填空堆文件组织heap file organization 一条记录可以放在文件中的任何地方，只要有空间存放这条记录。记录是无序的。通常一个关系是一个单独的文件。顺序文件组织sequential file organization 记录根据“搜索码的值顺序存储。散列文件组织hash

8、ing file organization 在每条记录的某些属性上计算一个散列函数。散列函数的结果确定了记录应该放到文件的哪个块中。聚簇文件组织clustering file organization几个不同关系的记录存储在同一文件中通常用一个文件存储一个关系的记录。甚至不同关系中的相关记录存储在一样的块中，于是一个I/O操作可以从多个关系中取到相关记录。13.顺序文件组织中，为什么在进展大量插删改后需要重组溢出块溢出表里简答题索引顺序文件上的修改动作:创立或删除一个空存储块创立或删除一个溢出块插入一条记录到一个空块中删除记录将记录移动相邻的块中14.索引是支持对于所要求的数据进展快速定位的附

9、加的数据构造。聚集索引与非聚集索引稠密索引与稀疏索引多级索引填空15.B+树的树结点的大小一般取块的大小。16.B+树的查询及构造方法，插入、删除方法，效率。简答，问答17.动态散列索引的实现原理可扩大散列，实现方法，桶分裂简答，问答思想原理:动态散列技术允许散列函数动态改变，通过桶的合并和分解实现数据库的增大或缩小的需求，这样既继承了散列高效查找效率又保持了良好的空间压缩率。 动态散列是逐步扩大散列值的位数来构造索引，它通过位比较来实现散列值的定位，这种比较方式计算机通过几个CPU机器指令即可实现，故它的效率很高。18.在位图索引中，从位向量得到压缩编码位向量的方法以及从压缩编码位向量重新构

10、造实际的位向量的方法填空K.O.19.位图索引的构造及维护方法简答K.O.20.查询优化是为关系代数表达式的计算选择最有效的查询方案的过程。填空题21.选择运算算法及代价分析主要考虑带有B+树索引的情况填空题，分析题22.外部排序的算法初始归并段的数目、归并的趟数及代价分析填空题，多空23.各种连接算法的实现及其代价分析块嵌套循环连接算法、散列连接算法、排序-归并连接算法占比例高，分析题24.对于基于主码、外码连接的情况：结果集的元组数等于外码所在表的元组数。填空题25.为什么要进展结果集大小的估计判断要不要用索引26.DBMS中存储的统计信息最大最小值，分布情况什么鬼的作用是什么制定执行方案

11、时，计算代价需要简答题27.启发式优化的步骤。简答题28.事务的ACID特性，以及分别有什么机制保证填空题事务定义：事务是由一系列操作序列构成的程序执行单元，这些操作要么都做，要么都不做，是一个不可分割的工作单位，例如银行转帐。SQL中事务的定义：事务以Begin transaction开场，以Commit work或 Rollback work完毕。Commit work表示提交，事务正常完毕Rollback work表示事务非正常完毕，撤消事务已做的操作，回滚到事务开场时状态事务特性(ACID)：原子性(Atomicity)：事务中包含的所有操作要么全做，要么全不做；原子性由恢复机制实现一

12、致性(Consistency)：事务的隔离执行必须保证数据库的一致性事务开场前，数据库处于一致性的状态；事务完毕后，数据库必须仍处于一致性状态数据库的一致性状态由用户来负责，由并发控制机制实现隔离性(Isolation)：系统必须保证事务不受其它并发执行事务的影响对任何一对事务T1，T2，在T1看来，T2要么在T1开场之前已经完毕，要么在T1完成之后再开场执行隔离性通过并发控制机制实现持久性(Durability)：一个事务一旦提交之后，它对数据库的影响必须是永久的系统发生故障不能改变事务的持久性持久性通过恢复机制实现29.事务可串行化的判断一般采用优先图来实现，优先图的构造方法及可串行化的判

13、断方法。什么鬼图，有没有环可不可串行化填空可串行化：假设调度S与一个串行调度的执行有一样的效果，那么称调度S是可串行化的。冲突可串行化：视图可串行化：如果某个调度视图等价于一个串行调度，那么称该调度是视图可串行化的，冲突可串行化调度一定是视图可串行化的，存在视图可串行化但非冲突可串行化的调度。30.死锁产生及其解决方法填空死锁：如果系统中存在一个事务集，集合中的每个事务在等待该集合中的另一个事务所锁住的数据项，那么称系统处于死锁状态。处理死锁的两种主要方法：死锁预防：采用死锁预防协议保证系统永不进入死锁状态1：对加锁请求加以限制2：强占与事务回滚死锁检测与死锁恢复：允许系统进入死锁状态，然后进

14、展检测和恢复。-死锁恢复选择牺牲者：应使事务回滚带来的代价最小。影响事务回滚代价的因素：事务已计算了多久，在完成之前还将计算多长时间， 事务已使用了多少数据项，为完成事务还需使用多少数据项，回滚时将牵涉多少事务回滚：彻底回滚，或只回滚到可以解除死锁处。基于超时的机制：一种介于死锁预防与死锁检测之间的折中的机制。31.锁表构造散列表及其工作原理在申请加锁，释放锁是怎样的简答题，问答封锁的实现锁管理器中重要的数据构造：锁表(lock table)。为目前已加锁的每个数据项维护一个链表，链表中每一个记录表示对该数据项的一个加锁请求。记录按请求到达的顺序排序。链表中的每个记录主要包括如下内容：哪个事务

15、提出的请求，请求的锁类型，该请求是否已被授予锁。采用一个以数据项名称为索引的散列表作为链表入口。锁管理器工作方式当一个封锁请求到达时，如果相应数据项的链表存在，那么在该链表末尾增加一个记录，否那么新建一个仅包含该请求的链表。数据项上的第一次加锁请求总是被授予，但当事务向已被加锁的数据项申请加锁时，只有当该请求与先前请求相容，并且所有先前的请求都已被授予锁的条件下，锁管理器才为该请求授予锁，否那么令请求等待。当收到一个事务的解锁消息时，那么将相应的链表记录删除，然后检查随后的记录，如果有正在等待的封锁请求，那么看该请求能否被授权，如果能，那么授权该请求并处理其后记录，如果还有，类似地一个接一个的

16、处理。如果一个事务中止，那么删除该事务产生的正在等待加锁的所有请求。当数据库系统撤消了该事务，那么该中止事务持有的所有锁将被释放。32.同数据库交互的三个地址空间.磁盘地址空间，缓冲区地址空间，事务内部的地址空间填空33.数据库中主要有哪几类故障。填空故障分类：事务故障：逻辑错误，事务由于某些内部条件而无法继续正常执行。系统错误，系统进入一种不良状态如，死锁，使事务无法继续正常执行。系统崩溃，硬件或数据库软件或操作系统故障，易失性存储器内容的丧失，事务处理终止。磁盘故障，由于磁头损坏或故障造成磁盘块上的内容丧失。34.使用undo/redo日志进展恢复系统故障的的方法。扫描文件，撤销队列，重做

17、队列，对没完成的事务加终止标记简答undo日志保证事务的原子性redo日志保证事务的持久性undo/redo日志保证事务的原子性和持久性使用undo/redo日志的恢复： 1. 从后往前扫描日志，构造undo-list 和redolist： 对每一个形如的记录，将Ti 参加redo-list。 对每一个形如的记录，如果Ti不属于redo-list，那么将Ti参加undo-list。 2. 由后至前重新扫描日志，对undo-list中的每个事务Ti的每一个日志记录执行undo操作。 3. 由前至后重新扫描日志，并且对redo-list中每个事务Ti的每一个日志记录执行redo操作。推迟提交的一个

18、问题： 使用undo/redo日志的系统中可能出现这样的行为： 事务在用户看来已经提交， 但由于记录尚未刷新到磁盘，后来的一次崩溃使该事务被撤销而不是重做。 最好为undo/redo日志使用一条附加的规那么：记录一旦出现在日志中就必须被刷新到磁盘上。35.undo / redo日志中，为什么要引入检查点，检查点的创立需要做的工作。防止读取整个日志文件，防止早就提交的事务的工作当前所有日志缓冲和数据缓冲恢复工作怎么样填空题，简答题故障恢复时扫描整个日志所带来的问题：扫描日志消耗时间长重做所有已提交事务消耗时间长，事实上许多事务对数据库的修改已经写到磁盘，不必再重做。解决方法：周期性地对日志做检查

19、点，以防止故障恢复时检查整个日志。undo / redo日志检查点的做法： 1写入日志记录，其中T1, , Tk是所有的活泼事务，并刷新日志。 2将所有脏缓冲区写到磁盘，脏缓冲区即包含一个或多个修改正的数据库元素的缓冲区。 3写入日志记录并刷新日志。系统使用检查点方法进展恢复的步骤：1、找到最后一个检查点记录在日志文件中的地址，由该地址在日志文件中找到最后一个检查点记录。2、由该检查点记录得到检查点建设时刻所有正在执行的事务清单ACTIVE-LIST，把ACTIVE-LIST暂时放入UNDO-LIST，REDO-LIST暂为空。3、从检查点开场正向扫描日志文件。如有新开场的事物Ti，把Ti暂时

20、放入UNDO-LIST；如有提交的事务Tj，把Tj从UNDO-LIST移到REDO-LIST，直到日志文件完毕。4、对UNDO-LIST中的每个事务执行UNDO操作，对REDO-LIST中的每个事务执行REDO操作。36.数据在分布式数据库的存储途径有哪三种。分片组，复制，分片+复制数据在分布式数据库的存储途径：复制：系统维护关系的几个完全一样的副本，这些副本存储在不同的结点上分片：关系被划分为几个片段，各个片段存储在不同的结点上复制+分片：关系被划分为几个片段，系统为每个片段维护几个副本37.分布式数据库中数据访问的瓶颈CPU,磁盘I/O,网络传输38.分布式数据库中，数据分片的四种方式。水

21、平，垂直分片；填空题数据分片优点：将关系分片，有利于按用户需求组织数据的分布。如产品内销产品，出口产品。分片方式：水平分片并运算,垂直分片连接运算,导出分片,混合分片39.分片透明性和位置透明性的含义讲义例子填空题，简答题分布网络透明性：分片透明性：用户或应用程序只对全局关系进展操作而不必考虑关系的分片。如果分片模式改变了，通过调整全局模式与分片模式之间的映象关系来保持全局模式不变位置透明性：用户或应用程序不必了解片段的存储位置局部数据模型透明性：用户或应用程序不必了解局部场地上使用的是哪种数据模型40.半连接的实现方法讲义中的例如重点简答题，问答题41.信息集成的三个方面的问题具体含义也要问答题，简答题动机:提供对分布、自治且通常是异质的多个信息源的共享与统一访问。自治性: 信息源系统独立地决定其自身特性，保持其分开的独立控制，随着时间改变数据与功能这种改变不应受到集成系统过