09级数据库系统实现复习提纲.doc

数据库管理系统主要包括存储管理器、查询处理器和事务管理器等几个子系统。DBMS从接受查询请求到返回结果的整个运行过程。存储管理器负责管理的数据包括目标数据、元数据、索引和统计信息等，这些数据保存在磁盘上。-一次磁盘访问（I/O）的时间包括寻道时间、定位时间和读取时间，相互关系。访问时间从发出请求到数据开始传输之间的时间 寻道时间（Seek time）磁盘臂定位时间，即磁盘臂移动到正确的磁道所需时间与移动距离成正比，平均寻道时间是最坏时间的1/3（4-10ms） 旋转等待时间（Rotational latency ）寻道结束后，等待被存取的扇区出现在读写头下面的时间平均旋转等待时间是磁盘旋转一周时间的1/2（2-5ms）数据传输率从磁盘获得数据或向磁盘存储数据的速率（4-8MB/秒） 平均故障时间预期系统无故障连续运行的时间（30,000-800,000小时，即3.4-91年） RAID具有提高性能和提高可靠性两方面的作用-。重点掌握RAID4、RAID5和RAID6优缺点RAID 4块级拆分，在一个独立的磁盘上为其他N个磁盘上对应的块保留一个奇偶校验块读取一个块只访问一个磁盘每个存取操作的传输率低，但可以并行地执行多个读操作，从而产生较高的总的I/O率读取大量数据的操作有很高的传输率，因为所有磁盘可以并行地读RAID 5将数据和奇偶校验位都分布到所有的N+1个磁盘上；对每个块，一个磁盘存储奇偶校验位，其余磁盘存储数据例如由5个磁盘组成的阵列，第n块的奇偶校验位存储在第(n mod 5)+1上，其余4个磁盘的第n块存储了对应这个块的实际数据奇偶校验块不能和这个块对应的数据存储在同一个磁盘上所有磁盘都参与对读请求的服务，而RAID 4中奇偶校验磁盘不参与读操作RAID 5包容了RAID 4，同时在相同成本下，提供了更好的读写性能RAID 6类似于RAID 5，存储了额外的冗余信息不采用奇偶校验位的方法，使用类似Reed-Solomon码的编码对每4位数据存储2位冗余信息可以容忍两个磁盘发生故障-顺序文件组织中，为什么在进行大量插删改后需要重组？如果需要存储在溢出块中的记录相当的少，这种方法会工作得很好。然而，搜索码顺序和物理顺序之间的一致性最终将完全丧失，在这种情况下，顺序处理将变得效率十分低下。此时，文件应该被重组，使得它再一次在物理上顺序存放。这种重组的代价是很高的，并且必须在系统负载很低的时候执行。需要重组的频率依赖于新记录插入的频率。-搜索码是用于在文件中查找记录的属性或属性集。索引是支持对于所要求的数据进行快速定位的附加的数据结构。-B+树的树结点的大小一般取决于块的大小。B+树的构造方法，插入、删除方法，效率。-动态散列索引的实现原理 思想原理 动态散列技术允许散列函数动态改变，通过桶的合并和分解实现数据库的增大或缩小的需求，这样既继承了散列高效查找效率又保持了良好的空间压缩率。 动态散列是逐步扩充散列值的位数来构造索引，它通过位比较来实现散列值的定位，这种比较方式计算机通过几个CPU机器指令即可实现，故它的效率很高。-在位图索引中，从位向量得到压缩编码位向量的方法以及从压缩编码位向量重新构造实际的位向量的方法查询优化是为关系代数表达式的计算选择最有效的查询计划的过程。-外部排序的算法（初始归并段的数目、归并的趟数）趟数= logM-1 ( br/M )代价= 2 br + 2 br logM-1 (br/M )br = br ( 2logM-1 (br/M )+ 1 )-各种连接算法及其代价分析（嵌套循环连接算法、块嵌套循环连接算法、归并连接算法、排序-归并连接算法）重点掌握散列连接方法对于基于主码、外码连接的情况：结果集的元组数等于外码所在表的元组数。-为什么要进行结果集大小的估计？DBMS中存储的统计信息的作用是什么？决定是否引用索引 DBMS中存储的统计信息的作用是制定执行计划，计算结果集的大小。 -启发式优化的步骤。1.将合取选择分解为单个选择运算的序列。这有助于将选择运算往查询树下层移。2.把选择运算在查询树上下推到最早可能执行的地方。 例如，尽可能将(r s)转换成( r) s或r (s)3. 通过使用 的结合律，重新组织查询树，使得具有限制比较严格的选择运算的叶结点关系首先执行。4.将跟有选择条件的笛卡尔积运算替换成连接运算。5.将投影属性加以分解并在查询树上尽可能往下推。必要时可以引入新的投影运算。6.识别那些可用流水方式执行其运算的子树，并采用流水线方法执行之。-事务的ACID特性，以及分别有什么机制保证原子性(Atomicity) 事务中包含的所有操作要么全做，要么全不做 原子性由恢复机制实现一致性(Consistency)事务的隔离执行必须保证数据库的一致性事务开始前，数据库处于一致性的状态；事务结束后，数据库必须仍处于一致性状态数据库的一致性状态由用户来负责，由并发控制机制实现隔离性(Isolation)系统必须保证事务不受其它并发执行事务的影响对任何一对事务T1，T2，在T1看来，T2要么在T1开始之前已经结束，要么在T1完成之后再开始执行 隔离性通过并发控制机制实现持久性(Durability)一个事务一旦提交之后，它对数据库的影响必须是永久的系统发生故障不能改变事务的持久性 持久性通过恢复机制实现-事务可串行化的判断一般采用优先图来实现。-锁表及其工作原理锁表是将数据库元素与有关该元素的封锁信息联系起来的一个关系表可以用一个散列表来表示，使用数据库元素（地址）作为散列码。任何未被封锁的元素在表中不出现，因此表的大小只与被封锁元素的数目成正比，而不是与整个数据库的大小成正比。-同数据库交互的三个地址空间. 1 保存数据库元素的磁盘块空间 2 缓冲区管理器所管理的虚存或主存地址空间 3 事务的局部地址空间-数据库中主要有哪几类故障。数据库系统中的故障可以分以下几类：（1）事务内部的故障；（2）系统故障；（3）介质故障；（4）计算机病毒。事务故障、系统故障和介质故障影响事务的正常执行；介质故障和计算机病毒破坏数据库数据。-使用undo/redo日志进行恢复的方法。 使用undo/redo日志的恢复 1. 从后往前扫描日志，构造undo-list 和redo-list： 对每一个形如的记录，将Ti 加入redo-list。 对每一个形如的记录，如果Ti不属于redo-list，则将Ti加入undo-list。 2. 由后至前重新扫描日志，对undo-list中的每个事务Ti的每一个日志记录执行undo操作。 3. 由前至后重新扫描日志，并且对redo-list中每个事务Ti的每一个日志记录执行redo操作。 -undo / redo日志中，检查点的创建需要做的工作。1）写入日志记录，其中T1, , Tk是所有的活跃事务，并刷新日志。 2）将所有脏缓冲区写到磁盘，脏缓冲区即包含一个或多个修改过的数据库元素的缓冲区。 3）写入日志记录并刷新日志。-数据在分布式数据库的存储途径有哪三种。复制 系统维护关系的几个完全相同的副本，这些副本存储在不同的结点上分片 关系被划分为几个片段，各个片段存储在不同的结点上复制+分片 关系被划分为几个片段，系统为每个片段维护几个副本-分布式数据库中数据访问的瓶颈分布式数据库中数据访问的瓶颈是磁盘I/O、网络传输。 -分布式数据库中，数据分片的四种方式。将关系分片，有利于按用户需求组织数据的分布。分片方式、水平分片、垂直分片、导出分片、混合分片-混合分片半连接的实现方法（讲义中的示例）混合分片关系按某种方式分片后，得到的片段再按另一种方式继续分片如SC（S#，C#，G）按学生系别分片，再对每个片段按成绩（及格，不及格）分片-集成视图与数据源之间的数据一致性的四个级别。收敛一致性(convergence)、弱一致性(weak consistency)、强一致性(strong consistency)、完全一致性(completeness)-信息集成的三个方面的问题自治性: 信息源系统独立地决定其自身特性，保持其分开的独立控制，随着时间改变数据与功能这种改变不应受到集成系统过多制约。异质性：信息源独立地选择系统平台、数据管理系统,并以其自身观察和理解方式对所关心真实世界进行建模。分布性： 用户基于某种全局模式提出查询或其他数据操作请求,这些请求需要通过重写分解为信息