数据库系统实现复习提纲.pdf
WORD 格式Step2:DBMS 对命令进行语法检查、语义检查、存取权限检查，决定是否执行该命令Step3:DBMS 执行查询优化，把命令转换为一串单记录的存取操作序列Step4:执行存取操作序列（反复执行以下各步，直至结束）Step5:DBMS 首先在缓冲区内查找记录，若找到转Step6:DBMS 查看存储模式，决定从哪个文件存取哪个物理记录Step9:操作系统将数据从数据库存储区送到系统缓冲区Step10:DBMS 根据用户命令和数据字典的内容导出用户所要读取的数据格式Step11:DBMS 将数据记录从系统缓冲区传送到用户工作区Step12:DBMS 将执行状态信息返回给用户3.存储管理器负责管理的数据包括 目标数据、元数据、索引和日志上。等，这些数据保存在磁盘Step7:DBMS 根据 6 的结果，向操作系统发出读取记录的命令Step8:操作系统执行读取数据的命令10，否则转 62.DBMS 从接受查询请求到返回结果的整个运行过程。（有图）（简答，问答）复习提纲 20151.数据库管理系统主要包括 存储管理器、查询处理器和事务管理器等几个子系统。Step1:用户向 DBMS 发出调用数据库数据的命令1专业资料整理WORD 格式4.磁盘结构及磁盘容量的计算。（填空题）磁盘控制器：控制一个或多个磁盘的小处理器，功能如下,定进行坏扇区的重映射。硬盘容量=柱面数(表示每面盘面上有几条磁道，一般总数是1024)磁头数(表示盘面数)扇区数（表示每条磁道有几个扇区，一般总数是相互关系。一般为 512B/4KB)5.一次磁盘访问（I/O）的时间包括 寻道时间（占时多）、定位时间（中）和读取时间（小），64）扇区(存储基本单元，大小区。为所写扇区附加校验和，并在读取扇区时检查它。该扇区正开始移动到磁头下面。将从该扇区读取的二进制位传送到主存储，或将从主存要写入的二进制位传送到该扇位磁头到一个特定的半径位置。选择一个准备读写的盘面，从位于该盘面的磁头下的磁道上选择一个扇区。并识别何时2专业资料整理WORD 格式6.磁盘块存取的优化方法。（调度那些，双缓冲，什么鬼）（填空，简答）在主存储器中对块进行缓冲以减少块的读写次数按柱面组织数据使用多个磁盘磁盘镜像磁盘臂调度-电梯算法利用非易失性 RAM 作为写缓冲预读和双缓冲日志磁盘7.RAID 具有提高性能和提高可靠性能两方面的作用。（填空题）RedundantArraysofInexpensiveDisks价格上，大量廉价的磁盘比少量昂贵的大磁盘合算得多性能上，使用大量磁盘可以提高数据的并行存取可靠性上，冗余数据可以存放在多个磁盘上，因此一个磁盘的故障不会导致数据丢失RAID 级别专业资料整理3WORD 格式RAID0 级：块级拆分，无冗余RAID1 级：带块级拆分的磁盘镜像RAID2 级：内存风格的纠错码组织结构RAID3 级：位交叉的奇偶校验组织结构RAID4 级：块交叉的奇偶校验组织结构RAID5 级：块交叉的分布奇偶校验位的组织结构写数据需要 2 次磁盘读和 2 次磁盘写操作。假定:有 4 个数据盘和一个冗余盘读出数据，与从任何一个磁盘读块没有差别；余盘，允许两个盘出现故障）优缺点（填空简答）RAID4RAID6 级：P+Q 冗余方案8.重点掌握 RAID4（块级拆分，奇偶校验）、RAID5（块级拆分，）和 RAID6（提供两个冗4专业资料整理WORD 格式RAID5例如由 5 个磁盘组成的阵列，第n 块的奇偶校验位存储在第(nmod5)+1 上，其余所有磁盘都参与对读请求的服务，而RAID4 中奇偶校验磁盘不参与读操作RAID5 包容了 RAID4，同时在相同成本下，提供了更好的读写性能磁盘的第 n块存储了对应这个块的实际数据奇偶校验块不能和这个块对应的数据存储在同一个磁盘上4 个将数据和奇偶校验位都分布到所有的N+1 个磁盘上；对每个块，一个磁盘存储奇偶校验位，其余磁盘存储数据5专业资料整理WORD 格式RAID6RAID6类似于 RAID5，存储了额外的冗余信息不采用奇偶校验位的方法，使用类似对Reed-Solomon 码的编码每 4 位数据存储 2 位冗余信息可以容忍两个磁盘发生故障9.缓冲区管理工作流程。（还有数据结构，填空简答）Dirty:已经被修改过的Frame请求处理的流程查看 Bufferpool 是否包含此页，如没有，则找一个 pin_count 为 0 的 frame，pin_count+如 dirty 为 true,则将其写入磁盘数据结构和流程:每个 frameframe 包括：pin_count,dirtypin_count,dirtypin_count:正在访问该frame 的事务的个数6专业资料整理WORD 格式将相应的页读入此 frame11.文件中变长纪录的组织方法，纪录 id（页号，块号，块内起始地址，长度）的组成。（填织。（填空）顺序文件组织（于是一个 I/O 操作可以从多个关系中取到相关记录。13.顺序文件组织中，为什么在进行大量插删改后需要重组？（溢出块溢出表里）（简答题）聚簇文件组织（clusteringfileorganizationclusteringfileorganization）几个不同关系的记录存储在同一文件中（通常用一个文件存储一个关系的记录。）甚至不同关系中的相关记录存储在相同的块中，散列文件组织（hashingfileorganizationhashingfileorganization）在每条记录的某些属性上计算一个散列sequentialfileorganizationsequentialfileorganization）记录根据“搜索码”的值顺序存储。堆文件组织（heapfileorganizationheapfileorganization）一条记录可以放在文件中的任何地方，只要有空间存放这条记录。记录是无序的。通常一个关系是一个单独的文件。空）12.文件中组织纪录的几种方法：堆文件组织、顺序文件组织、散列文件组织、聚簇文件组将 frame 的地址返回10.文件中定长纪录的组织方法，纪录id（页号，块号）的组成。函数。散列函数的结果确定了记录应该放到文件的哪个块中。7专业资料整理WORD 格式14.索引是支持对于所要求的数据进行快速定位的附加的数据结构。聚集索引与非聚集索引17.动态散列索引的实现原理（可扩充散列，实现方法，桶分裂）（简答，问答）思想原理:动态散列技术允许散列函数动态改变，通过桶的合并和分解实现数据库的增大或缩小的需求，这样既继承了散列高效查找效率又保持了良好的空间压缩率。动态散列是逐步扩充散列值的位数来构造索引，它通过位比较来实现散列值的定位，这种比较方式计算机通过几个 CPU 机器指令即可实现，故它的效率很高。15.B+树的树结点的大小一般取块的大小。16.B+树的查询及构造方法，插入、删除方法，效率。（简答，问答）稠密索引与稀疏索引多级索引（填空）创建或删除一个溢出块插入一条记录到一个空块中删除记录将记录移动相邻的块中索引顺序文件上的修改动作:创建或删除一个空存储块18.在位图索引中，从位向量得到压缩编码位向量的方法以及从压缩编码位向量重新构造实际的位向量的方法（填空）K.O.K.O.19.位图索引的构造及维护方法（简答）K.O.K.O.20.查询优化是为关系代数表达式的计算选择最有效的查询计划的过程。（填空题）（填空题，分析21.选择运算算法及代价分析（主要考虑带有B+树索引的情况）题）外部排序的算法（初始归并段的数目、归并的趟数）及代价分22.析（填空题，多空）-归并23.各种连接算法的实现及其代价分析（块嵌套循环连接算法、散列连接算法、排序连25.为什么要进行结果集大小的估计？（判断要不要用索引）26.DBMS 中存储的统计信息（最大最小值，分布情况什么鬼）的作用是什么？（制定执行接算法）（占比例高，分析题）24.对于基于主码、外码连接的情况：结果集的元组数等于外码所在表的元组数。（填空题）8专业资料整理WORD 格式计划时，计算代价需要）（简答题）27.启发式优化的步骤。（简答题）28.事务ACID特性，以及分别有什么机制保证的（填空题）这些操作要么都做，要么都不做，事务定义：事务是由一系列操作序列构成的程序执行单元，是一个不可分割的工作单位，例如银行转帐。SQL 中事务的定义：事务以Begintransaction开始，以Commitwork或 Rollbackwork结束。Commitwork 表示提交，事务正常结束数据库的一致性状态由用户来负责，由并发控制机制实现隔离性(Isolation)(Isolation)：系统必须保证事务不受其它并发执行事务的影响对任何一对事务 T1，T2，在 T1 看来，T2 要么在 T1 开始之前已经结束，要么在成之后再开始执行隔离性通过并发控制机制 实现T1 完一致性(Consistency)(Consistency)：事务的隔离执行必须保证数据库的一致性事务开始前，数据库处于一致性的状态；事务结束后，数据库必须仍处于一致性状态Rollbackwork 表示事务非正常结束，撤消事务已做的操作，回滚到事务开始时状态事务特(ACID)(ACID)：性原子(Atomicity)(Atomicity)：事务中包含的所有操作要么全做，要么全不原子性由恢复机制实性做；现9专业资料整理WORD 格式持久性通过恢复机制实现29.事务可串行化的判断一般采用优先图来实现，优先图的构造方法及可串行化的判断方法。（什么鬼图，有没有环 可不可串行化）（填空）死锁：如果系统中存在一个事务集，集合中的每个事务在等待该集合中的另一个事务所锁住-死锁恢复选择牺牲者：应使事务回滚带来的代价最小。影响事务回滚代价的因素：事务已计算了多久，在完成之前还将计算多长时间，事务已使用了多少数据项，为完成事务还需使用多基于超时的机制：一种介于死锁预防与死锁检测之间的折中的机制。31.锁表结构（散列表？）及其工作原理（在申请加锁，释放锁是怎样的）（简答题，问答）封锁的实现锁管理器中重要的 数据结构：锁表(locktable)。为目前已加锁的每个数据项维护一个链表，链表中每一个记录表示对该数据项的一个加锁请求。记录按请求到达的顺序排序。链表中的每个记录主要包括如下内容：哪个事务提出的请求，请求的锁类型，该请求是否已被授予锁。少数据项，回滚时将牵涉多少事务回滚：彻底回滚，或只回滚到可以解除死锁处。2 2：强占与事务回滚死锁检测与死锁恢复：允许系统进入死锁状态，然后进行检测和恢复。的数据项，则称系统处于死锁状态。处理死锁的两种主要方法：死锁预防：采用死锁预防协议保证系统永不进入死锁状态1 1：对加锁请求加以限制冲突可串行化调度一定是视图可串行化的，存在视图可串行化但非冲突可串行化的调度。30.死锁（产生）及其解决方法（填空）可串行化：若调度 S 与一个串行调度的执行有相同的效果，则称调度冲突可串行化：视图可串行化：如果某个调度视图等价于一个串行调度，则称该调度是视图可串行化的，S 是可串行化的。持久性(Durability)(Durability)：一个事务一旦提交之后，它对数据库的影响必须是永久的系统发生故障不能改变事务的持久性10专业资料整理WORD 格式采用一个以数据项名称为索引的散列表作为链表入口。锁管理器工作方式当一个封锁请求到达时，如果相应数据项的链表存在，则在该链表末尾增加一个记录，否则新建一个仅包含该请求的链表。（数据项上的第一次加锁请求总是被授予，但当事务向已被加锁的数据项申请加锁时，只有当该请求与先前请求相容，并且所有先前的请求都已被授予锁的条件下，锁管理器才为该请求授予锁，否则令请求等待。）当收到一个事务的解锁消息时，则将相应的链表记录删除，然后检查随后的记录，如果有正在等待的封锁请求，则看该请求能否被授权，如果能，则授权该请求并处理其后记录，如果还有，类似地一个接一个的处理。如果一个事务中止，则删除该事务产生的正在等待加锁的所有请求。当数据库系统34.使用 undo/redoundo/redo 日志进行恢复（系统故障的）的方法。（扫描文件，撤销队列，重做队列，对没完成的事务加终止标记）（简答）undo 日志保证事务的原子性redo 日志保证事务的持久性undo/redo 日志保证事务的原子性和持久性对每一个形如 的记录，将Ti 加入 redo-list。使用 undo/redoundo/redo 日志的恢复：1.从后往前扫描日志，构造undo-list和 redolist：止。磁盘故障，由于磁头损坏或故障造成磁盘块上的内容丢失。逻辑错误，事务由于某些内部条件而无法继续正常执行。系统错误，系统进入一种不良状态（如，死锁），使事务无法继续正常执行。系统崩溃，硬件或数据库软件或操作系统故障，易失性存储器内容的丢失，事务处理终故障分类：事务故障：（填空）33.数据库中主要有哪几类故障。（填空）撤消了该事务，则该中止事务持有的所有锁将被释放。32.同数据库交互的三个地址空间.（磁盘地址空间，缓冲区地址空间，事务内部的地址空间）11专业资料整理WORD 格式对每一个形如 的记录，如果 Ti 不属于 redo-list，则将 Ti 加入 undo-list。作。推迟提交的一个问题：使用 undo/redoundo/redo 日志的系统中可能出现这样的行为：事务在用户看来已经提交，但由于最好为 undo/redoundo/redo 日志使用一条附加的规则：记录一旦出现在日志中就必须被怎么样？）（填空题，简答题）故障恢复时扫描整个日志所带来的问题：扫描日志耗费时间长重做所有已提交事务耗费时间长，事实上许多事务对数据库的修改已经写到磁盘，不必再重做。解决办法：周期性地对日志做检查点，以避免故障恢复时检查整个日志。undo/redoundo/redo 日志检查点的做法：1 1）写入日志记录STARTCKPT(T1,Tk)，其中 T1,T1,Tk,Tk 是所有的活跃事务，并刷新日志。2 2）将所有脏缓冲区写到磁盘，脏缓冲区即包含一个或多个修改过的数据库元素的缓冲区。3 3）写入日志记录 并刷新日志。系统使用检查点方法进行 恢复的步骤：1、找到最后一个检查点记录在日志文件中的地址，由该地址在日志文件中找到最后一个检查点记录。2、由该检查点记录得到检查点建立时刻所有正在执行的事务清单ACTIVE-LIST，把ACTIVE-LIST暂时放入UNDO-LIST，REDO-LIST暂为空。刷新到磁盘上。记录尚未刷新到磁盘，后来的一次崩溃使该事务被撤销而不是重做。2.由后至前重新扫描日志，对undo-list 中的每个事务记录执行undo 操作。3.由前至后重新扫描日志，并且对 redo-list 中每个事务记录执行redo 操Ti 的每一个日志Ti 的每一个日志35.undo/redo35.undo/redo 日志中，为什么要引入检查点，检查点的创建需要做的工作。（避免读取整个日志文件，避免早就提交的事务的工作）（当前所有日志缓冲和数据缓冲,）（恢复工作12专业资料整理WORD 格式3、从检查点开始正向扫描日志文件。UNDO-LIST；如有新开始的事物 Ti，把 Ti 暂时放入13专业资料整理WORD 格式如有提交的事务 Tj，把 Tj 从 UNDO-LIST移到 REDO-LIST，直到日志文件结束。4、对 UNDO-LIST 中的每个事务执行 UNDO 操作，对 REDO-LIST 中的每个事务执行 REDO 操数据在分布式数据库的存储途径：38.分布式数据库中，数据分片的四种方式。（水平，垂直分片；）（填空题）模式改变了，通过调整全局模式与分片模式之间的映象关系来保持全局模式不变位置透明性：用户或应用程序不必了解片段的存储位置局部数据模型透明性：用户或应用程序不必了解局部场地上使用的是哪种数据模型分布（网络）透明性：分片透明性：用户或应用程序只对全局关系进行操作而不必考虑关系的分片。如果分片分片方式：水平分片（并运算）,垂直分片（连接运算）,导出分片,混合分片39.分片透明性和位置透明性的含义（讲义例子）（填空题，简答题）数据分片优点：将关系分片，有利于按用户需求组织数据的分布。如产品（内销产品，出口产品）。复制+分片：关系被划分为几个片段，系统为每个片段维护几个副本37.分布式数据库中数据访问的瓶颈（CPU,CPU,磁盘 I/O,I/O,网络传输）复制：系统维护关系的几个完全相同的副本，这些副本存储在不同的结点上分片：关系被划分为几个片段，各个片段存储在不同的结点上作。36.数据在分布式数据库的存储途径有哪三种。（分片组，复制，分片+复制）14专业资料整理WORD 格式40.半连接的实现方法（讲义中的示例）（重点）（简答题，问答题）15专业资料整理WORD 格式41.信息集成的三个方面的问题（）具体含义也要（问答题，简答题）动机:提供对分布、自治且通常是异质的多个信息源的共享与统一访问。设计自治性：各信息源之间以及信息源与集成系统之间在数据模型，数据元素命名，数据的语义解释，完整性约束，以及系统实现平台等诸多设计选择方面是相互独立的。自治性:信息源系统独立地决定其自身特性，保持其分开的独立控制，随着时间改变数据与功能这种改变不应受到集成系统过多制约。16专业资料整理WORD 格式执行自治性：信息源不受干预地运行自身系统并调度外部提出的数据操作请求。技术差异：例如不同的通信协议、交换格式、API、查询能力与机制、查询语言等。分布性：用户基于某种全局模式提出查询或其他数据操作请求为信息源查询或其他子事务。同时，从访问性能及数据可用性方面考虑要冗余存储(复制或实化视图)。冗余数据的相容性维护需要更为复杂的更新传播技术支持。42.数据集成中，包装器完成的三种映射（模式，语言，数据映射）（填空）43.集成视图与数据源之间的数据一致性的四个级别。（收敛，弱，强（时序），完全）（填空）一、填空题 30基本概念，简单计算二、简答题 2045 道，给要点就好三、分析题 25算法代价分析（实验的那些B+树散列索引,），基本思想四、问答题 25详细的44.数据集成的三种体系结构，重点掌握中介器-包装器和数据仓库方法。（还有数据库联邦）需要检测和消解数据源之间数据的不相容性（数据融合）。查询重写需要复杂的映射支持。需要的更强能力支持包括:需要访问不同模式的数据。,需要容许数据的必,这些请求需要通过重写分解建模差异：有些文献称之为逻辑异质性，指对于真实世界概念在理解、建模及其表示方面存在的差异。数据模型差异：例如关系、OO 及 XML 等等。不同的数据模型分别提供不同建模原语，并具有不同表达能力。异质性：信息源独立地选择系统平台、数据管理系统,并以其自身观察和理解方式对所关心真实世界进行建模。相关自治性：信息源独立地决定哪些数据可以作为集成系统组成部分提供其他系统共享。题型：17专业资料整理
