数据库

数据库原理复习大纲一、名词解释事务：用户定义的一个数据库操作序列，这些操作要么全做要么不做，是一个不可分割的单位。封锁：事务T在对某个数据对象例如表、记录等操作之前，向系统发出请求进行加锁。是实现并发控制的一个非常重要的技术。串行调度：数据库中，一个调度中，属于一个事务的所有操作连续执行，称之为串行调度。可串行化调度：多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行的执行这些事务时的结果相同，称这种调度策略为可串行化的调度。两段封锁协议：所有事务必须分两个阶段对数据项加锁和解锁。分布式DBS（数据库系统)：由一组数据组成的，这组数据分布在计算机网络的不同计算机上，网络中的每一个结点具有独立处理能力，可以执行局部应用。同时每个结点能通过网络通信子系统执行全局应用。分布式DBMS：是建立、管理和维护分布是数据库的一组软件。由局部场地上的数据库管理系统（LocalDBMS）、全局数据库管理系统（GlobalDBMS）、全局数据字典（GDD）和通信管理（CM）四部分组成。数据复制：数据复制是将一组数据从一个数据源拷贝到多个数据源的技术，同时也可以将它理解为一份数据发布到多个存储站点上的有效方式。数据分片：使数据存放的单位不是关系而是片段。有利于按照用户需求较好的组织数据分布，也能有利于控制数据冗余度。分片透明：指用户或应用程序只对全局关系进行操作而不必考虑关系的分布。位置透明：用户或应用程序不必了解片段的存储场地。OODBS：面向对象数据库系统，它既具有数据库管理的基本功能，又支持面向对象数据模型。可变格式记录：字段或字段顺序不是完全由记录或表示元组或对象的关系或类决定。其最简答的表示格式是标记字段序列，标记字段包括字段角色和字段值。可变长记录：字段的长度不是固定的。在字段首部写入记录长度，指向所有变长字段的起始处的指针。稀疏索引：只为每个存储块设置一个键——指针对，键值是每个数据块中第一个记录的对应值。稠密索引：块中只存放记录的键以及指向记录本身的指针。辅助索引：为给查询带来便利，在一个关系上建立多个索引。多级索引：在索引上再建索引，使第一级索引更为有效。二、问答题1试叙事务的四个性质，并解释每一个性质对DBS有什么益处?原子性、一致性、隔离性、持续性原子性是事务的逻辑工作单位。一致性是数据只包含成功事务提交结果时数据库的所处的状态。隔离性保证一个事务的执行不能被其他事务干扰。持续性指一个事务一旦提交，它对数据库中数据的改变就应该是永久的。2事务的COMMIT操作和ROLLBACK操作各做些什么事情?当事务故障时，COMMIT命令用于把事务所做的修改保存到数据库，它把上一个COMMIT或ROLLBACK命令之后的全部事务都保存到数据库。ROLLBACK命令是系统将事务中对数据库的所有已经完成的操作全部撤销，回滚到事务开始时的状态，使得事务好像根本没有启动一样。3UNDO操作和REDO操作各做些什么事情?UNDO（撤销）REDO（重做）4DBS中有哪些类型的故障?哪些故障破坏了数据库?哪些故障未破坏数据库，但其中某些数据变得不正确?事物内部故障数据库可能处在不正确状态。系统故障影响正在运行的所有事务但不破坏数据库。介质故障破坏数据库或部分数据库，并影响正在存取这部分的所有事务。计算机病毒对数据库有危害，使其中数据变得不正确。5什么是“运行记录优先原则”？其作用是什么？在数据库系统中，写一个修改到数据库中和表示这个修改的登记记录到日志文件中是两个不同的操作，在这两个操作之间可能发生故障。这时，如果先写了数据库修改，而在记录中没有登记这个修改，则以后就无法恢复这个修改，那么以后也就无法撤销这个修改。为了安全起见，采用“运行记录优先原则”它包括两点：至少要等相应运行记录已经写入日志文件后，才能允许事务往数据库中写记录。直至事务的所有运行记录都已写入日志文件后，才能允许完成“ENDTRANSACTION”处理。6什么是数据库的恢复？恢复的基本原则是什么，恢复如何实现？当系统发生故障时，数据库管理系统必须具有把数据库从错误状态恢复到某一已知的正确状态功能，这就是数据库恢复。原则：冗余，即数据的重复存储。实现：定期对数据库进行复制或转储、登记日志文件、恢复。7数据库的并发操作会带来哪些问题？如何解决？丢失修改、不可重复读、读“脏”数据解决办法：封锁、时间戳、乐观控制法。8试叙述串行调度与可串行化调度的区别。串行调度是多个事务按照一定的次序依次执行，在某个时刻只有一个事务执行。可串行化调度是并发调度的一个概念。在并发调度中，某一时刻有多个事务同时被处理，如果某事务集的一个并发调度结果与某个串行调度等价，则称为并发调度是可串行化调度。9分布式数据库系统有哪些优点和缺点?优点：(1)具有灵活的体系结构(2)适应分布式的管理和控制机构(3)经济性能优越(4)系统的可靠性高、可用性好(5)局部响应速度快(6)可扩展性好，易于集成现有系统缺点：(1)系统开销大，主要花在通信部分(2)复杂的存取结构，原来在集中式系统中存取数据的技术，在分布式系统中都不适用。(3)数据的安全性和保密性较难处理。10分布式数据库中，数据分配有哪些策略?数据分片有哪些策略?数据分片的准则是什么?“数据分配”策略：(1)集中式：所有数据均安排在同一场地。(2)分割式：所有数据只有一份，分别安置在若干场地。(3)全复制式：数据在每个场地重复存储。(4)混合式：数据库分成若干可相交子集，每一子集安置在一个或多个场地上，但是每一场地未必保存全部数据。“数据分片”策略：(1)水平分片：按一定的条件把全局关系的所有元组划分成若干不相交的子集，每个子集为关系的一个片段。(2)垂直分片：把一个全局关系属性集分成若干子集，并在每个子集上做投影运算，每个投影为垂直分片。(3)混合型分片：将水平分片与垂直分片综合使用。数据分片准则：(1)完备性条件：必须把全局关系的所有数据映射到各个片段，决不允许发生属于全局关系的某个数据不属于任何一个片段。(2)重构条件：划分所采用的方法必须确保能够由各个片段重建全局关系。不相交条件：要求一个全局关系被划分后得到的各个数据片段互相不重叠。11分布式系统中影响查询的主要因素是什么?主要因素：12基于半联接的查询优化策略的基本思想是什么?不参加连接的数据不在网络中传输。13在OO技术与DB技术相结合过程中，采取了哪两条不同的途径？一条是在传统的关系模型基础上，提供复合数据类型，扩充SQL语言使之能处理新的数据结构。这种模型称为对象关系模型，还不能说是严格意义上的面向对象数据模型。但用户易于接受，易于推广。另一条是在OOPLC++基础上进行扩充，能操作持久数据，形成持久化C++系统，即OODBS。但较难提供说明性查询的支持，因此推广使用难度较大。14DBMS的程序模块可按功能划分为哪些主要部分？（1）模式翻译（2）应用程序的翻译（3）交互式查询（4）数据的组织与存取（5）事务运行管理（6）数据库的维护15试叙述一个DBMS运行过程实例?16数据库中要存储哪四个方面的数据？并说明。（1）数据描述，即数据的外模式、模式、内模式；（2）数据本身；（3）数据之间的联系；（4）存取路径这4个方面的数据内容都要采用一定的文件组织方式组织、存储起来。17试描述两阶段多路归并算法？其主要步骤如下:(1)在所有子表载入主存的数据块中的第一个元素中找出最小记录；(2)将最小记录移动到输出块的第一个可用位置;(3)如果输出块已满，则将其写入磁盘，并重新初始化该缓冲区;(4)如果数据块中的元素已经取完，则从相同的子表中读出下一个块到相同的缓冲区，如果没有块剩余，则该缓冲区为空。18给一个索引关键范围[a,b]，试写出B+树上的指定范围查找算法。19试至少举出5种改善二级存储器访问性能的方法。20当系统从崩溃中恢复时，它构造一个undo-list和一个redo-list。解释为什么undo-list中事务的日志记录必须有后至前进行处理，而redo-list中的事务的日志记录则必须由前至后进行处理。27叙述查询处理过程28请说明一个没有子查询的语法树转换为关系代数的原则？29存储在数据库中的物理数据有哪几种类型，试说明之。（1）数据主体：用户数据本身及辅助信息。（2）数据字典：有关用户数据的描述信息。（3）数据间的联系信息：数据与数据间的联系信息，在关系数据库中，这类信息也是作为数据主体组织存储的。（4）数据存储路径信息：访问数据库的途径，在关系数据库中，可以使用的存储路径有：索引、HASH、集簇等。（5）其他信息：与数据主体及其使用有关的其他信息，包括：日志信息，用户信息，审计信息等。30文件有哪几种常用的格式？它由哪些内容组成？请说明之。顺序文件，索引文件，B树类文件和HASH文件。顺序文件通常用于组织数据的存储，是一种记录式文件。索引文件用于提供访问数据的人口信息。B树类文件和HASH文件是索引文件最常使用的两种方式。31请说明记录与磁盘块之间的关系单块单记录，单块多记录，多块单记录，多块多记录。在数据库系统中最常用的是：多块单记录和单块多记录两种方式。多块单记录常用于单个记录的数据长度特别大的情况中，而较常用的是单块多记录组织方式。单块单记录对存储空间浪费较大，多块多记录虽然空间利用率高，但不利于文件的修改和扩充，所以这两种方式使用较少。21设文件F具有10000个记录，每个记录50字节，其中10字节用来表示文件的键值。每个磁盘块大小1000字节，指向磁盘块的指针占5字节，不允许记录跨两个块。1）存放整个文件需要多少个磁盘块？如果F是顺序文件，查找一个记录需要多少次磁盘I/O？如果F无序，查找一个记录需要多少次磁盘I/O？2）如果为文件F建立主索引，索引文件占用多少磁盘块？利用这个主索引查询需要多少次磁盘I/O？3）如果为文件F建立B+树索引，索引文件占用多少磁盘块？利用这个B+树索引查询需要多少次磁盘I/O？22设：关系R和S的元组字节数分别是IR和IS，元组数目分别是TR和TS，BR表示磁盘块数,M表示主存缓冲区的块数，b表示每个磁盘块字节数。试叙循环嵌套算法，并分析算法的磁盘存取量。23设教学数据库有三个关系：学生关系：S(S#,SNAME,AGE,SEX)选课关系：SC(S#,C#,GRADE)课程关系：C(C#,CNAME,TEACHER)数据库上的一个查询为“检索男同学选修课程的课程名和任课教师名”。写出该查询的初始关系代数表达式。画出初始关系代数表达式对应的查询树。使用启发式代数优化规则对该查询进行优化，画出优化的过程和最后结果。24用键值（2,3,5,7,11,17,19,23,29,31）建立一个B+树，假设树初始为空，值按照递增顺序加入。根据以下的能够容纳的最大指针数，分别构造B+树。(a)4(b)6(c)825假如一条记录有如下顺序的字段组成：一个长度为15的字符串，一个2字节整数，一个10字节的日期以及一个8字节的时间。如果每个记录有一个首部，由两个4字节指针和1个1字节的字符组成。问三种情况下，(a)字段可以在任何位置开始；(b)字段必须在4的整数倍开始；(c)字段必须在8的整数倍开始。一个大小4096字节的磁盘块，最多能够装入多少纪录（磁盘块的首部由10个4字节的整数组成）。26假设存储块能存放块能放10个记录或者99个键和100个指针，再加设B树结点的平均总满度为70%，即有69个键和70个指针。对于下面描述的结构，确定(1)1000000个记录的文件所需要的总块数；（2）检索一个给定键值的记录所需要的平均I/O数。假设最初在主存中不存在任何东西，并且查找键是记录的主键。(a)数据文件是按照查找键排序的顺序文件，每块存放10个记录。B树是稠密索引。(b)数据文件是顺序文件，且B树是稀树索引，但是数据文件的每个基本块有一个溢出块。平均来讲，基本块是满的，而溢出块半满。不过，记录在基本块和溢出块中没有特定的顺序。