徐俊刚分布式数据库系统及其应用课后习题及答案.docx
《徐俊刚分布式数据库系统及其应用课后习题及答案.docx》由会员分享,可在线阅读,更多相关《徐俊刚分布式数据库系统及其应用课后习题及答案.docx(18页珍藏版)》请在冰点文库上搜索。
徐俊刚分布式数据库系统及其应用课后习题及答案
第一章分布式数据库系统概述
1.1请用自己的语言定义下列分布式数据库系统中的术语:
(1)全局/局部数据:
(详见课本第9页所谓的局部数据是指……;所谓的全局数据是指……)
(2)全局/局部用户(应用):
(3)全局/局部DBMS:
(4)全局/局部DB:
(5)全局外模式:
(详见课本第13页)由全局用户视图组成,是全局概念模式的子集。
(6)全局概念模式:
(详见课本第13页)定义分布式数据库系统中所有数据的整体逻辑结构,是全局应用的公共数据视图。
(7)分片模式:
(详见课本第13页)是全局数据整体逻辑结构分割后的局部逻辑结构,是DDBS的全局数据的逻辑划分视图.
(8)分配模式:
(详见课本第13页)用于根据选定的数据总体分配方案,定义各片段的物理存放地点.
(9)局部概念模式:
(详见课本第13-14页)是全局概念模式被分片和分配到局部场地上的映像的逻辑结构及特征的描述,是全局概念模式的子集。
其逻辑结构与局部DBMS所支持的数据模型有关,当全局数据模型与局部数据模型不同时,局部概念模式还应包括数据模型转换的描述。
(10)局部内模式:
描述局部概念模式涉及的数据在局部DBMS中的物理结构及物理存储细节,完全与非分布式系统相同。
1.2采用分布式数据库系统的主要原因是什么?
(P1)
1.3分布式数据库系统可分为哪些类?
(课件第1章4.2。
课本P6,7,8)
1.4什么是分布式数据库系统?
它具有哪些主要特点?
怎么样区别分布式数据库系统与只提供远程数据访问功能的网络数据库系统?
(分布式数据库系统的定义、特点详见课件第1章4.1.课本P6)
1.5分布式DBMS具有哪些集中式DBMS不具备的功能?
(课件第1章5.5附加功能。
课本P15)
1.6用自己的语言解析“什么时候需要进行数据分片和数据复制”?
(课本第10,11页)
1.7在分布式数据库系统中,为什么要对数据进行分片?
什么是关系的片段?
关系的片段有哪些主要类型?
(课本第9-10页。
数据分片是指数据存放单位不是全部关系,而是关系的一个片段。
也就是关系的一部分。
包括:
(1)水平分片:
按一定的条件把全局关系的所有元组划分成若干不相交的子集,每个子集为关系的一个片段。
(2)垂直分片:
把一个全局关系的属性集分成若干子集,并在这些子集上做投影运算,每个投影为垂直分片。
(3)混合型分片:
将水平分片与垂直分片方式综合使用则为混合型分片。
)
1.8为什么说分布式数据库系统中,数据独立性这一目标比集中式数据库系统更为重要,也更为复杂?
(详见课本第25页第二段)
1.9概述分布式DBMS的参考模型中,用户处理器、数据处理器、全局数据库控制和通信子系统的组成和功能。
(组成(参考模型):
详见课件5.6;功能:
用户处理器课本第18页;数据处理器课本第20页;全局数据库控制和通信子系统课本第21页)
1.10分布式数据库系统潜在的优点是什么?
存在哪些技术问题?
(优点:
详见课本第34-35页共6点;技术问题详见课本第35-36页面共7点)
第二章课后习题
2.1概述分布式数据库系统的创建方法、方法特点和适用范围
答:
创建方法有:
组合法、重构法
组合法的特点:
剖析网络功能;剖析原有数据库系统;解决数据的一致性、完整性和可靠性;难度较大;
组合法适用范围:
通常是异构或者同构异质DDBS
重构法的特点:
根据实现环境和用户需求;按照DDBS的设计思想和方法;从总体设计做起,包括LDBS,重新建立一个DDBS;可有效解决数据一致性、完整性和可靠性问题。
重构法的适用范围:
通常是同构异质或同构同质DDBS
2.2分布式数据库设计的主要目标是什么?
P42,第二段起-43第三段;课件:
第二章,第9张幻灯
2.3概述分布式数据库设计的关键问题及解决方法
答:
关键问题:
1)访问的多个数据对象是存放在同一站点上还是分布在多个站点所需的时间和费用有很大区别。
2)数据对否被复制、复制副本的多少问题
3)数据分片、片段如何复制、数据或片段如何分布、分布式数据库管理系统的透明性
解决方法:
1)分布式数据库遵循本地性或近地性,尽量减少通信次数和通信量,90/10准则,分片和分布方案(本地和远程访问次数)择优;
2)控制数据适当冗余,冗余增加了可靠性、可用性,提高了效率,维护数据一致性开销增加
3)工作负荷分布
4)存储能力和费用
2.4考虑为局域网设计的分布式数据库系统和为广域网设计的分布式数据库系统由什么区别?
这道不会,参考p421.分布式数据库的本地性或近地性
2.5请用自己的语音阐述分布式数据库设计的自顶向下和自底向上设计方法及其适用范围。
答:
自顶向下:
从概念设计到形成形式规格说明设计分布式数据库。
适用范围:
通常是同构异质或同构同质DDBS。
自底向上:
通过聚集现存数据库来设计分布式数据库。
适用范围:
通常是异构或者同构异质DDBS。
2.6数据分片应遵守哪些原则?
数据分片要准守的原则:
完备性原则:
要把所有的数据映射到各个片断中
可重构原则:
关系分片后的各个片断可重构整个关系
不相交原则:
关系分片后的各个片断不能重叠
●数据分片有哪些基本类型和方法?
P45第3段-5段
2.7为什么说在关系型分布式数据库中使用导出式水平分片,使关系之间的连接变得更加容易?
试举例。
答:
原因:
可将连接条件代之以子查询,从而使它变为一般的判别条件。
具体实例可见课本47页。
2.8采用DATAID-D方法的分布式数据库设计与传统的集中式数据库设计在步骤和内容上有什么不同?
P522.3.1节的2、3、4段
2.9考虑图2.12所示的公司数据库的分片和分布。
假设该公司有三个计算机站点,……题目P67,答案在p383
2.10连锁百货店具有地域上分散而管理闪又相对集中的特点……题目在p68,答案在p384
第三章
1、分布式查询和集中式查询的相同点即在本地的CPU和I/O代价,不同点为分布式查询比集中式查询多了通讯代价
2、p79
3、p79~p80
4、基本原理:
p84~p85适用情形:
p85,由此可见那段,第四行的“所以。
。
。
”开头
5、
6、6、
(1)R∞S∞T
A
B
C
D
E
I
2
3
5
6
6
9
1
6
8
3
8
9
5
3
5
6
6
9
2
6
8
3
8
9
(2)R∝S
A
B
C
2
3
5
1
6
8
5
3
5
2
6
8
S∝R
B
C
D
3
5
6
3
5
9
6
8
3
S∝T
B
C
D
3
5
6
6
8
3
5
9
6
4
1
6
T∝R为空
R∝T为空
T∝S
D
E
I
6
6
9
3
8
9
7、
解:
假设每个属性域长度均为1B,考虑所有的半连接
a)选择得益最高的P2进行优化,得到新的R,S’,T,并对受到影响的的方案重新计算得益和费用。
新的R,S’,T如下:
对受到影响的的方案重新计算得益和费用
b)选择得益最高的P4进行优化,得到新的R,S’,T’,并对受到影响的方案重新计算得益和费用。
新的R,S’,T’如下:
对受到影响的的方案重新计算得益和费用
c)选择得益最高的P1进行优化,得到新的R’,S’,T’,并对受到影响的方案重新计算得益和费用。
新的R’,S’,T’如下:
对受到影响的的方案重新计算得益和费用
d)选择得益最高的P3进行优化,得到X,Y,Z站点上最终的R’,S’’,T’。
X,Y,Z站点上最终的R’,S’’,T’如下:
所以选择各站点做连接的代价为:
X站点代价=2*3+2*3=12
Y站点代价=4*3+2*3=18
Z站点代价=4*3+2*3=18
故选择X站点作为收集站点代价最低。
由简化过程得知半连接过程为:
1.S’=S∝R
2.将S’传送给T,做半连接T∝S’得到T’
3.将S’传送给R,做半连接R∝S’得到R’
4.将T’传送给S’,做半连接S’∝T’得到S’’
即:
(R∝(S∝R))∞((S∝R)∝(T∝(S∝R))∞(T∝(S∝R))
8、
1)将NewYork站点上的副本传至Toronto站点;
2)在NewYork站点上求平均工资,传至Toronto站点;
3)Toronto,Edmonton,Vancouver,Montreal求最高工资,传至Toronto汇总;
10、
(1)提出查询的站点:
(1)Aromonk站点,plant-number=X的站点;
(2)Aromonk站点,plant-number=Xi的站点;(3)各工厂站点
(2)需要结果的站点:
(1)plant-number=X的站点,Aromonk站点;
(2)plant-number=Xi的站点,Aromonk站点;(3)Aromonk站点
4.1概述分布式数据库系统中事务的定义、特性、结构和状态,以及分布式事务所特有的性质。
分布式数据库系统中的事务是一个分布式操作的序列,被操作的数据分布在不同的站点上,所以称为分布式事务。
分布式数据库系统中的事务具有事务的ACID四个特性,即原子性、一致性、隔离性和耐久性。
分布式数据库系统中事务的结构以begintransaction原语作为一个事务的开始,以commit原语作为一个事务成功完成的结束,而以rollback或abort原语作为事务失败的结束。
分布式数据库系统中的事务状态(这点找不到……)
分布式事务所特有的性质有大量的数据传递、通信原语和控制报文等。
4.2请用自己的语言描述分布式事务管理的抽象模型和分布式事务执行的控制模型。
4.3分布式数据库系统中的事务管理与集中式数据库系统中的事务管理有何不同?
分布式与集中式相比,会多遇到一些问题:
(1)处理数据项的多个副本;
(2)单个站点的故障;(3)通信网络的故障;(4)分布式提交。
4.4什么是事务的提交点?
为什么说它们很重要?
当事务所有的站点数据库存取操作都已成功执行,并且所有操作对数据库的影响都已记录在日志中时,该事务就到达提交点。
(为什么说它们很重要?
这点找不到……)
4.5日志、档案库和检查点的作用是什么?
典型的日志包含哪些内容?
为什么要“先写日志”?
日志的作用是为了能够从故障状态中恢复有影响的事务。
档案库的作用是为了防止因介质故障而破坏日志和数据库。
检查点的作用是为了便于恢复事务。
典型的日志包含了每个改变数据项值的写操作记录。
因为系统崩溃时主存中的内容可能丢失,所以恢复时只能考虑已写回磁盘的日志内容。
因此,在事务到达提交点以前,还未写到磁盘的日志的任何部分,必须被写入磁盘,即“先写日志”。
4.6列出分布式数据库系统中可能出现故障类型。
哪些故障也可能出现在集中式数据库系统中?
事务故障、系统故障、介质故障、站点故障、通信故障。
事务故障、系统故障、介质故障也可能出现在集中式数据库系统中。
4.7请用自己的语言描述两阶段提交过程。
4.8为什么说两阶段提交协议在不丢失运行日志信息的情况下,可从任何故障恢复?
因为在执行过程中维护了事务日志,记录了执行恢复所需要的信息。
4.9在分布式数据库系统中对多副本数据的更新通常采用什么方法?
快照方法的优点和缺点是什么?
主文本更新法、快照方法。
快照方法的优点:
既避免了某些并发空控制的开销,又便于复杂查询的完成,是提高系统可用性的有效方法。
缺点:
快照只是一个只读关系,其中数据只能读而不能写。
4.10为什么说分布式事务增强了数据库的一致性?
第五章
5.1为什么说分布式数据并发控制比集中并发控制要复杂得多?
P131第二段分布式数据库中。
。
。
。
要复杂得多。
5.2描述分布式事务的可串行化理论的一些定义:
事务、冲突操作、并发调度、串行调度、一致性调度、两个调度等价、可串行化调度。
事务:
P134一个事务是一个偏序集。
。
。
。
序列中的一个操作。
冲突操作:
P135如果有两个操作。
。
。
称为冲突的操作
并发调度:
P135如果T={T1,T2。
。
。
,Tn}….执行顺序。
串行调度:
P135如果一个调度。
。
。
相继执行的。
一致性调度:
P135如果执行一个调度。
。
。
。
为一致性调度
两个调度等价:
P135两个调度。
。
。
。
Oi串行调度:
与串行。
。
。
可串行化调度。
5.5什么是两阶段封锁协议?
它如何保证可串行性?
为什么人们经常更愿意采用严格两阶段封锁和严酷两阶段封锁?
答:
所谓两段锁协议是指所有事务必须分两个阶段对数据项加锁和解锁:
1.在对任何数据进行读、写操作之前,首先要申请并获得对该数据的封锁。
2.在释放一个封锁之后,事务不再申请和获得任何其他封锁。
因此保证可串行性。
由于实现基本2PL协议要锁管理器必须要知道事务的锁点位置;保守2PL要事先声明续集和写集,这都是难以实现的。
严格2PL和严酷2PL容易实现。
严格2PL的实现方法是:
事务在提交或者撤销之前,绝对不释放任何一个写锁;事务结束时(提交或者撤销),同时释放所有的锁。
严酷2PL的实现方法是:
事务T在提交或撤销之前,不能释放任何一个锁(写锁或者读锁),因此它比严格2PL更容易实现。
5.6描述死锁预防中的占先权方法和非占先权方法,比较它们的异同。
描述检测分布式死锁的三种基本方法。
答:
等待-死亡模式(非占先权)的方法:
如果Ti对已被Tj封锁的一数据项请求封锁的话,则只有在Ti比Tj年老时(Ti如果Ti比Tj年轻(Ti>Tj),则Ti被终止并带有同一时间戳重新启动。
这个方法的理论基础是:
最好总是重新启动较年轻的事务,允许较年老的事务去等待已持有资源的较年轻的事务,但不允许较年轻的事务去等待较年老的事务。
受伤-等待模式(占先权)的方法是:
如果Ti对已被Tj封锁的一数据项请求封锁的话,则只有在Ti比Tj年轻时(Ti>Tj),才允许Ti等待。
否则,Ti比Tj年老(Ti这个方法的理论基础是:
只有年轻的等待年老的。
两种方法的异同:
课本P159,第2、3、4、5、6段。
集中式死锁检测方法:
选择一个站点负责整个系统的死锁检测,死锁检测器放到这个站点。
每个站点的锁管理器周期性地将本站点的LWFG传送给死锁检测器,死锁检测器构造GWFG,并在其中寻找回路;或者,其它每个站点上的锁管理器周期性地把记录本站点上事务的开始时间,对锁的持有、请求情况变化的动态表,发送给负责处理封锁的站点,由它维护一张全局封锁动态表,形成GWFG,并在其中寻找回路。
如果至少包含一条回路,它会选择一个或者多个事务,把它们取消并恢复,释放资源,使得其它事务继续进行。
选择的标准是尽可能使撤销并恢复的代价最小,如撤销年轻的事务,撤销占有较少资源的事务,撤销具有最短运行时间的事务,撤销具有最长运行时间的事务等,使系统情况而定。
层次式死锁检测方法:
树叶是各站点的局部死锁检测器,在本站点建立局部等待图。
本站点的死锁检测器找出本站点局部等待图中的任何回路,并把有关潜在全局回路的信息发送给上一层死锁检测器。
每个非本地死锁检测器只对它所涉及的紧挨下层进行死锁检测,合并这些接收到的有关潜在全局回路的信息,并找出任何回路。
如果还有上层死锁检测器,将经过简化的有关潜在全局回路的信息发送给它上一层死锁检测器,由上一层死锁检测器再进行合并,找出任何全局回路。
这样,逐层检测,直到最高层。
分布式死锁检测方法:
使用局部信息建造LWFG,该LWFG包含EX节点。
对每次接收到的信息,执行如下对LWFG的修改。
对报文中的每个事务,若LWFG中不存在,则将其加入。
从EX节点开始,按照报文所给的信息,建立一个到下一个事务的边。
在新的LWFG中寻找不含EX的Loop,若存在,则检测到死锁。
在新的LWFG中找到含有EX的Loop,于是有潜在的死锁,再按规定向外传送信息。
5.7什么是多粒度封锁和意向锁?
它们在什么情况下使用?
答:
多粒度封锁是:
封锁的粒度不是单一的一种粒度,而是有多种粒度。
可以定义多粒度树,根节点是整个数据库,叶节点表示最小的封锁粒度。
意向锁是:
如果对一个节点加意向锁,则说明该节点的下层节点正在被封锁。
对任一节点封锁时,必须先对它的上层节点加意向锁。
具有意向锁的多粒度加锁方法中,任意事务T要对一个数据对象加锁,必须先对它的上层节点加意向锁。
申请封锁时应该按自上而下的次序进行,释放锁时则应该按自下而上的次序进行。
具有意向锁的多粒度加锁方法提高了系统的并发度,减少了加锁和释放锁的开销。
它已经在实际的DBMS系统中广泛应用,例如Oracle中。
5.8在分布式数据库系统中如何产生和调整全局时标?
讨论基于时标的并发控制技术中的基本时标和保守时标法。
答:
全局时标分配方法:
使用全局的单调递增的计数器,全局的计数器维护是个难题。
全局唯一时间的形成与调整:
每个站点设置一个计数器,每发生一个事务,计数器加一。
发送报文时包含本地计数器值,近似同步各站点计数器。
基本时标法规则:
每个事务在本站点开始时赋予一个全局唯一时标。
在事务结束前,不对数据库进行物理更新。
事务的每个读操作或写操作都具有该事务的时标。
对每个数据项x,记下写和读操作的最大时标,记为WTM(x)和RTM(x)。
如果事务被重新启动,则被赋予新的时标。
保守时标法规则:
每个事务只在一个站点执行,它不能激活远程的程序,但是可以向远程站点发读/写请求。
站点i接收到来自不同站点j的读/写请求必须按时标顺序,即每个站点必须按时标顺序发送读/写数据请求,在传输中也不会改变这个顺序。
每个站点都为其它站点发来的读/写操作开辟一个缓冲区,分别保存接收到的读/写申请。
5.10乐观并发控制技术和其他的并发控制技术有什么不同?
为什么它们也被称为确认或者验证技术?
讨论一个乐观并发控制方法的典型阶段。
答:
并发控制乐观方法的基本思想是:
对于冲突操作不像悲观方法那样采取挂起或拒绝的方法,而是让一个事务执行直到完成。
在乐观方法中,改变了通常每个“读集包含写集”事务执行的三个阶段的顺序,
(1)读/计算阶段;
(2)验证阶段;(3)写阶段。
课本P169。
备注:
例题5.3去年考到了,不过增加了2个调度,就是4个调度。
主要考察给出若干个调度,然后分别画出每个调度的优先图,再根据优先图来判别调度是否为串行化调度。
貌似最后一节课的时候李院长说了这个是必考内容。
5.4和5.9不会写,李院长讲这些内容的时候我没来上课。
第6章
6.1如何理解分布式数据库的可靠性和可用性?
如何度量它们?
可靠性
–指数据库在一给定时间间隔内不产生任何失败的概率。
–它强调数据库的正确性,要求数据库正确运行,既符合某种规格化要求。
–通常用来描述不可修复的系统。
可用性
–强调的是当需要访问数据库时,它是可用的。
–指在给定的时间点系统可以正常运行的概率。
–通常用于描述那些可以修复的系统。
如何度量它们:
(1)平均故障间隔时间,
(2)平均修复时间
6.2分析分布式数据库系统中系统失败的原因,你知道有哪些基本的容错方法和技术?
P175和P177
6.3概述分布式可靠性协议的组成以及他们各自的适用范围。
P179和P180页1-2段
6.4讨论两阶段提交协议的终结协议和两阶段提交协议的恢复协议。
(1)P1826.3.4节的后2段。
(2)P1856.3.5节的后一段。
6.5什么是三阶段提交协议?
讨论三阶段提交协议的终结协议和三阶段提交协议的恢复协议。
(1)P187倒数第3段。
(2)P187的最后一段。
(3)P190第3段。
6.6为什么三阶段提交协议也不能处理网络分割?
讨论网络分割如何被其他协议处理?
课件第6章53张PPT4.1节的内容
6.7什么情况下要进行不一致性检测?
讨论不一致性检测及其解决方法。
(1)P199第3段
6.8为什么说在分布式数据库系统中,冷启动是极其困难的?
什么情况下才使用冷启动?
(1)P201第6段。
(2)P2016.5.3节后一段第2行。
6.9在设计一个分布式数据库时,应该要考虑哪些问题?
可靠性和可用性等方面、
6.10设一个分布式数据库有三个站点和三个数据项X,YZ,他们的分布如图6.9(a)所示,有可能出现网络分割故障的全部可能方式……P387
第七章
7.1讨论数据库权限和授权、自主访问控制、强制访问控制、数据库审计、多级安全数据库、BLP模型的含义或内容。
答:
①权限和授权在P213页7.2.2里面的权限控制小节,“为了实现数据库数据的安全……….”“用户对数据对象的访问权可以静态地分配……”;
②自主访问控制和强制访问控制在P212页(11)(12);
③数据库审计在P211页第一段,课件里面也有:
也可以通过对系统日志的扩充来记录用户和相关操作的信息
系统日志包括对分布式数据库的实施的每一个操作的入口项,事务故障和系统故障时就需要利用这些记录对数据库进行恢复
如果怀疑出现了对数据库的任意篡改,就可以执行数据库审计
–审计扫描一段时间内的日志,以检查所有作用于数据库的存取动作和操作
–当发现一个非法的或未授权的操作时,DBA就可以确定执行这个操作的帐号
数据库审计对于敏感性数据库非常重要,比如银行数据
用于安全性的数据库日志,也叫审计跟踪;
④多级数据库和BLP模型在P217页的7.2.3
7.2 什么是数据库的安全性?
用你自己的语言阐述分布式数据库存在的不安全因素及其防范措施。
答:
数据库的安全性:
P206 第三段
不安全因素及防范措施:
P206 第四段
(1)-(3)点
7.3在你使用的或者你了解的某个支持分布式数据库的DMBS中,提供了哪些实施数据库安全性的方法和技术?
答:
数据库随便写,安全性的方法和技术在P228页的7.5.3
7.4 试述《可信计算机系统评估标准》(TCSEC)和《可信计算机系统评估标准的可信数据库管理系统说明》(TCSEC-TDI)将系统安全划分为四类七个级别的基本内容。
答:
P226 第六段到本页结束 P227第二段最后一句
7.5理解并解释强制访问控制(MAC)机制中的主体、客体、安全性级别标记(敏感度标记)的含义。
举例说明MAC机制如何确定主体能否访问客体。
答:
主体(Subject):
引起信息流动或改变系统状态的主动实体,如用户,程序,进程。
客体(Object):
蕴含或接收信息的被动实体,信息的载体,如DB,表,记录,视图,属性等。
主体能否访问客体在P219页最下面。
7.6 统计数据库中存在何种特殊的安全性问题?
答:
P222 第三段第一句、第三段最后三句、第四段
7.7为什么进行数据加密?
概述数据加密的一般方法。
答:
P223的7.4.1有数据加密的必要性,P224有图7.2下面有数据加密的一般方法。
7.8 简述分布式数据库目录的内容、用途、组织方式、逻辑结构和分布方式。
为什么说在分布式数据库系统中目录系统占更加重要的地位?
答:
目录的内容:
P232 第一段
用途:
P233 第1到5小点
组织方式:
P234 第二段 第1-3点
逻辑结构:
P234最后一段 P235第1、2、3、4段
分布方式:
P236 第1到第5大点
原因:
P231倒数最后一段
7.9讨论因“分布”和“站点自治”而引起的权限保护和用户识别问题。
答:
P238的7.7一整节都讲